MC Digital プログラミングコンテスト2022(AHC008)に参加しました。
問題はTerritory。領域を切り分ける問題です。
暫定テストは826人中9位、システムテストでは7位でした。
問題
グリッド上に動物がたくさんいてうるさいので、300ターンで人を動かしたり壁を置かせたりして人間の領域と動物の領域を切り分けてね。
人間が5～10人いてそれぞれ動き、動物の移動もターン毎に返ってくる、マルチエージェント的*1でインタラクティブな問題だよ。
人間が広い場所にいると嬉しいけど、4近傍連結セル内に動物がいると特大ペナルティがあるよ。
考察
まず、人間が広い場所にいるとスコアが増えるので、人間の領域は出来るだけ広くしたい。人間は複数人いるので、一番広い領域に全員で入るのが最も効率的。つまり、動物を出来るだけ小さい領域に入れる問題になる。
動き回る動物を1手で囲うのは難しいので、残り1マスを閉めるだけの部屋を用意しておいて、入り口にその1マスを閉める担当を配備すると良い。*2
今回もSeed=0のビジュアライズ結果を共有していいルールだったが、そこでも壁含めて3x14の巨大部屋を20個作って必要な場所だけ閉じるものがあった。ただ問題になるのは犬で、犬は人間の間を移動する動きになるので、出入口が1つの部屋に入っていくことは基本無い。*3ではどうするかというと、出入口が2つある通路のような部屋にする。これなら部屋の中を通ってくれるし、むしろ入口の2人の間を通るために積極的に部屋に入ろうとする。
入口2つの部屋を準備して閉じる、という全体方針になるが、部屋を動的に配置するというのは難しい。テンプレートを準備して、その通りに配置させることにする。ではどういうテンプレートがいいか。部屋の大きさ、部屋の数という観点から考える。まず、部屋の大きさは小さいほど理論スコア*4が高くなる。部屋の数は、理論上は（複数同時入れを考えなければ）動物と同じだけあればいいことになる。ただし、部屋が小さくて少ないほど、動物が部屋の中にいる確率が低くなる。また、猫は部屋が小さいほど部屋に入りにくい。動物が部屋にいないことには部屋を閉じられないので、小さい部屋を過剰に用意し、必要な分だけ閉じるという方針が安定しそう。
テンプレート完成後は、人を良さそうな入口に配置して実際に閉じるという問題になる。部屋にスコアを与えて、人を配置する部屋のスコアの総和を最大化するという方針か。色々調べたところ、どうやら最大カバー問題（最大被覆問題）の亜種ということになるようだ。最大カバー問題では1人を配置すると部分集合がカバーされるが、この問題では2人を配置しないといけない。他にも3人で2段をカバー出来たりするので、ここの計算が難しそう。最悪、3-3-4人で3チームにして、各チーム単位で目標を決めれば計算しきれるだろう。
動的に探索しながら動くタイプも一応考察してはみたけど、動物から間2マス以上離れないと間に壁を置けないという仕様上、人間が団子になると犬に粘着されてまともに動けなくなりそうなので、高度な制御が必要になりそう。
やったこと
初動
開始から数日遅れで参加登録。まずはじっくり考察。重実装なのは見えているので、実装ロスが出ないよう問題の性質を考える。
下のようなテンプレートを用意してみた。中央を空けることで、上下の分断が起きないようにしている。この通路が悪さをする予感が無いでもないが、まあ実験的にやってみるのはありかな。通路が無い場合は、部屋は行ごとにどれか1つ空けるようにしないといけない。
テンプレートの設置は、1人目は左端から順に縦向きに設置、2人目は右から、みたいな感じで固定順にした。初期位置に応じたマッチングは後で入れるけど、ロスは今は許容する。
テンプレート完成後は、仕事が無くなった順に人数と縦位置が固定のチームを組んで、最適な列に移動する。評価は、目的とする部屋ごとに{(0.5^動物との距離) * (0.8^チームが到達するまでのターン)}の総和とした。3チームに対して9列なので、適切に前処理してやれば9^3パターンで全探索が普通に間に合う。*5
土日＋αで完成させて、提出スコアは50.6%。*6提出720人くらいのうち14～16位くらいだったかな。
レイアウト変更
やはりというか、極太通路部分に動物が溜まる。牛がこの辺りで反復横跳びしているとどうしようもない。通路部分が多いというだけでなく、太いということも関係していそうだ。幅1なら2方向にしか動けないが、幅2なら3方向、幅3以上なら4方向に動けることも出てくる。方向が多ければ、それだけ期待した方向に動く確率は低い。ということで、レイアウトを変更した。
段にある10列を全て使うと上下が分断されてしまうので、9列使ったら残りの1列は使わないようにしている。
これで提出スコアは56.4%。この時点では牛が一番の強敵。
夢の全員野球
ある程度配置を固定して10^3パターンにしているけど、明らかに仕事をしていない人がいる。1人ずつ目的地を設定できたら強いんじゃないか？と思い、挑戦してみる。
無理でした。作りこめば可能性はあるんだけど、目的地が変わりすぎるせいで部屋の入り口前に留まれないので、全員が実質仕事していない状態になる。これを調整しきるのは至難と思い、この方針は一旦保留。*7
細かい改善
・動物ごとに重みを付ける（牛＞豚＞兎＝猫＞＞犬）
・レイアウトの事前配置の担当列決めをマッチング（一次元なのでソートするだけ）
提出スコアは55.7%。手元ケースでは上がってるのでOK。
レイアウト追加
1位は60%強で、捕獲完遂精度を高めても到達できそうにない。もっと小さい部屋をたくさん用意する方針に変えるか、1部屋に動物をたくさん詰め込まないといけない。（そもそもテンプレートを使う方針が合っているかというのはあるが、ここは自分を信じる）
動物をたくさん捕まえる方針は、ある程度大きく動く動物は犬猫（兎）くらいで、うちコントロールできるのは犬だけなので限界がありそう。また、使用済の部屋が多いせいで手近に入れる部屋が無くなる問題もあり、そういう意味でも部屋が多い方が良い。テンプレートを2つ増やしてみる。
この2つのテンプレートは多少無理があって、部屋が6段のレイアウトでは、部屋の中として封鎖ができる対象位置の、チェスでいう白黒が部屋ごとに1:3となっている。ただ部屋が3マスずつずれているので、全体としてみればそこまで変わらない。7段に至っては1:1で、犬すら捕獲が難しい。ここから、豚猫犬の2マス移動動物が対処しづらくなる。また、通路の割合が増えるため、猫が特に強敵。
ただ多少捕獲失敗ケースが増えても、一定の捕獲完遂率があれば全体のスコアは上がる。ターンを余らせても何も嬉しいことは無いので、ここからはより上位のテンプレートが使えるように捕獲完遂率を上げていくことになる。
提出スコアは57.4%。
細かい改善
・チームの仕事が無くなったら、他のY位置まで出張する
・なるべくチーム内の横座標を合わせる（一部のメンバーが壁置きで停止したら、他も停止する）
提出スコアは57.7%。
夢のドッグラン
犬だけを捕獲するための細長い通路を端に別途作る。
3～4匹も捕まえれば黒字の計算だが、ドッグランまでの移動に最大30ターン近くかかり、通路に引っかかった犬を待ち、犬が中に入り切るのを待ち、と時間のロスがかなり大きい。
どうやら、元々時間に余裕のあるケースでないと厳しいようだ。ドッグランを中央に置くとか、最初に他の壁を置くより前にやればいくらか良さそうな気もしたけど、そこまで差は出ないかな。
また、犬は元々他の動物と一緒に捕獲しやすい性質なのもあり、何処まで効果が出るかは疑問が残った。
細かい改善
・猫の目的地を予想する。猫が入らない部屋にはスコアを加えない。
また、動物の重みを（猫＞牛＞豚＞兎＞＞犬）に変更する。
・チーム内でしか部屋を閉じれなかったのを、全員で閉じれるようにした。
また、複数同時捕獲の部屋や、上下端の部屋を優先するようにした。
提出スコアは58.3%。
使用レイアウト調整
動きが良くなっている分、難しいレイアウトを使いやすくなった。NとMにより振り分ける基準を再設定。
提出スコアは58.2%。下振れっぽい。
ダメージコントロール
動物が1匹残るだけでそのケースのスコアが半減する。これが怖いばかりに部屋が大きいレイアウトを使って得点の上限が伸びなくなっているので、1匹残して被害50%のところを、広めの部屋に入れて10%などに抑えたい。それが出来ればもっと攻めに行くことができそう。
部屋単位で数部屋x数部屋のブロックを作ってみて、それを閉じるための移動が出来るか最小カットで確認して、みたいな感じで実装してみるも、あんまりチャンスが無い。そもそも動物の方が最大速度が速いので、慎重になりすぎているのだろうか。
そもそも動物を残すのは全体の4%程度しかないので、多少攻めたレイアウトに挑むにしても、その1～2割でしか効果が無いというのはあまりに小さい…。結果的にレイアウトを攻めるまでの効果は得られず、動物残しがさらに少し減ったくらい。
提出スコアは57.9%で、下振れ…だといいなぁ。ここでコンテスト終了。
他の人の解法を見て
暫定1位～2位の方は、事前配置して部屋を閉じて、最後の1匹に特殊対応を入れたりと、細かい手法は違うけど大枠は一緒かな。*8
通路幅が3でもいいのが意外でした。あと部屋が1x4（私のは2x2）だったけど、部屋を閉じることが出来る2マスを必ず通らないと部屋の向こう側に行けない構造なので、確かに向こうの方が良さそう。2x2は1/2を引いてくれないと部屋を閉じられないので…。
1x4通路も試作パターンの中にあったけど、途中(10列レイアウトにした辺り)で捨てちゃったんですよね。掘り返してみる価値はあったかな。
ビジュアライズ結果公開について
今回の問題は、上位陣からするとビジュアライズ結果公開との相性は悪かったんじゃないかなぁ…と思いました。理由は以下の通りです。
・犬猫のいない結果を見て方針を真似すると実はハズレという、初心者に対する罠になる。
・犬猫あり想定の結果が共有されると真似するの考察皆無実装ゲーになる。
・Seed=0以外を想定していそうな言及も、無いとは言えなかった。
（そもそもseed=0とそれ以外で方針が違う人は少なそう）
・閃き＋重実装ゲーなので、残り1日などで良い方法が共有されると、実装速度や時間の都合で勝敗が決まる。
ただ今回は参加者層の多くが想定しないであろう振る舞い重視のコンテストなので、ビジュアライザ共有が無いとそれはそれで苦しいのかな…とも。
感想
段階によってネックになる動物が変わって、その対応を考えていく問題解決の連続が面白かったです。最後まで実装イヤイヤ期が来なかった。
スコア計算はペナルティが多すぎて、ケース1000件回しでは済まない限界チューニングゲーになっていたところはありそうです。時間を長くして残り時間ボーナスにするとか、20匹に対して1匹残りなら5%ダウンとか、ペナルティが軽くなれば助かるかなと思いました。
※ビジュアライザの画像にはDOTOWN様の画像が使用されています。
