これは何？
AHC008の日記です。コンテスト中に書いていたものをそのまま貼り付けただけなので全くまとまっていません。まともな解説記事はリンク先を参照してください。
暫定順位の推移はこんな感じです。日記と併せてどうぞ。
2/12（土）
問題を読む。むっず。これは確かに2週間が妥当。
とりあえず最小カットとマッチングで仕切りを置いていく。258M。動きがぐちゃぐちゃで自分を閉じ込めてしまう。動物に支配される人間。
脳死マッチングはダメそうなので格子状に分割してみる。何も考えず全体を3x3分割したら387M出て草。格子に穴を空けておいて1つずつ閉じ込めていくのはアリかも。1Gくらいは取れそうな気がする。明日試してみる。
一日目終了時点でトップが887M。どこまで行くか正直見通せない。最終日には4G～5Gくらいの争いになっててもおかしくない？
2/13（日）
ずっと空戦AIをやってた。
4G～5Gって昨日言ったばかりなのにもう4G出てて草。いやはや見積が甘い……。
2/14（月）
格子状にするやつ、どちらが「外」か判断するのが難しいのと、犬の処理が難しいのとで微妙かも。
スリット状にすれば良いのではないか？横向きにスリットを作って人は縦向きに動くようにし、動物が来たらフタをする。かなり良さそう。
何も考えずやるとターン数が足りない。真面目にやらないとダメ。とりあえず今日はここまで。
全然ダメだと思っていたが、記念に提出してみると1.8Gで19位になった。方針は間違ってなさそう。あとはいかに効率良くやるか。ちゃんと詰めてみる。
しかし一見賢い貪欲を作るパズルゲーかと思いきや、考察を進めていくとTSP+αっぽい問題になってくるの本当に凄いなあ。こんな作問できる気がしない。
2/15（火）
今日は考察デー。
- スリットをスタッフに割り振るパート
- スタッフを定位置の列に移動させるパート
- ペットを捕まえるパート
の3つに分けて考察した。今ボトルネックになっているのは必要ターン数なので、とりあえず必要ターン数の最小化を試みる。ターン数が短くなれば戦略の幅も広がるはず。
スリットをスタッフに割り振るパート
最大値を最小化するタイプの配送計画問題だが、別に大真面目に配送計画問題を解く必要はなさそう。
仕切りを置く経路としてヘビ型のものを考えて決め打つと、DPができる。DP[i][bit]:=ヘビ型の経路のiマス目まで見て、経路が確定したスタッフの集合がbitであるときの最大ターン数の最小値 と定義。計算量はヘビの経路長をKとしてO(MK2 2M)とかでちょっと怪しい感じはするが、無駄な遷移（さすがに1人に9割を担当させるのは明らかに無駄）を省けばさすがに間に合う気はする。もし問題になったらまた考える。
次のスタッフを定位置に移動させるパートもまとめて解けたら良いが計算量的に間に合わないのと、どうせペットに邪魔されてブレるので次のパートで吸収することにする。
スタッフを定位置の列に移動させるパート
これも最大値の最小化問題。スタッフと列をマッチングさせる。実は蟻本のp.206にほぼ答えが書いてあって、かかるターン数を1ターンずつ増やしてグラフの辺を追加しながらフローを流せばよい。計算量は謎だけどまあ余裕だろう。
ペットを捕まえるパート
未来のことはかなり信用ならないので、とりあえず貪欲的に解く。捕まえるのに必要なターン数は縦方向のチェビシェフ距離+1となる。同時に動かせるスタッフが1組だけならただの貪欲で良いが、複数並行して捕まえに行くことが可能なので難しい。各小部屋の扉を閉じたときのスコアの増加量をΔS、それにかかるターン数をTとして、各小部屋の基礎スコアをS'=ΔS/T2とする。このとき、スタッフを頂点とし、頂点iと頂点jの間に重みS'の辺を張り、一般最大重みマッチング問題を解けばよさそう。
一般最大重みマッチング問題は解いたことがないが、解き方は色々ありそうで、
- エドモンズ法
- 線形計画・整数計画
- 枝刈りDFS
- 焼きなまし
あたりが候補。エドモンズ法は実装が死ぬほど大変そうなので却下。どうせ定数倍もよくなさそう。線形計画も実装が不可能。焼きなましで焼けるのは焼けそうだが、毎ターンこれをやったとき近似解がブレブレになっちゃうとスタッフが右往左往するハメになるので、S'の降順にソートして枝刈りDFSで厳密解を求めに行くのが最有力。動物は高々20匹なので小部屋も20個見れば十分で、ワーストケースを超雑に見積もっても1ターンあたりO(2N)なのでまあ大丈夫。実際はずっと速いはず。
枝刈りDFSを思い付いたのはchokudaiさんのツイートのおかげ。これがなかったら多分焼いてたと思う。ありがとう……。
2/16（水）
O(2N)は嘘で、これにM2がかかる。けどまあ大丈夫でしょ。
ゴリゴリ実装する。仕事終わってからずっとAHCやってる異常生活。いつまで身体が持つのだろうか……。
手元1000ケースで計測。何もしなかったときの得点率が16.6%、ヘビDPを実装すると28.2%、定位置移動のマッチングを実装すると28.7%、捕まえるときに最大マッチングを使うと30.8%になった。うーんこれだけか？40%はさすがに乗ると思っていたのだけれど。
捕まえるときに仕事しないスタッフがぼーっとしているのは明らかに無駄なので、一番近い動物と縦軸を合わせることにした。32.4%。
スタッフの人数によってスリットの列数を変えるようにした。37.4%。だんだん上がってきた。
1行目にスリットを置くのは無駄なので空けることにした。40.0%。ようやく4割に乗った。
よく考えると角の部分は不要なので消した。43.9%。いいぞいいぞ。
提出すると4.30Gで暫定9位。ちなみに実行時間は1,017msで、やっぱりDPがボトルネックになってそう。*1 とりあえず今日の目標は達成したけど、一位は5.3Gだからここからさらに10%上げないといけない。無理では？ともかく明日ビジュアライザを見ながら考察しよう。
我慢できずにもうビジュアライザを見てしまった。明らかにもう少しで捕まえられそうなのに動物が邪魔でフタができない場合、捕獲候補から外して別の場所に向かっているのがかなりもったいない。そういうときは我慢して待機してもらうことにする。これを実装すると53.4%。めちゃくちゃ良くないか？？？提出すると5.327Gで暫定2位！ハチャメチャにはしゃいでる。1位のymatsuxさんは5.335Gなのでもう目と鼻の先。
せっかくなのでパラメータをいじって1位を取っておいた。記念というだけであまり意味はないけどモチベは上がる。
あと1週間以上あるんだよな……。どうやって逃げ切るか。
2/17（木）
ウサギとかはさっさと捕まえたい感じがする。
暫定1位取ったしとりあえずコーディングはお休み。代わりにToDoキューを作ってアイデアを放り込んでいくことにする。とりあえず、
- 手ぶらなスタッフと動物のマッチング（今は近い動物を貪欲に選んでいるので複数人が群がっていて無駄が多い）
- 定位置ポジショニングを待たずに捕まえ始める（待ってる時間が無駄）
- 迂回してるやつを真面目にする（ヘビを作るときの動きをちょっと賢くして2ターン削減）
- 実行時間測定（パフォーマンス改善用）
- 戦法ごとの得点率予測（列をいくつ作るのが良いか予測させる）
を入れた。絶対ここからMM勢とか潜伏勢とかが無限に出てくるので、まだ最終的に10位に残れるかどうかもよく分からない。残り1週間以上あるのでアイデアを絶やしたら死にそう。
2/18（金）
朝起きたらeivourさんに抜かれていた。昨日の夜の段階で一瞬で5G弱まで来ていたから時間の問題だとは思っていたけど、5.56Gかあ。これ本当に6Gくらい行くかもなあ。
抜かれた衝撃でアイデアが生えた。今は(1, 15, 30)列目みたいな感じで通路にしているけど、例えば(5, 15, 25)列目を通路にしても良いのではないか？マッチングは自己ループを作れば無理矢理今のコードでいけそう。改修が重そうなので土日に試してみる。
土日に試すと言ったな、あれは嘘だ。場合分けめんどくさいと感じつつ実装。思惑通り手元1024ケースで56.1%を叩き出した。これを投げると5.76Gで首位奪還。思わずガッツポーズ。かなり上振れてるっぽいけど気にしない。
仮に完璧に捕獲できたときにどのくらいの点になるか見積もる。
xxx)|(xxxx)|(xxxx)|(xxx みたいに割り振るのが良さそうで、これだとざっくり62%くらい。60%くらいを目指してみたいなあ。
浮かれてしまっていたがまだこれコンテスト期間の半分も経ってないんだよな……。マラソンしんどすぎる。
2/19（土）
最大重みマッチングの枝刈りを削除するか迷っている。一人で閉じられる扉を想定していなかったため枝刈りロジックが怪しい。でも消すとスコア下がるんだよな……。多分これがブレーキ役となっており、早々に全部捕まえてしまって時間を持て余す現象を軽減しているものと思われる。もはや枝刈りではないのだが、残すかどうかは要検討。時間の有効活用についても要検討。
開始10000分時点でphocomさんに抜かれた。5.92G。やっぱり6Gくらいの戦いになりそう。こっちはこっちでちょうど配置が遅い人を待たずに捕まえ始めるようにしたやつを実装したので回してみる。手元で57.0%、投げると5.85G。1%改善したけど、手札が減っていくのは怖い。
phocomさんの2分後に提出したから誤解されてそうだけど、本当にできたてほやほやなんです。信じて。
手ぶらなスタッフは貪欲に近いペットを割り当てていたが、これもマッチングで割り振ることにする。手元だとで57.4% (+0.35%)。投げてみたけどこれは伸びない。1ケース取りこぼすだけで大きくスコアが下がるので、いつも以上に順位表は参考値と考えた方が良さそう。
600ターンだとどうなるか試してみた。58.4%らしい。やっぱどういう戦略にするかってところを精度良く決める必要がありそう。
以前から画策していたNNで戦略ごとのスコアを予測させるやつをやってみる。まずデータが集まらないことにはどうしようもないので、収集するやつを作る。通路の数を2, 3, 4個とした3パターンを作って、それらのmaxを各ケースで取ると平均60.5%。これが完璧に予測できれば60%行く可能性はありそう。とはいえ事故るケースもあるので簡単ではない。
ABCが終わったのでCPUをぶん回して100,000ケース分のデータを収集する。終わるのは明日の昼くらいになりそう。
2/20（日）
スタッフの人数が少ないとき、1セルあたりが大きくなってスコアが低下するのをなんとかしたいと昨日から考えていた。途中を行き止まりにしてエの字型にする案を昨日思い付いていたが、犬に弱くなる上そもそも連結性が確保できなくなるので却下していた。が、それなら一部の通路だけエの字にすればよさそう。
手元で回すと58.1%。ここに来て1%弱伸びるのは大きい。投げると5.89G。パラメータ調整がガバいので丁寧にやる。あとコードも殴り書きなのでひどい。あとでリファクタリングする。
NNで予測させるやつを作る。PyTorchは慣れていないので入門記事を読みながら。どういうモデルを作るべきか分からないけど、そんなデカいモデルを作る必要はなさそうだし、だからといって別に小さくしすぎる必要もないので、
- 入力層: dense 7x32 -> ReLU
- 隠れ層1: dense 32x32 -> ReLU
- 隠れ層2: dense 32x32 -> ReLU
- 隠れ層3: dense 32x32 -> ReLU
- 出力層: dense 32x(out) -> Sigmoid
で行くことにする。入力は (スタッフ数, ペット数, 牛, 豚, 兎, 犬, 猫) 、出力は各配置パターンの得点率。だいたい0～1になるように正規化。コード書いて学習させるぞと思ったら一瞬で収束する。なんかバグったか？と思っていたけど、そこそこそれっぽい予測ができてそう。まあ線形結合に毛が生えた程度で表現できそうだし。
これで終わりではなくて、Rustに移植しなければならない。Python側でNNのパラメータを引っ張り出してbase64にエンコードして、それをRustでデコードして行列を復元して順伝播を実装する。もちろんbase64のデコードは手動。全部初めてなので何も分からなくてバグらせまくる。
どうにか完成したので回してみる。58.3%。あまり変わらない。まあ大部分は良い感じのチョイスになっていたということか。これを投げると5.93Gで1位に復帰。とはいえ普段のコンテスト以上にスコアがブレまくるので信用ならないね。
一部のケースでバグっているのを発見。seed=15000が0点になっている。あとでリファクタリングついでに調べる。
スタッフを置く場所は中央から順番に並べていたのを端からにしていたが、再度中央からに戻した。58.8%。めちゃくちゃ上がった。提出するものの逆にスコアは下がった。まあOK。
ペットを捕獲するパートで、各セルの評価値を(捕獲したときの得点の上がり幅)/(チェビシェフ距離+1)2としていたが、2乗を外したら58.9%になった。投げると6.01G。ついに大台に乗って嬉しい。まあこのままだとシステスは60%乗らないんだけど。
チェビシェフ距離、ターン数に余裕があるときは1乗、余裕がないときは2乗がいいのかも。これもコンフィグに入れたい。
2/21（月）
エの字型だけじゃなくてコの字型もアリでは？
今日はリファクタリングと高速化をする。高速化といってもサボってたところをちゃんと書くってレベルだけど。実行時間的に問題があるわけではないが、考察のイテレーションを高速に回したい。あとはTLEのリスクも減らしておきたい。結構苦しかったがなんとか書きあげて、5倍くらいにはなったっぽい。ついでにコの字型をはじめとしてある程度自由にマップを書けるように改修した。
2/22（火）
アイデアが生えた。今は最後まで定位置にポジショニングしているが、残り時間が短くなったら積極的に追いかけても良いのでは？高速化したおかげで、追いかけるべきか定位置で待つべきかはモンテカルロできそう。明日実装かな。アルゴリズムとしてはKターン前にどちらが良いかチェックして、追いかけた方がいいという判断になったらとりあえず近付いて、動物からKマス以内かつ自分の今いるマスより動物側にあるマスに配置、とかで試してみる。
ビジュアライザを観察してみると、だいたい豚か牛が最後まで残ってる。移動回数が少ないと通路を通る試行回数も少なくなるからだろうか。猫もたまに残る。犬は人間に近寄ってきたところでだいたい捕獲されてる。かわいいね。
今のところだいたい捕獲失敗率が6.5%くらいっぽい。これを詰めるのが一番効果が高そう。仮にこれを半分くらい救えたとして、それらの点数が倍になると考えると1.5%くらいの改善が見込める。
同じ方向から近付くのは無駄なので、他の人が近くにいるマスはペナルティをかけてダイクストラすると良さそう。周囲2マスくらいにペナルティをかける感じか。
今日はコーディングはお休み。気付いたら2位が5.95Gまで追い上げてきている。100ケースじゃブレも大きいので0.5%差なんてあってないようなもの。コンテスト期間もあと4日を切ったので、このアイデアでどこまで伸ばせるかが勝負っぽい。
2/23（水）
適当にペットの周囲2～3マスに置くだけだとうまくいかない。序盤に捨てた最小カットを試してみるべきか？
一発じゃうまく行かなくて、丸一日色々試した。マップの通路からペット周囲のマスまでのフローを最小カットする。59.61%。0.6%上がったのはまあまあ大きいが、想定ほどの効果はなかった。提出すると6.03G。やっぱり暫定テストケースはちょっと甘め？当たり前ではあるけどいつも以上に順位表は信頼しない方が良さそう。
捕獲失敗率は6.5%から3.6%まで下がっているので、一定の効果はありそう。あとは捕獲に向かわない方がいいケースがあるということか。以前考えていたように自前シミュレーションでどっちが良いか複数回試して期待値の高い方を選べば点数が伸びる余地はあるかも。
祝日丸一日潰したのでどうなることかと思っていたが、ちゃんと伸びてくれて良かった。さすがにもう費用対効果は最悪だけども。
重みを更新した。59.76%。提出すると6.08G。本質的には何も変わっていないのだけれど、数字が大きくなるとテンション上がるね。
しかし開始から2週間近く経ってもやることが尽きないの本当に凄い問題だなあ。何十時間溶けたか分からない。
2/24（木）
モンテカルロ、動物がどこにいるか予測するのにも使えない？明日試してみる。
まずは確実に点の上昇が見込めそうなセルフジャッジ実装を試みる。公式ジャッジツールから移植。同言語だとこういうとき楽。終盤になったらモンテカルロ法を残り2500msになるまで回して、追いかけるやつと追いかけないやつのどちらか良い方を選ぶようにした。モンテカルロ法の実行数は50回くらい？そんなに多くはないけどまあ十分かな。
回すと59.96%。0.2%だけ？もうちょっと欲しかったな……と思ったけど、よく考えたらモンテカルロ法の発動ターンを最適化していなかった。適当に試したところ275ターン目くらいでモンテカルロするとよさそう。60.30%。ついに手元でも60%の大台に乗った。ここに来て0.54%も上がったのは大きい。昨日のと合わせると1.3%くらいの上昇。捕獲失敗率は4.6%なので半分とまでは行かなかったが、まあまあ見込み通りの成果が得られた。
重みを更新したらなんか0.1%下がった。まあ誤差か。とりあえず戻しておく。
提出すると6.15G。2位のsimanさんに1%のアドバンテージを付けたがまだ気が抜けない。phocomさんとか開始20000分で提出してきそうな気がするし、他にもまだ何人も思い浮かぶ。とりあえずあと1日と18時間必死に逃げ続けるしかない。
2/25（金）
wleiteさんにめちゃくちゃ追い上げられている。6.12G。かなり厳しい。
モンテカルロ法を導入してみる。動いてそうに見えるが、点数は悪化した。不貞寝。
寝たら冷静になった。デバッグをすると案の定バグっていた。修正すると0.2%ほど上がって60.50%。提出すると6.03G。これもう順位表見ない方が良いな。念のため手元ケース数を1024から4096に増やして改善していることを確認。ちなみに4096ケースだと60.36%で、1024ケースのやつもちょっと甘い可能性が出てきた。
ストレステストを20000ケース回す。無限ループが起きている。マジか。小部屋にIDを振るところでバグっていたので修正。
重み用のデータ収集を走らせて寝る。明日の朝には1位陥落してそうだなあ。明日できることもそんなになさそうだけど、やれるところまでやってみる。
2/26（土/最終日）
朝起きたらもうすぐそこまで迫られてる、と思ったら抜かれた。さすがにね……。
終盤に人の閉じ込めが発生していたため、脱出ルートにはバリケードを置かないようにした。60.76%。提出すると6.03G。まあそんなもんか。
コードを眺めているととんでもないバグを発見した。これ1週間以上前に書いたところなんだけど……。1024ケースだと不足を感じてきたため、4096ケースで試す。60.472%→60.629%。バグってても動いちゃうの怖すぎ。提出すると6,159,277,781点で、wleiteさんの6,159,611,114点とほぼ並んだ。こんな僅差になることある？
通路の両側から閉じ込めるとき、ペットが邪魔で置けない場合は優先度を下げることにした。60.629%→60.941%。0.3%も上がったのはかなり大きい。提出すると6.172G。残り5時間で1位に復帰した。
残り2時間時点でwleiteさんが6.26G。強すぎる。これは完敗。50000ケースのストレステストを回して問題ないことを確認。60.683%だった。大丈夫そうなのでさっきのを最終提出にする。まあよく健闘したかな。
*1:注：これは嘘です。ちゃんと実行時間を計測しましょう。
