MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008） お疲れ様でした。コンテスト時間がいつもより長く、その分実装が重いものになって大変でした。
暫定テストでは5,500,555,555点で 位でした。システムテストで順位が落ちそうなことが心配です。
問題概要
マスからなる部屋の中に
匹のペットと
人の人がいます。うまく仕切りを設置して、ペットが入ってこれないスペースを確保してください。
人を上下左右に動かしたり、上下左右に仕切りを設置したりして、うまくペットを隔離する問題です。インタラクティブ形式で、ペットの動きはターンごとに標準入力で与えられます。
得点の計算方法や各ペットの動きなどは公式の問題文を参照してください。
制約
方針
罠をたくさん仕掛けて、ペットが罠にはまったときに出入り口を封鎖しました。
ここでいう罠とは、出入り口が狭くて簡単に封鎖できる領域のことです。ビジュアライザを見ればわかると思います。
罠の張り方は色々考えられます。最終的には斜めに伸ばした通路を罠にしましたが、もっと良い方法があるかもしれません。
罠の張り方について
簡単なものから順に紹介します。
※それぞれの解法に私が獲得した点数をつけていますが、実装方法によって得点が変わると思います。
何もしない作戦
まず、人が何もしないものを提出しました。
2,041,339点で、ほぼ最低点です。
得点の計算方法を見ると、同じ連結成分に属するペットの数に対して指数関数的に得点が減少することがわかります。よって、広い領域を確保することよりも、ペットを隔離することのほうが優先順位が高そうです。
1マス確保作戦
ペットを隔離するのは少し難しそうなので、人間を隔離するものを提出しました。
11,132,901点で、何もしないときの6倍近くの点数になりました。
部屋分け作戦
点数を伸ばすには、人間の領域をもっと広くする必要があります。そこで部屋分けをするという考えが思い浮かびました。
9個に部屋を分け、ペットが多い部屋を閉めるようにしたところ、2,027,135,417点を獲得しました。 を100%とすると、20%のスコアを獲得したことになります。コンテスト開始2日目で暫定トップになりました。
愚直にこの部屋分けを行おうとすると、犬が中央の部屋に高確率でいてうまくいきません。そこで、犬を左上に誘導することで、先に犬だけを閉じ込めるようにしました。犬は人を追いかけるので厄介ですが、逆に、誘導して閉じ込められる唯一のペットでもあるわけです。このように、犬を狭い場所に誘導して閉じ込める作戦を「犬誘導作戦」と呼ぶことにします。
9個の部屋分けを行うということは、9個（正確には8個）の罠を張るというようにも捉えることができます。罠の数を増やせば、ペットをより狭い領域に閉じ込められそうです。
横縞作戦
正方形の部屋分けは連結性の確保（部屋を閉じても他の部屋同士の連結性が担保されていること）が少し難しいと考え、行を4つにわけるようにして罠を張りました。
3,566,267,413点を獲得しました。
よく考えると、通路3列の左右の列の仕切りはなくてもいいので消しました。
4,668,407,438点まで伸びました。
犬誘導作戦にターン数を割きすぎていると考え、犬誘導作戦をなくしました。
5,003,567,273点を獲得しました。
この方針でどの程度まで得点を伸ばせるかを概算してみます。
ペットを閉じ込める前の時点での、仕切りが占める割合のことを「仕切り占有率」と呼ぶことにします。横縞作戦では、9列は仕切りがほぼなく、残り21列の仕切り占有率が約50%なので、全体の仕切り占有率は約35%になります。
1部屋閉じるごとに4~9マス減少するため、理想的に動いても約53億点（53%）しか得点を得ることができません。（ペットを隔離しきれないケースがあるため、理想よりも少し低い点数になっていました。）
もっと仕切り占有率が低い方針がよさそうです。
部屋を高くする作戦
横縞作戦では横長の部屋だったので、今度は少し高さを出してみました。
4,035,896,807点に下がってしまいました。
仕切り占有率は約28%ですが、入口が狭くてペットが罠に入りにくくなり、ペットを隔離しきれないケースが増えてしまいました。部屋を閉じたときに最大14マス減少するというのもよくなさそうです。
ジグザグ作戦
人は速く通過できるが、ペットは速く通過できない通路を考えた時に思いついたのがジグザグ作戦です。
3,949,690,969点でこれもうまくいきませんでした。
仕切り占有率は30%ですが、思ったよりペットを罠にかけにくかったようです。
斜め縞作戦
罠を斜めに張れば、仕切り占有率を低くしたまま、ペットを閉じ込めやすくできると考えました。
4,652,039,059点を獲得しました。
6分割（人間用通路が5本）は分割数が多すぎる気がしたので、5分割に変更しました。
5,270,763,887点を獲得しました。
仕切り占有率が約29%で、1部屋閉じるごとに7~10マス減少するため、理想的に動けば約56億点（56%）獲得できます。
ローカルでテストケースごとの点数を分析したところ、 のような人が少ないケースでペットを隔離しきれないものが多いことがわかりました。4列の人間用通路を5人で網羅するのは難しいようです。
ハイブリッド作戦
罠の張り方によって、ペットの閉じ込めやすさに違いが出てくるため、 で場合分けをしました。
およそ のときは横縞作戦、
のときは5分割の斜め縞作戦、
のときは6分割の斜め縞作戦にしたところ、5,500,555,555点を獲得しました。（実際には
も少しだけ考慮しました。）
罠の張り方のまとめ
よい罠の張り方とは
- 仕切りを置いても連結性が担保される。
- 仕切り占有率が低い。
- 仕切りを置いたことによって到達不可能になるマスが少ない。（罠が狭い。）
- ペットが罠にはまりやすい。
- ペットが罠から抜け出しにくい。
- 罠の出入り口が少ない。
などの条件を満たすものだと思います。
牛と豚と兎、犬、猫でそれぞれ性質が異なり、全てのペットに対応した罠を張ることが難しかったです。
また、 の値によって、全ペットの隔離の成功のしやすさが変わってくるのも難しいところです。
罠を張る仕事の割り振りについて
近くにある仕切りをいくつかまとめて、30個程度のグループに分割した後、それらを手の空いた人に割り振るようにしました。
工夫した点をいくつか紹介します。
双方向に仕切りを作れるようにする
左から右に移動するケースと右から左に移動するケースの両方に対応できるようにしました。
仕切りを2マスに一気に置く
「1マス動く→1マス置く」を繰り返すよりも、「平均2マス動く→2マス置く」を繰り返した方が少し効率がよくなります。2マスに仕切りを一気に置こうとすることで、ペットのせいで片方に仕切りを置けなくてももう片方に仕切りを置けるケースが出てくるからです。
他の人から遠い仕事を割り振る
Aさんの仕事が終わり、Aさんに新たな仕事を割り振るときのことを考えます。Aさんから見て最も近い仕事を割り振るのではなく、仕事を基準にして、最も近い人がAさんになるようなものを選びました。
このような処理を入れることで人の移動を減らせると思います。
ペットの閉じ込め方について
下図のようにブタが斜めの通路にいるケースを考えます。
このとき、紫の場所から内側に向かって仕切りを設けたいので、紫の場所に移動要求を出します。
また、上図の猫のように、ペットが人間用通路（縦の通路）にいるときは、優先度を低めにしてその場所に移動要求を出すことにしました。
それぞれの人が最も近い移動要求から順に仕事をこなすようにしました。
犬や猫をひきつけてから仕切りを置いたり、人の横移動を減らしたりするなど、いくつかの工夫を行いました。詳細は省略します。
実装のコツ（初心者向け）
実装が苦手な初心者向けに実装のコツを紹介します。自己流ですので参考程度にしてください。
シミュレータ部分と作戦部分を分離する
ペットや人間の動きをシミュレートして入出力も行うシミュレータと、人間に指示を出す作戦部分でクラスを別にしました。
シミュレータを一度作ってしまえば、どんな方針であれ、ほとんど同じものを使い回すことができます。書き直す部分がわかりやすくなり、方針を変えたときの負担が減少します。
シミュレータには欲しい機能をたくさんつけました。BFSで目的地に近づく方向を返す関数や、全ての人が連結状態であるかを確認する関数など、いくつかの関数を使いまわしました。
assert文を入れる
assert文は、条件式がfalseのときにエラーを出してくれます。今回のコンテストでは、予期しないケースが起きやすく、エラーだらけでまともにコードが動かない状態に陥りやすいです。assert文を適切に配置することでデバッグを行いやすくなります。（私の場合、コンテスト中だけで何十回もassert文にひっかかったと思います。）
特にシミュレータ部分にassert文を配置すると、WAやREを防ぎやすくなると思います。
提出コード
ハイブリッド作戦を行なったため、コードが長くなりました。約1900行です。
上位との差（反省点）
自分よりも上位の解法ツイートなどを見て気づいた点を挙げておきます。
- 罠をグリッド全体に張らない方針でも高スコアを出せる。
- 仕事の割り当て方をもっと計画的にできる。
- ペットを捕まえることを最小カット問題に帰着できる。
- 終盤でもペットが捕まらなかった場合に無理やり捕まえるといい。
- 部屋（罠）を
の大きさにして、うまく実装すると高得点を出せる。
コンテスト中は罠の張り方ばかり考えてしまいましたが、ペットを捕まえるアルゴリズムのほうで差をつけられたような気がします。
最後に
2週間のコンテストでしたが、上位層の間でもある程度の差がついていて、とてもやりがいがあるコンテストでした。
最後まで読んでいただき、ありがとうございました。
