こんにちは B2 の noya2 です。競技プログラミングをしています。AHCのレーティングは　1357 です。

これは 2023-12-01(金) 19:00 ~ 2023-12-10(日) 19:00 の期間に行われた HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027 の参加記です。終了直後に書き殴ったものですが、読んでいただけると嬉しいです。

長期のヒューリスティックコンテストとしては初めて本格的に参戦させていただきました。自分はもともとヒューリスティックにはあまり興味がなく、ずっとアルゴばかりやっていたのですが、先日の短期のヒューリスティックコンテスト(AHC026) でヒューリスティックでもアルゴリズムの面白さを感じられそうだとわかったので、期末試験もちょうど終わって時間が取れそうだったのもあり、1 週間のコンテスト期間ですが腰を据えて計画的に取り組むことにしました。

序盤

その文脈での方言だと思うのですが、最適化の掟のひとつに「最適化するな」というものがあります。この真意はおそらく、最適化する前にできることが山ほどあること、最適化はときにその本質を覆い隠しコードを冗長化・複雑化してしまうことに十分注意せよ、ということだと思います。この教訓？を活かし、今回は「実装するな」というコンセプトで序盤に挑みます。

初日は期末試験の疲れもあり何も取り組みませんでした。月曜日が休みなので焦ることなく土日から始めていきます。

自分の薄いヒューリスティックコンテストの立ち回りの経験から、実装が破滅しがちという反省を活かし、土日はしっかりと考察に時間を当てました。

まず、最終的に何をすることになりそうかを考えると、マスの列としてある経路を取り、それを山登りまたは焼きなましで改善していく未来が見えます。それを見据え、まずはスコアの構造を調べます。マスの汚れやすさを $d$ とし、周期 $L$ のうち $c$ 回そのマスを訪れることにすれば、できるだけ等間隔で訪れたほうがよく、そのときのスコアへの寄与は $dc(L/c{)}^2/L$ であり、問題文の通り汚れやすさに比例して訪れる回数を増やすのが良さそうです。さらに、できれば等間隔で訪れるのがいいことから、

汚れやすい場所を巡回しながら、ときどき寄り道をして汚れにくい場所にも出張して掃除しにいく

という経路を選ぶのが良さそうに見えます。

次に、テストケースの生成方法に目を向けます。今回はそこまで難しいことは書かれておらず、次のことが読み取れました。

• 壁は多くないが、一つが長いことがある
• 壁が極端に少ないこともある
• 汚れやすさは近い場所に固まっている（近さは、壁も考慮した場合のもの）
• 汚れやすい場所は他の $10\sim 100$ 倍も汚れやすい

壁に関する条件と直感から、グリッドをいくつかの壁が中にないブロックに分割して、スケールを小さくした問題を解くのが良さそう、と思いました。

必ずすべてのマスを訪れないといけないですが、アルゴリズム的にそれを達成するのは $40\times 40$ のスケールと壁ありという条件では筋が悪そうと判断したのは悪くない（はず）です。

汚れやすさの条件から訪れる回数は極端に多くしないといけないことがあって困るとも思い、ブロックに分割した後にブロックの汚れやすさを指標に「ブロックの経路」を改善していくことを第一ステップにして良さそうです。

「マスの経路」を改善するときのために、何をすることになりそうかも計画を立てておきます。全てのマスを訪れるという条件のもとで経路に局所的な変更を加えて行くことになりそうです。

• 1 マス余計に進んですぐ戻る
• すぐ戻る場所を消す
• 2 マス寄り道する
• 2 マス寄り道している場所を消す

あたりが考えられます。ざっくりとしていますが、先が見えてきたので実装方針を煮詰めながら時間を過ごします。このあたりで 初期解はかなり丁寧に作った方が良さそう と思い始め、実装地獄を覚悟します。（これは正しかったようで、頑張った甲斐がありました。）

ここまでで土日を使いました。ブロックへの分割だけは実験して性質をみたかったのでコードを書きました。壁のない領域を全列挙し、大きさの大きい順に貪欲に採用しながら分割すると大体 $100$ 個以下におさまりそうなことがわかりました。スケールがかなり小さくなったので、今後に期待が持てます。

D 論コンテストや Universal Cup 、ABC にも出てアルゴの方で既に疲労困憊ですが、空き時間はヒューリスティックに充てていました。

中盤

月曜日です。期末試験期間中ですが自分は既に全ての強化を終えたので、この日はすべてを費やして HTTF をやります。まだ提出すらしていないので SNS での参加表明ができていないことが残念ですが、とりあえず提出まで行くことを目指します。

「マスの列の改善」パートへのバトン渡しとして、マスの列の初期解を作ることが目標です。ブロックの列を「適当に」取り、改善を施し、それを「適当に」マスの列に変換します。

まずはブロックの列を用意し ... と思っていた矢先、ブロックサイズがあまりにも違いすぎると、後々の局所的な変更では対応しきれない大胆な変更が実は必要だったということで困りそうだと気づきます。そこで、大きなブロックが取れたとしても、大体 $812$ くらいのサイズに統一しようと思いました。この数字はかなり意図的です。ということでここから少しアルゴリズムです。

さまざまなサイズの矩形があります。これを同じくらいの大きさのサイズに分割してください。

という問題設定で挑みます。「同じくらい」という条件が完全にアルゴとは言いがたい側面です。まずは、矩形を一刀両断することを繰り返す方針に決めます。一方の幅が小さいときはすべて手作業で実装すればいいのですが、 $40$ 通りもやるのは骨が折れるのでいい案を探します。ここでフロベニウスの硬貨交換問題に着想を得て、ある程度幅が大きければ $3,4$ の幅のブロックに分割すれば大きいブロックについては大きさが $916$ に収まります。さらにこの過程でできる $4\times 4$ の部分は $2\times 4$ を $2$ つに分割すれば $812$ に収まって、かなり良さがあります。これを実装したのが namespace splitter の中身です。

こうしてブロックの分割を実装し終えます。かなり地獄です。

小さなブロックに分割したのには理由があって、ブロック内のマスを全て訪れる最適な経路を埋め込むことができるようになります。ここで大変な長さの埋め込みが行われます。地獄 2 です。

次にブロックの列を受け取ってマスの列を出力する関数を作成します。

• ブロック同士が隣り合っているかどうか判定する関数
• ブロック同士の近似的な距離を計算する関数
• ブロック内の 2 マスを指定したら、そのマスを端点に持ちブロック内の全てのマスを訪れるパスを構築する関数
• ブロック内の 2 マスを指定したら、そのマスを結ぶ最短パスを構築する関数

などを実装し、組み合わせてなんとか実現します。

ブロックに分割してスケールを小さくしたことで、 $2$ マスの近似的な距離ができるようになったのは旨味です。（ $1600\times 1600$ のテーブルを作るのが怖かった。）

ここまでで $10$ 時間くらい、 $800$ 行程度実装しました。本当に地獄です。

最後に提出に漕ぎ着けるために、すべてのブロックを本当に順番に訪れるだけのコードを書いて、見事 AC を得ます。 $1713554581$ 点（小さいほうがスコアが良い）ですが $33$ ms で、かなり高速に動いてくれています。いい感じです。

さて、またまたアルゴリズムの出番です。ブロックを $18$ 個程度選んできたときにどの順で巡れば効率的かどうかが分かれば、ブロックの列の初期解に大きく寄与しそうです。これを達成するには ... ? そう、これは巡回セールスマン問題なので bitDP で解くことができます。ブロックが $K$ 個あったとして $O(K^2{2}^K)$ 程度でこの問題を解くことで、局所的に最適なブロックの列を計算できます。ブロックは合計で $150$ 個程度あるのですが、これをざっくりとした位置で $20$ 分割し、内部でこの問題と解いて繋ぎ合わせることでブロックの列の初期解を得ます。

ここで終わらず適当な山登りで時間をいっぱい使ってみるコードを書き $1221871409$ まで改善して月曜日は終わりです。HTTF参加してますツイートもしました。楽しい楽しい。

結局この日で $12$ 時間くらい費やし、 $1000$ 行程度実装しました。本当に疲れましたが、かなり没頭してしまっているのが伝われば、と思います。

火曜日から通常授業なので避ける時間は減りますが、なんと水曜日と木曜日が全休なので、まだまだ時間は十分にあります。

水曜日はマスの列の方の改善を頑張りました。スコアとしては本当に素直に $O(N^2+L)$ で毎回計算するものを採用しました。この部分に手を入れる余地はあったのですが、とりあえず置いておきます。

近傍として上述したものを実装し、かなりスコアが改善しました ( $881687191$ )。が、まだまだ上を目指したいところです。実験しては観察して、というのが主な改善方法だったのですが、このあたりでちゃんと $50$ ケース程度手元で回してジャッジする仕組みが必要だと思い立ち、シェルスクリプトを用意しました。やはり $30$ 分の提出制限は苦しいので、この判断は良かったです。さらに、局所的とはいえそこそこ大きな変更も必要だろうと思い立ち、長さ $N$ 程度の部分を破壊して適当に繋ぎ直すということを行い、ついに $7$ 億台に突入です ( $795774302$ )。この日は CodeChef のアルゴのコンテストがありました。クリケットのルールが全くわからず、非本質に悩まされました、ぐぬぬ。

木曜以降はかなり苦しかったです。全然スコアが改善せず、思い付いた超良さげな変更を施しても、スコアが悪くなるなんてことはザラです。 ﾂﾗｲﾑ u ___ u

特に、山登り法を焼きなまし法に変更したところ、スコアが目に見えて悪くなり、これはどうしようもなくだめだとなりました。近傍の取り方が悪く、少しの変更でスコアの変動が大きくなりすぎていたのが原因かもしれません。結局最後まで山登り法を信じて改善していました。

ただし、スコアが思うように改善しなくても、終盤まではネチネチしたパラメータ調整はしないと決めていました。少しのスコアの改善はあるかもしれないですが、それよりもはるかに大きな改善の余地を見過ごしたくないですからね。オーダーレベルでの計算量の改善や、ブロックの列の近傍にもいくらか変更を加えるなどして、ジリジリとスコアを改善していきました ( $777201868$ )。

ここまでで木曜日が終了です。ライブラリの展開まで含めるとコードが $2000$ 行程度になってしまい、破滅こそしていないですが、魑魅魍魎待ったなしです。

終盤

それらしい改善をいくつか施しましたが劇的な改善は起こらず、順位表の $40\sim 50$ 位あたりをうろうろしていました。最後の最後はパラメータをいくつかいじって実験を繰り返しては提出を行うなどしましたが、あまり改善はありませんでした。それよりかは、たとえばブロックの列の改善を施す前の初期解のランダム性を一部除いて、ブロックの位置で偏角ソートした結果をそのまま利用するなどした方がいい、という考察を反映した改善の方が目に見えてスコアが改善するというものです。やはりパラメータ調整は本当に本当に最後に行うことかもしれません。パラメータ調整の掟「パラメータ調整するな」かもです。

結局大胆な実装をすることもなく、アルゴも恋しくなってきたこともあり、それほど時間を割くことはしませんでした。それでも、順位表を見て順位が下がっていることが悔しくてつい手をつけてしまうものです。最後の方はあちらこちらに転がっているパラメータたちをガチャガチャしているだけでしたが、なんやかんや月曜から毎日提出してしまいました。本当に楽しかったです。

コンテスト終了時点の暫定順位は $61$ 位で、悪くないです。あれ、 $61$ ？... そうです、大勢の参加者が土日でラストスパートをかけ、ここまで順位が下がってしまいました。最終スコアは $750456904$ です。

感想

上位勢を見ていると、 deque を使ったスコアの差分計算や焼きなまし法を使った経路の改善などを見かけ、そんなことできるんだ...すごい...となっていました。ヒューリスティック楽しいですね、アルゴリズムと同じくらい楽しいです。ここまで没頭できたのは、そこそこ計画的に挑んだのと、多少アルゴができたことが大きかったと思います。実装しているとき、はたまたデバッグしているときは本当に辛いですが、頭の中で考察していい案が湧いてくるのは本当に楽しいです。一週間という長い期間でしたが、かなりたくさん遊ばさせていただきました。ありがとうございます。

システムテストで最終的な順位が決まるのですが、どうやらプレテストには入っていない「本当に本当に汚れやすいオフィス」も紛れているようです。楽しみですね！

さいごに

\\ ( . ________ .) ﾋｭ~