MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008）お疲れ様でした。今回はratedコンテスト初の一桁順位（3位）を取ることができたのでとても嬉しいです。レーティングも2512まで上がって正式に橙コーダーになりました。
というわけで、今回も解説を書いていきます。今回はかなりアルゴ寄りの解法で、bit DP、マッチング、最小カットなどが盛りだくさんになっています。
問題概要
ペットが放し飼いにされてるので良い感じに仕切りを配置してペットのいない広いスペースを確保してね。
めちゃくちゃTopCoder MMっぽい問題！案の定今回はMM勢が強かったです。今までと比べてもかなり自由度の高い問題で、なかなか取っかかりを掴むのが難しい問題でした。
方針
最初から全員でペットを追いかけ回すという案もありましたが、あまりに難しすぎてまともな実装になる気配がなかったので諦めました。
横方向に通路を作り、左右の大通りからフタをして捕まえる方針にしました。このように通路を作ると犬や猫が左右に移動するとき必ず通路を通るようになるため、かなり捕まえやすくなります。かわいいね。*1
またそれだけだと捕まえきれないケースがあるため、残りターン数が少なくなった場合は通路を気にせず全員で捕まえに行くアルゴリズムも入れています。
上記方針を実現するため、いくつかの手順に分解します。
- 左右から捕まえるパターン
- 柵を置く担当を割り振る（初回のみ）
- 担当割りに従って各スタッフが柵を置く
- 柵を置き終わったスタッフから大通りに向かう
- 大通りの左右からペットを捕まえる
- 全員で捕まえに行くパターン
- ペットを捕まえる柵の配置を決める
- 柵を置く担当を割り振る
- 柵を置く
ここまで来たら、あとはひたすらアルゴリズムの問題として解いていきます。
登場する主な問題・アルゴリズム
今回は焼きなましもビームサーチも使っていません。かなりフローを多用しています。*2
| 問題 | アルゴリズム |
|---|---|
| 配送計画問題（最大値最小化） | bit DP |
| 重み付き最大二部マッチング（重みの最大値最小化） | Dinic*3 |
| 重み付き最大二部マッチング（重みの総和の最小化） | 最短路反復 |
| 重み付き一般マッチングもどき（重みの総和の最大化） | DFS全探索 |
| 最小カット | Dinic |
| 関節点列挙 | LowLink |
| 回帰 | Neural Network*4 |
| 期待値計算 | モンテカルロ法 |
解説1（左右から捕まえるパターン）
柵を置く担当を割り振る
ターン数が300しかなくて時間的に結構厳しいので、できるだけ早く柵を置ききってしまいたいです。これはどういう問題かというと、柵の担当を各スタッフに割り当てて、一番時間のかかる人の終了ターンをできるだけ早くする最大値最小化問題になります。スタッフが一人なら巡回セールスマン問題になりますが、今回は複数人いるので配送計画問題ですね。
配送計画問題を真面目に解こうとするとかなり大変ですが、今回の柵の配置位置を考えると、ある程度巡回のパターンを決めてしまっても良さそうです。ということで、下図のようにヘビ型の巡回経路を考えて、この経路をいくつかの区間に分割した上で各スタッフに良い感じに割り振ることにします。*5
ここで難しいのは、単純に各スタッフに均等な長さの区間を割り振れば良いというわけではないということです。スタッフが区間の開始地点に到達するまでにもターン数がかかるので、そこも考慮に入れないと真に最適な担当割りが求められません。ここではbit DPを用いて担当割りを求めることにしました。
選択済みの人の集合が
で、ヘビの
マス目まで割り振り済みのとき、最も時間がかかる人の必要ターン数*6
と定めてあげると、これはヘビの経路長をとして
で求めることができます。ちょっと計算量が怖いですが、10人のケースでもなんか間に合ったのでOKです。*7
担当割りに従って各スタッフが柵を置く
ここは単純に柵を置いていくだけです。注意点として、スタッフの進行方向に柵を置くと遠回りするハメになるので必ず設置位置を通り過ぎてから置くようにしましょう。
柵を置き終わったスタッフから大通りに向かう
柵を置き終わったスタッフから順番に大通りへと向かわせますが、ここの割り振りも注意が必要です。柵を置き終わるタイミングはDPのおかげである程度同じくらいにはなるのですが、たまにペットに邪魔されてめちゃくちゃ遅れるスタッフが出てきます。こういうスタッフはなるべく近い大通りへと優先的に割り振ってあげたいです。
これももうちょっと問題を整理すると、最も遅く到着するスタッフの到着時間を早める最大値最小化のマッチング問題になります。スタッフと通路
の間に到着までにかかるターン数
の辺が張られていて、
の最大値を最小化します。なおターン数は（柵の構築完了までにかかるターン数）＋（大通りへの移動にかかるターン数）より求めます。
なんとなく最小費用流で解きたくなりますが、最小費用流はの総和を最小化するだけで最大値の最小化はしてくれないため、ここでは不適です。
実はこの問題は蟻本p.206「Evacuation」とほぼ同じ問題で、最大流問題として解くことができます。ターン数を1ずつ増やしながら、の辺を追加してフローを流す、それでダメなら
の辺を追加してさらにフローを流す……としていき、全てマッチングできた時点のものを解とすればよいです。*8
大通りの左右からペットを捕まえる
準備が整ったので、ペットを捕まえていきます。最初にチームを決めてチーム単位で動かしている方も多かったようですが、私はどのペアで捕まえに行くかをマッチングにより動的に決定しました。
まず、スタッフとスタッフ
で通路
を閉鎖するときの評価値
を全て算出します。通路
にスタッフ
とスタッフ
が辿り着くまでのターン数を
*9、
ターン後に通路
に存在するペット数の期待値を
、通路
の面積を
として、
と定めました。ペット数の期待値
はモンテカルロ法で雑にシミュレートしています。*10 また通路を閉鎖することでマップの連結性が失われると大幅なスコア減となるため、LowLinkで関節点を求めたうえで関節点は候補から外しました。*11
この評価値の和が最大となるような閉鎖タスクの集合を求めていきます。厄介なのは、一人のスタッフに2つ以上のタスクを割り当てられない点です。各スタッフについて、右側の人とペアにすべきか左側の人とペアにすべきかを考えなければなりません。
ここで、スタッフを頂点とし、スタッフ間に重み
の辺を張ったグラフを考えます。*12 このようにすると、この問題は一般最大重みマッチング問題もどきとして捉えることができます。「もどき」としているのは、同じ通路を2組以上のスタッフに割り当てることができないためです。*13 今回はDFSで全探索してしまいましょう。validな集合は結構少ないようで、十分高速に求められます。選択済みのスタッフや通路の集合はbitで持っておくと判定が楽です。
なお、ここでペアからあぶれた人は近くのペットに横軸を合わせに行くようにしました。ここでも貪欲に近付かせると同じペットにスタッフが群がる事象が発生しそうだったので、ペットまでの距離を辺の重みとした重み付き最大二部マッチングを考え、最小費用流問題として解いています。
ここまでやってようやく左右からペットを捕まえることができるようになりました。
解説2（全員で捕まえに行くパターン）
基本的には上記の戦法で行きますが、これだけだと捕まえきれないケースも出てきます。特に牛や豚あたりはなかなか通路に入ってくれないことがあるため、残りターン数が少なくなってきたら自分から動いて捕まえに行くようにしました。
ペットを捕まえる柵の配置を決める
うまくペットを捕まえられるように柵の配置を決める必要がありますが、これは結構難しいです。今回は大通りをsource、ペット周辺の2マスをsinkにつなぎ、最小カット問題として捉えました。
辺の張り方について説明します。今回はグラフの辺ではなく、各頂点（マス）でカットする必要があります。これも蟻本のp.192に書いてあって、頂点数を2倍にしてin側の頂点とout側の頂点を作り、その間に辺を張ることで実現できます。ABCの過去問でいうとこの問題（ネタバレ注意）が参考になるでしょう。なお、ターン数制限内に到達できないマスではカットできないため、そのようなマスの辺は容量としています。
あとはsourceから大通りマスのin側に、ペット周辺のマスのout側からsinkに辺を張ればよいです。イメージとしてはこんな感じです。各辺の容量は試行錯誤して適当に決めます。*14
グラフができたらACLを使って最小カットします。inがsource側、outがsink側になっているところがカットすべきマスです。
柵を置く担当を割り振る
柵を置く担当を各スタッフに割り振ります。これも重み付き最大二部マッチングを考え、最小費用流で解きました。スタッフと柵
の間にコスト＝距離
の辺を張ってマッチングさせています。誰も割り当てられない柵があると困るので、図のように柵
からsinkへの辺を2種類作ることで確実に1人ずつは割り振られるようにしました。
柵を置く
あとは設置場所に近付いて柵を置くのですが、結構な確率でペットと一緒に閉じ込められるスタッフが発生してしまいました。かわいそう。
ここはなかなか上手くいかなかったところで、とりあえず脱出経路を作って脱出経路上には柵を置かないような処理を入れました。ただし一部のスタッフを犠牲にした方が点数が上がるケースも多いため、300ターン目でも脱出不可能な場合は容赦なくスタッフごと閉じ込めることにしました。このあたりもうちょっと上手くやりたかったです。
解説3（その他）
基本の流れとしては以上ですが、他にもいくつか工夫をしたので紹介です。
モンテカルロ法によるスコア期待値予測
全員で捕まえに行くパターンを実装してみたものの、結果はかなり不安定でした。そこで、このパターンを使う場合・使わない場合でスコアの期待値がどの程度になるかモンテカルロ法を使ってシミュレーションを行い、スコアの期待値を予測しています。モンテカルロ法の発動ターンは275ターン目で、それぞれだいたい50～100回ずつくらい試行が回っていました。
NNによる最適マップの予測
スタッフとペットの数によってターン数に余裕が出たり出なかったりしたので、いくつかマップの候補を作成して使い分けるようにしました。
どのマップを選ぶべきか考えましょう。各マップで想定されるスコアの期待値を求めて、一番期待値の高いマップを選べば良さそうです。
実行時間に余裕がある場合はモンテカルロ法でシミュレーションすれば期待値が求められますが、1回あたり500ms程度かかっているためちょっと現実的ではありません。またスタッフ数とペット数からどのマップを使うかという表を作成しておくのも良いですが、できればどのペットが何匹いるかという情報も考慮に入れたいです。というわけで、今回はNeural Network (NN)で各マップのスコアを予測させることにしました。*15
入力は(スタッフの数, ペットの数, 牛の数, ..., 猫の数)の7要素、出力は各マップごとの得点率（0～1）とし、マップごとに10万ケース分のデータを学習させました。ネットワーク構成は (dense 7x32 → relu) → (dense 32x32 → relu)x3 → (dense 32x5 → sigmoid) としています。*16
なお数ある回帰手法からNNを選定した理由ですが、NNは結局重みを埋め込んで行列計算すれば良いだけなので*17、GBDT系等の他の手法よりRustへの移植が簡単そうだったからというだけです。別にNNの表現力でないと予測できないというわけでは全然ないと思います。さすがに線形回帰とかだと表現しきれないとは思いますが。
以上を実装すると、3位になることができます。コード長はACL部分を除いても4000行近くとなりました。今までのコンテストで最長です。
感想
最初は賢い貪欲を作るゲームなのかなと思っていたのですが、当初の想定以上にアルゴリズムの使いどころがあってびっくりしました。自分でも納得のいく解法が作れたのでかなり満足です。綺麗な解法が作れると嬉しいですね。このようにヒューリスティックコンテストでも意外と各種アルゴリズムの使いどころがあるので、普段ヒューリスティックコンテストに出ていない人にも是非出てほしいなと思っています。
また300ターンというターン数制約も絶妙だと感じました。ここが緩いと細かいところを詰めるだけのゲームになりますし、キツいと無理ゲーになってしまうところかと思います。このあたりの調整も素晴らしかったように思います。*18
ビジュアライザの共有は難しい問題だったように感じます。個人的にはHTTF2022予選くらいが許容ラインで、今回の問題は戦略が盤面にモロに出てしまうのでちょっとやりすぎかなという感覚でした。とはいえビジュアライザが共有されると宣伝になって参加人数は増えますし、まったく手の付け方が分からない人のヒントにもなるので悩ましいところですね。*19
2週間、最後までずっとやることが尽きないとても面白い問題でした。writerのwataさん、スポンサーのMC Digital様、本当にありがとうございました！
おまけ
コンテスト中に書いていた日記はこちら。長いので別記事としています。
*1:ここは天才パートかなと思いますが、ここを除けばあとはひたすらアルゴの問題が続きます。
*2:ヒューリスティックコンテストでフローが使えるとなんだかテクいことをしている気分になれます。
*3:二分探索してもよいですが、実はしなくても解けます。
*4:アルゴリズムでは、ありません……。
*5:ヘビの始点を左上にするパターンと右上にするパターンの2パターンが考えられるので、両方試して良かった方を選びます。
*6:スタート地点へのマンハッタン距離＋経路の長さ＋置く柵の数。区間の始点をスタート地点とするパターンと終点をスタート地点とするパターンの2通りがあるので、どちらか小さい方を選びます。
*7:ちなみに1人で全体の9割を担当するような極端なケースが解になることはないので、もし実行時間が厳しい場合はDPの遷移幅を制限することで高速化が見込めます。
*8:もちろん二分探索でターン数を決め打ち、グラフを作成してフローを流してもよいです。
*9:チェビシェフ距離ですね。
*10:猫を真面目にシミュレートすると計算量が大変そうなので、猫は豚と同じように動かしています。逆に犬は各スタッフからBFSしておけばそこまで計算量は増えないのでそちらは真面目にシミュレートしました。
*11:袋小路は閉鎖しても問題ないため後処理で除外しています。今思えば通路を辺と見なして橋を列挙する方が綺麗だったかもしれません。
*12:一人で閉鎖できる通路については、スタッフからスタッフ
に自己ループとなる辺を張ってしまえば誤魔化すことができます。
*13:集合被覆っぽく捉えた方が良かったかもしれない？
*14:なんかいい感じの決め方があれば知りたい……。
*15:もし実行時間が許すのであれば、NNとモンテカルロのアンサンブルなどもやってみたかったです。また盤面を画像と捉えてCNNに突っ込む案もありましたが、提出容量制限に引っかかりそうなのと逆に精度が下がる可能性があったため不採用としました。
*16:ノウハウがないので適当です。
*17:重みの埋め込みにはbase64を使いました。base64デコーダを自力実装するのがなかなか苦行でした。
*18:ちなみに捕獲失敗率ですが、スコアが35%以下だったケースを「捕獲失敗」と雑に定義してローカルで1000ケース回したところ2.0%ほどでした。
*19:Kaggleなんかは公式discussionがありますが、よくあれで競技として成り立つものだと感心しています。競プロ出身勢からするとあの形式はなかなか慣れません。
