2022年8月9日～16日に開催された「RECRUIT 日本橋ハーフマラソン 2022夏（AHC013）」に参加して9,093,373点で136位でした。
前半は準備不足でなかなかスタートできなかったり、中盤は実装が膨れて＆バグが頻発して生産性が落ちたり、最終日前日にメモリバグで地獄を見たりと大変なことも多々ありました。
ただ、途中で方針を見直してプログラムが期待通りの動きをしてくれてスコアも目標にしていたラインを越えることができたので振り返ってみると楽しい1週間でした。
この記事では提出解法について簡単に説明し、参加していた時に考えたこと／試していたことを時系列で振り返ろうと思います。
コンテスト／問題概要
[math]N \times N[/math]のマスに部屋に[math]K\ (2\leq K \leq 5)[/math]種類のコンピュータが100台ずつ置かれている。移動と接続を最大[math]100K[/math]回まで行いサーバ同士をつないだクラスタを作る。
クラスタごとの得点が
「同じ種類のコンピュータの組合せ」-「異なる種類のコンピュータの組合せ」
で与えられるので合計得点が高くなる配置＆接続を見つけてください。
要はできるだけ同じ種類のコンピュータで構成された大きなクラスタを作ってくださいという問題になります。移動＋接続が最大[math]100K[/math]回という制限が厳しく[1]100台のコンピュータを連結するのに99回接続がいるのでランダム配置から全種類をつなぐのはほぼ不可能です。制約を踏まえて目標をどこに設定したのかで明暗が分かれたのではと思います。
提出解法
スコアの決め方から同じコンピュータ数の二乗に比例してスコアが伸びるので
多少、別種のコンピュータを含めてでも同種のコンピュータで大きなクラスタを作る
ことを目標にしました。
大きく3つのステップで作っていて
- 同種のコンピュータのみで構成したクラスタを別種のコンピュータを経由してつないでクラスタを大きくする
- ルールベースでクラスタ内の別種のコンピュータをどかしたり、コンピュータと入れ替えたりして改善
- 最後にBeam searchでルールでは対応できないような改善を探索
としました。ステップ1, 2はコンピュータの種類を決め打って実行する…を[math]K[/math]種類分回してその中で一番良かったものをBeam searchしました。
Step.1 連結成分を作る
種類を決め打って(例. 種類1を大きくする)
- DFSで同一種類のコンピュータだけで構成できるクラスタを求める。この時にクラスタから接続できる別種のコンピュータも求めておく
- クラスタと別種のコンピュータの二部グラフができるので連結成分数が大きくなるようにクラスタを貪欲に大きくする
としました。この時点で大きさ60-80くらいのクラスタを作ることができていました。
Step.2 ルールベースで改善
ここでは大きく2つのことをしています。
- クラスタに含まれる別種のコンピュータを除く
- クラスタに同種のコンピュータを移動する
まず、別種のコンピュータで辺が一直線になっているものは除いても連結性を保てるので外側に移動させます。他にも
- 近くに同種のコンピュータがあれば別種コンピュータを外側にどかして入れ替え
- 近くに同一連結成分内で次数1のコンピュータがあれば入れ替え
同種のコンピュータの移動はクラスタから連結できる場所に移動させれば十分ですが、実装が間に合わず単純にクラスタ内へ移動させました。
Step.2の段階で[math]N[/math]が中～大の問題では
- 決め打った種類はほぼすべてつなげて、別種のコンピュータが2-3個残る
- 残った手数で他の種類の小中規模のクラスタが2-3個できる
という状況になることができました。
一方、[math]N[/math]が小さい問題では中小規模のクラスタを複数作るのが精一杯でスコアを伸ばすことができませんでした[2] … Continue reading。
Step.3 Beam search
Beam searchでは各コンピュータを移動させたときに
- 同種のコンピュータ間で接続ができる
- 別種のコンピュータの連結成分に入っている時に外側に移動する
ものを評価するようにしました。
実は方針を見直した際に捨てる予定でしたが、Step. 2のルールベースの後にBeam searchをつなげると改善したので最終提出に含めることにしました。
時系列での振り返り
ここからは当時のメモを中心に振り返ります。文体がですます調じゃないなど統一感が無い点は予めご了承ください。
8/9(初日)
AHCは普段使っているPCと別のPCを使っているのですがケーブル類が見つからず何もできないところからスタートでした。
AHC用マシンの電源ケーブルとLANケーブルを引っ越しの時に捨てたっぽいので調達するところからスタート。 pic.twitter.com/pqTI6bWWBe
— starpentagon (@stat_learning) August 9, 2022
さらに久々に起動したらVSCodeからつなげない…。どうも家庭内では通信ができるけどInternetと通信できていない。ネットワークの設定を調べたりしているうちにAHC013がスタート。PC、ルータを再起動したらようやくつながった。
久々の出社日で疲れたのもあって問題を理解したところで就寝。
8/10
自分の理解もかねてテストセットを作るプログラムを作成。理解が深まる面もあるけど、終わった後に他の人と会話がかみ合わない[3]終わった後に「seed=7の問題が～」といった発言が飛び交うので次回からは公式の問題生成ツールを使うのでも良いかも。
この日は飲み会に誘ってもらったので移動中に「グリッドだしドミノ敷き詰めみたいなDP使えないかな…」と夢想したけど難しそうということだけ分かって終了。
8/11
金曜を休みにしたので今日から5連休。ただ、二日酔いでしんどい。頭が動き出したのは夕方。で、何をしたかというとスケジュールを作ること。
前回、AHC011に参加した時（参加記、日記）はのめり込んで毎日全力を出す！みたいな感じになって疲れたので今回はスケジュールを立てて他の事とのバランスも取って進めることが目標。
移動、接続は分けて考えた方が良いだろうというのと、途中ロジックを見直すことを想定し2周回す前提でスケジュールを立てました。
最終日はロジックの大枠は固めてパラメタ調整や時間調整に使うのが理想だけど果たしてどうなることか。
この日は接続用のロジックを作る前に小さな[math]N[/math]とコンピュータ数(12以下)で全探索した結果を求めていました。
目的は最適な接続を理解することとロジックの答え合わせ用に…と思っていましたが
- 非自明な最適な接続は特になかった
- コンピュータ数=100を前提にしていたコードの修正が発生
のでかけた時間の割には得られたものは少なかったです…。
夜に貪欲に接続するロジックを少し書いて終了。
8/12
さっそく立てたスケジュールから遅延。接続ロジックは貪欲に
- 他のクラスタと辺の交差がない（周りに影響を与えない）クラスタはつなぐ
- 他のクラスタと交差があるものは連結後に大きくなるように貪欲につなぐ
- 別種のコンピュータを経由すると大きくなる場合はつなぐ
としました。
この段階で結構バグらせて時間がかかって日付が変わるころに手元の2,000問、10,000問をエラーなく完走！seed=0のサンプルも
それっぽくつなげている！
よしよしということで初提出。暫定テストは44K点でトップは328Kまで行っていてて1桁の違いが出ている。移動を含めてどこまでスコアを伸ばせるか…。
8/13
移動パートは方針を立てるところで結構迷いました。
- コンピュータの密度が小さい場合は全域木を決め打って[4]終了後のTweetを見ているとこの方針の人もいてて渦巻き型や王の字型にしていたようですそこに移動させるのがよいのでは？
- コンピュータの密度が高い場合は空白をうまく動かすのが必要で良い移動を定義しにくいので焼きなまし法か
- 中間くらいの密度ならBeam searchで貪欲＋αで見ていくのがよさそう
と[math]N, K[/math]によって難しさが違って取るべきアプローチも複数ありえそうでした。
最初のロジックは操作回数の制限が厳しく無駄な移動をして接続できないとダメだと思いBeam searchで貪欲チックに改善することにしました。
最初の実装がまずく非常に重い実装になってしまって(ビーム幅1でも20秒くらいかかった)、プロファイルをとってボトルネックを探したり実行時にtopコマンドを眺めているとメモリを大量に使っていることを発見。10GBくらい使っていててなんでだ？というのと恐らくそれが遅い原因だろうというのを目星を付けたところで終了。
8/14
メモリを大量に使っているのをヒントに見直したら単純に設計ミス（無駄に状態を覚えていた）
ビーム幅1だと間に合うようになって平均スコア2,300くらいまで伸びた。これを提出。108K(平均2,170)になって平均スコアにちょっとギャップあり。暫定テスト、ひょっとして偏ってる？
ボトルネックになっている処理がBeam searchで「孤立しているコンピュータを同種の連結成分に近づける」というのがどうも重い＆バグっているようで外すと速くなってスコアも伸びた。
おかげでビーム幅をようやく2にできてこれで148K(平均スコア2,980)まで伸びた。
この段階で移動＆接続を一回しできて改めて方針検討。このままだとスコアが伸びる余地もなさそうで上位陣ともかなり差があるので方針から見直した方がよさそう。毎回100個つなぎ切れれば4,950点で暫定テストだと247K相当だけどすべてのケースで100個つなぐのは厳しそうなので200K越えを目標にしました。
夜につらつら考えていたら
これはたくさん接続するゲームじゃなくて１つでもいいから大きな木を作るゲームだ！
というのに気づいてとにかく大きな木を作る方針に転換。
今のロジックだとどの種類も平等に大きくしていこうとするので中途半端な大きさのクラスタが複数できてスコアが伸びない…ということなんだと理解。
スケジュールは依然1日遅れだけど最悪16日はバッファなのでギリギリなんとかなるかな…でも明日から平日だしな…と不安に思いつつ終了。
8/15
接続パートはとにかく連結成分を大きくするようにロジック書き直し。
非常に実装が大変で途中２回設計＆実装をやり直して無限に続くかと思われたデバッグが終わったのが日付が変わる直前。
とりあえずBeam searchと組み合わせるとseed=1の問題で100個つなぐことに成功！
左上に輝くScore=4950。この方針で間違ってなかったと実感。いやー、うれしい。
手元のテストだと平均スコアが3,600で1種類しかつなげていないけどすでに前のロジックのスコアを越えた。ルールベースでさらに改善もできそうで、Beam searchと比べて高速なのでK通り試して一番良いやつを採用といったこともできそう。
日付変わったけど俄然やる気が出てきて移動パートへ。
連結成分の情報を管理しルールベースで最短路問題解いて移動させるだけ…のはずが、
と見たことないエラーが。
ん？？なんだこれ？と原因も分からないし再現性もなく、エラー起こる場所すら毎回違う…という非常にタチの悪いエラー。しかも別のエラーもたまにでてカオスなことに。
結論としては
- 連結成分の情報をmapで管理していてて値をmap.find(x)->second と返していた[5]Getterはconst関数で書くことにしていてて、[]演算子はconstでないのでfindを使っていた。。xがない時にend iteratorが返ってそれを参照してバグる
- 最短路を求めるときのテーブルに範囲外アクセスをしていた
という2つのバグを同時に踏んでいました。
処理自体は接続パートのヘビーさに比べればかわいいもので、なんでこんなにバグるの！？え？なんで？？なんか悪いことした？と深夜に一人地獄を味わっていました。
結局、原因が分かって直せたのは朝方でした。この日は天国と地獄を両方味わった一日でした。
8/16(最終日)
なんだかんだで最終日。この日は念のため午後休を取ることにしていたので午後からスタート。
移動パートはまだ終わっていないけど処理の全体が見切れていない「1種類しか接続しない」のを「複数種類つなぐ」ようにしないと後悔しそうなのでまずそちらを実装。が、あまりスコアは伸びず。やはりいかに大きな木を作るかが勝負になっているようだ。
ここからは移動パートの実装。昨日のバグ地獄とは打って変わって順調に実装。一通りアイディア実装して提出すると198K(平均3,962)まで伸びた！ルールベースを2回回すとさらにぐっと伸びて213K(平均4,274)まで行ってついに目標ラインを越えた！
最後に計算時間に余裕があったので、Beam searchの後半は連結成分の最大化ではなくスコア最大化するように変更したらスコアは伸びたけど時間がきわどい感じに。悩んだものの時間管理を入れる余裕はなくて間に合うと信じて最終提出しました。
終わった後、ヘロヘロでしたがTwitterを眺めたり、かえでさんが開いていたスペースを聴いたりして過ごしました。トップ層との違いは
同種のコンピュータで全部つなぎ切る
ことを目標にしていたかに尽きると思います。参加していた時は同種のコンピュータでつなぎ切るのは難しいのでは？と思っていてて別種のコンピュータが残るのは仕方ない…と思っていたので、そこの部分でスコアの伸びが弱かったのだと思います。
トップのbowwowforeachさんは「同種のコンピュータの全域木を2つ作る」を目標にアルゴリズム設計をしたとTweetしていてて、目標の高さとともにそれを設計＆実装しきれるのはすごいと思います。
あと、１つ残念だったのはシステムテストで懸案だった計算時間オーバーが6個あったことです。最後の最後で欲を出してもったいないことをしてしまったと反省です。
とはいえ、途中で方針を見直してプログラムが期待通りの動きをしてくれた時は感動しましたしスコアも目標にしていたラインを越えることができたので結果には満足です。スケジュールも初っ端から遅延しましたが最終日前日を除くとほぼ計画通り過ごせたのかなと思います。
来月にも長期コンテストがあるようなのでまた参加してみようと思います。
