HTTF2023(AHC016)参加記録

こんにちは。競技プログラミングのコンテストに参加しているyunixです。 最近行われたHACK TO THE FUTURE 2023予選(https://atcoder.jp/contests/ahc016)に参加して6位でした！ 上位10人に入れたのでオンサイトの本戦に行けそうです*1。とても楽しみです。

コンテスト中にやったことや考えたことを書いていこうと思います。

問題の概要

  • 高橋さんは過去に情報を送ることができるやばい機械を開発してしまいました(SERNに狙われるぞ...)
  • 過去にギャンブルの当選の情報を送って一攫千金を目論みました。M個の選択肢のうちから、当選する番号を送る必要があります。
  • 機械で送ることができる情報はグラフです。あらかじめギャンブル前にノード数NのグラフM個を選んでおいて、未来からグラフを送信します。
    • ノード数が多いグラフを送るにはエネルギーがたくさん必要なので、できるだけNが小さい方がありがたいです
  • 伝送路は結構ノイズが強くて、ε(問題ごとに0~0.4)の確率でグラフのエッジの情報が反転してしまいます。また、グラフの点のIDの情報がなくなってしまいます。
  • できるだけたくさん稼ぎたいので、ノイズに強いグラフを設定したいです。
  • 一つのテストケースの中では(M, ε)が与えられます。
    • Nをいい感じに決めて、エンコードするグラフをM個出力してください
    • 100回未来から信号が来るので、それがM個のうちどのグラフのものかを判定してください

解法の概要

手抜きですが、twitterに投稿したものをまず見ていただくと良いかもしれません:

  • グラフを識別するために、グラフの各ノードのエッジの数の分布をソートしたもの(次数列*2 )に注目します
  • 解答の作り方
    • エンコードする各グラフごとにノイズのシミュレーションを400回行って、ノイズが入った後の次数列を作って、次数列の期待値みたいなものを用意しておきます
    • 観測した信号の次数列と上で用意したグラフの次数列を比較して一番近いやつを解答します
  • エンコードするグラフの集合の選び方: エンコードするグラフ集合と問題ごとのNはローカルで事前計算する
    • 解答の作り方からして、次数列の期待値ができるだけばらけるような集合を用意したほうがよさそうです
    • たくさんのグラフを用意して、その中からM個のグラフの集合を選択して、次数列ができるだけバラけるようにしています。この選択の際に焼きなまし法を使っています。
    • グラフのサイズ(N)・選択肢の数(M)に応じてエンコードするべきグラフの集合が異なります。事前にローカルでよさそうな集合を作っていて、(M, N)ごとに情報を埋め込みました(あとεの大小に分けて作りました)。
    • また、問題で与えられる(M, ε)ごとに最適なNは決めることができるので、これについても事前にローカルで計算して定数としてプログラムに与えました
  • ε=0の場合は別に処理しました(記述を割愛)

また、nadareさんの解説が結構近い感じでした。他にも似たような感じで次数列に注目をして解いた人を何人か見つけました!*3 py2k4.hatenablog.com

解法の概要はこんな感じで、長期AHCにしては結構シンプルだったかなと思います。 細部で差がついた感じがあるので、細かいところを書いていこうかと思います。

詳細な解法

以下のような流れで解法を書いていきます

  • 各クエリに対してどのようにしてグラフを選択するか
  • エンコードに使用するグラフの集合をどのように決めるか
  • (M, ε)に対して最適なNを決める

最終提出はこれです: Submission #36689129 - HACK TO THE FUTURE 2023 qual（AtCoder Heuristic Contest 016）

1. 解答の作り方

まずは解答の作り方(未来から送られてきたグラフがどのグラフかを判定する部分)について書いていこうと思います*4。

と言っても大体概要に書いた通りではあります:

  • エンコードする各グラフごとにノイズのシミュレーションを400回行って、ノイズが入った後の次数列を作って、次数列の期待値みたいなものを用意しておきます
  • 観測した信号の次数列と上で用意したグラフの次数列を比較して一番近いやつを解答します

(多分)大事なポイントとしてはシミュレーションを行なって次数列の期待値を各グラフごとに計算したことです。

観測した信号の次数列の分布 x_0, x_1, ..., x_{M-1} と、エンコードしたグラフmの次数列期待値の分布 y_{m, 0}, y_{m, 1}, ..., y_{m, M-1} の距離を以下のように定義しました*5。

\displaystyle \sum_{k=0}^{M-1} pow(|x_{k} - y_{m, k}|, 2.60117)

これをグラフ間の距離と考えて、この距離が最も小さいものを答えるようにしました。

2. エンコードするグラフ集合の選択の仕方(ローカルでの事前計算パート)

解答の作り方からして、上で定義した距離ができるだけ離れるようなグラフの集合を作れればよさそうです。 どうやればそのようなグラフを選べるかわからなかったので、ヒューリスティックに選択することにしました。

(M, N, ε)ごとに選択するグラフの集合を以下のようにして決めました(ただしεについてはソースコードの容量の問題でεの大小でしか(0.3以上,未満)分けていません)。

(1)下図のようなグラフの作り方のルールを合計17種類用意して、グラフにエッジを詰めていきました*6:

グラフのエッジの詰め方のルール(合計17種類)

(2)エッジの本数の範囲は0~(N(N-1))/2本なので、これをM-1で割って等間隔にエッジ本数を選んで、各ルールごとにM個のグラフを候補として挙げました。つまりM*17種類のグラフを列挙することになります。

(3)この中からM種類のグラフを選択すれば良いのですが、焼きなまし法で選択しました。この焼きなましパートの概要や考え方は以下のような感じです:

  • グラフ間の距離は前節で定義した次数列の距離を使用します
  • 状態としてはM種類のグラフのリストを保持して、近傍としてはグラフの交換を使用しました(ランダムに使用するグラフをリストから外して、使用していないグラフからリストに入れる)。とてもシンプルですね。
  • 評価関数は選択されているグラフ間の距離を昇順にソートして(d_0, d_1, ....)として、
\displaystyle \sum_{k=0} d_k \times 0.9^k

として、これをスコアとして最大化しました。これは以下のような気持ちで決めました:

  • グラフの誤識別を起こしやすいのは距離が近いグラフ同士
  • 誤識別をなくすためにできるだけグラフ間の最小距離を大きくした方が良いが良い
  • かといって距離の最小値をスコアにしてしまうとスコアが状態空間に対して平坦になってしまう
  • 距離が小さい順にソートして重みをつければいいか
  • 問題のスコアっぽい感じになってちょっと面白い

これを焼いて各(M, N)・(εの大小)ごとに使用するグラフのIDを決めました。 これをソースコードに埋め込んで問題を解く際に使用しました。

2-1 Nの間引きとグラフのID列の圧縮: ソースコードのサイズを減らす

ここで一つ思わぬ壁が立ちはだかりました*7。 N, Mはそれぞれ100個ずつくらい候補があり、ID列はMの長さがあるので、大体 100 * 100 * 50 =5 * 105 くらいの数値を配列として埋め込まなければいけません。 ソースコードの提出制限が512 KiB = 512 \times 1024 byte ~ 5* 105 byteなので、半角文字は1文字1byteとしてどう考えてもソースコードに入りません。 IDは最大で3桁くらいになり、配列のカンマなども入れなければいけないので512KiBは大変厳しいソースコード長の制限と言えます*8。

というわけで以下の対応をとることにしました:

Nを間引いて埋め込むID列の情報を減らす

  • 具体的には以下のようにしました。Nが小さい方がNのサイズの変化がスコアに効いてくるので、できるだけNが小さい領域で細かく区切りました。
    • N<15の時: 全部のNを使用
    • 15<= N <= 50: 偶数のNだけを使用
    • 50 < N: 4の倍数のNだけを使用

数値の列を文字列にエンコード

グラフのIDの列は普通に書くと

{{{3, 16, 20, 26, 43, 50, 69, 79, 80, 99}, {2, 4, 11, 20, 27, 29, 73, 88, 91, 98, 120},...

こんな感じになります。一つの数値に対して桁数+カンマがあって3文字くらい使ってしまっていますね。 これだと容量が勿体無いので、以下のようなルールで圧縮しました:

  • IDを昇順にソートしておく
  • ID列の差分を計算する
  • 差分の数値をasciiコードにエンコードする (http://www3.nit.ac.jp/~tamura/ex2/ascii.html)
    • 具体的にはasciiコードの一部の文字を使っていて、40~90と97~122を使いました
    • これだと合計77種類しかなく、ID列の差分がこれを超えたときにはエンコードできなくなります。このような時の対策として、asciiコード127の文字(~)を使って、"~" + "数値の桁数" + "数値" という形でエンコードしました。
  • エンコードしたasciiコードを全部くっつけて文字列にしました

例えば

{0, 5, 30, 122, 125, 133, 166}

というID列があったときに、まずこれらの差分を取ります(先頭の数値はそのまま):

{0, 5, 25, 92, 3, 8, 33}

次にasciiコード表と照らし合わせて対応する文字に変換するのと特殊なルールに対応する

{'(', ',', '@', '~292', '*', '/', 'H'}

最後にこれを文字列として結合します:

"(,@~292*/H"

どうでしょうか? 結構コンパクトになりましたね。実際には特殊ルールに引っかかるのはあまり多くないので、もうちょっと圧縮度が上がる気がします。

ソースコードに埋め込んだ文字列は以下のような感じでした。ひどい見た目ですね笑。

このように圧縮したID列をεの大小で分けて貼り付けて、最終的な提出は518,355byteでした。 提出制限が512KiB(キビバイト)なのでぎりぎりですね。

3. (M, ε)ごとにNを事前計算しておく

(M, ε)に対して、最適なNは一意に決めることができます。 M, εに対して全てのNで一万回シミュレーションをして、スコアがもっともよいNを選択するようにしました。 この際にNの候補は前節での事情から、全てのNではなく間引かれたものになっています。 これもリストとして持っておいて、ソースコードに埋め込んで、使用するNを決めるようにしました。

最後に

結構シンプルな解法だったのですが、各所に小技を効かせるのと事前計算による力押しで結構良い順位が取れました*9。 過去最高順位で、オンサイトの本戦に出場できそうです(登録ミスっていないか3度くらい確認しました)。

ただ、この記事を書いていても細部が詰めきれていなかったり、何でこっちの方が良いんだろうと思うところが各所にあって、もう少し取り組みたい気持ちもあります。暇なときに考えてみようと思います。

上位陣でメジャーだったの(多分)はクリークによるノイズ対策+グラフの同型判定で、こちらは筋が良さそう。 クリークの判定難しそうだなあと思って僕は早い段階でこの方法を捨ててしまったのですが、もうちょっと考えた方がよかったかもしれません。 結構焼きなましに使える時間が限られているので大変かと思っていたのですが、焼ける人は焼けるんだなあと思って感心しました。 writerのwataさんの解説が参考になります。

今回のコンテストもとても楽しかったです。主催していただいたフューチャー株式会社さんとtsukammoさん・visualizerの用意に関わったフューチャー社の有志の方、ありがとうございました！ 次はHTTF本戦ですね。次回も対戦よろしくお願いいたします。

*1:競プロを始めたのがコロナ禍以降の2020年だったので、初のオンサイトコンテスト出場です。めちゃくちゃ嬉しい。

*2:多分次数列といったときにはソートされているとは限らないと思いますが、このブログの文脈ではソートされたものということにしておいてください

*3:嬉しい

*4:解答時の順番としてはエンコードをするグラフの集合を決定する -> 解答なのですが、どのようなグラフにエンコードすればいいかは解答の作り方によって決まるので、先にこちらを書こうと思います

*5:2.60117はoptunaの託宣です。2にしたくなる気もしますが、2にする理由はおそらく特にはないはずなので、optunaで一番スコアが良くなるものを選びました。この次数列の分布の各位置の値が正規分布に従うなら2にすればよさそうなのではありますが、多分そうではない気がする? 実はここのところちゃんと調べていないので、距離の定義を詰めたら良くなる可能性がありそうな気がします

*6:グラフの選び方ミスってて草ですね。また、グラフの種類が増えれば増えるほど良いかと思ったのですが、必ずしもそうではありませんでした。焼きなましのスコアは改善するのですが、問題のスコア自体は改善しないということが起きていました。焼きなましのスコアと問題自体のスコアはある程度相関が良いようですが、あんまり焼きなましのスコアにこだわっても良くなさそうでした。あと時間が足りなくてどのグラフが重要だったかなどは詰めきれていないです。この辺りもうちょっとやってもよかったかと思いますが、他の人の方が伸び代多そうなので1週間で終わってラッキーだったと思っています。

*7:正確にいうと全ての(M, N)の組み合わせを使うわけではないので、一部サボってもっと短くできるはず。例えばεが小さいときにM=10, N=100というような選択はされない。M, εに対してNを決めた後に範囲を絞る作業ができればよかったのですが、時間がなくて間に合いませんでした。

*8:いや、そんなことはないんですが、埋め込みを考え出すと意外と大変

*9:クラウド費用さん...