MC Digital プログラミングコンテスト2022（AtCoder Heuristic Contest 008）

AHC

暫定64位（4.72G点）、最終55位（93.9G点）の者の思考過程と試行過程です。
ほとんどが外れ方針をやっていた過程なので、最終的な方針のことは13日目以降くらいにしか書いていません。

問題概要

A - Territory

  • 30 \times 30のマスの中に、10～20匹のペットと5～10人の人間がいる。
  • 300ターンに渡り、人間の行動を出力し、ペットの行動を受け取るということを繰り返す。
  • 最終的に、人間がいる連結成分の広さを、同一連結成分内にいるペットの数をnとして\frac{1}{2^n}にした得点を得る。1ケース当たりの上限（あり得ないがペットも障害物も0個の場合）は1億点で、暫定100ケース当たり100億（10G）点となる。
  • 各ターンの人間やペット（5種類）の動きは以下の通り。犬や猫は、目標に到達するか到達不可能になるまで目標は不変。
    • 人間：隣接するマスに1回移動、または隣接するマスに壁を置く。
    • 牛：隣接するマスへのランダムな移動を1回行う。
    • 豚：隣接するマスへのランダムな移動を2回行う。
    • 兎：隣接するマスへのランダムな移動を3回行う。
    • 犬：特定の人間に向かって1マス移動した後、隣接するマスへのランダムな移動を1回行う。
    • 猫：特定のマスに向かって1マス移動した後、隣接するマスへのランダムな移動を1回行う。

　

1日目

  • ペットを追いかけて取り囲むのは難しそうな気がするので考えないことにする。
  • 適当に半分くらいに区切ってみたときのことを考えると、面積による基礎点はおよそ半減するが、ペットを1匹でも締め出せれば元が取れるので、適当に区切っていっても区切る前の状態より点数が下がるようなことはあまりなさそう。
  • いかに狭い範囲にペットを閉じ込めるかという問題であると認識する。
  • とりあえず、5等分くらいに縦に区切った後、上から下に下がりながら、ペットが該当エリアの上部にいれば横線を引いて閉じるということをやってみる。
  • ペットが上にいなければ、真ん中辺りで待機する。

f:id:ks2m:20220227000753p:plain
※青が人間、赤がペット

  • これで370M～400M点程度。開始4～5時間の時点で最高3位になる。（あとは最終日までほぼ下がる一方）
  • 区切る本数を人数分にしてみたりして、474Mまで伸びる。

　

2日目

  • とりあえず1日目の方針で、待機場所を上\frac{1}{3}辺りに変えてみたりして、517M。
  • 最初のエリア分けを5～7個くらいまでにして、余った人間はいるエリアでは、2人で両側から同時に置いていくことで下にすり抜けられることを減らしたり、上と下から別々に作業させたりといったことを考えたが、バグり始めたし、この方針で頑張ってもすぐに行き詰まると思ったので捨てることにする。
  • ビジュアライザに人間の行動をコピペして、ビジュアライザに出てくるペットの行動を実行プログラムの方にコピペして、\cdotsを手作業でやるのが限界になってきたので、ジャッジも作ることにする。

※なおこの時点では、不正な出力をしていてもチェックしていないし、犬や猫の動きに不備もあった。（結果をビジュアライザに貼ると壁に突っ込んだりしている）

  • 共有された画像を見て、1手で閉じ込められる隅の方でペットが来るのをひたすら待ち続ける方針を思い付く。

f:id:ks2m:20220227005239p:plain

  • これなら20匹いても12行くらいしか使わず、上手くいけば6G点以上が見込めるのではと思ったりもするが、現実的には上の方の狭い範囲にはなかなかペットはやって来ず、あるいは複数来てなかなか5人同時には置けなかったりと、300ターンでは良くても5箇所目くらいで終了といったところだった。
  • 一応提出はしたが、23M点で論外。

　

3日目

  • 基本形は1日目に近い形に戻しつつも、まず全員を同じ連結成分に入れたいと思い、エリアの閉じやすさも考慮して以下のようなものを考える。

f:id:ks2m:20220227010754p:plain

  • 多少の調整をしても519Mでほぼ変わらず。
  • ビジュアライザを確認すると、中央の通路が犬だらけになってどうにもならない感じ。
  • また、エリアを1つ閉じることで失う面積が大きすぎるのも問題がある。

4日目

  • 周囲だけあるいは中央だけ市松模様に塗れば、その部分にペットが入り込めば足が遅くなって囲いやすくなりそうな・・・などと考えてみたりするが、100Mも出なそうで却下。
  • 他にも囲碁のように初めは一間飛び、二間飛びのような形で緩やかに囲って徐々に形を確定させていくようなことも思い浮べてみたが、上手く囲い込める気がせず思い付いただけで終了。
  • ある程度真面目に確率を考えてみると、やはり3日目のような入口が1マスだけあって内部が広くなっている形が最も抜け出されにくいように思える。
  • 出口目前まで来た時に、出口に入る確率が\frac{1}{4}で、続けて完全に外に出る確率が\frac{1}{2}なので、合わせて\frac{1}{8}？
  • 出入口付近に余計な壁があると、\frac{1}{3}や\frac{1}{2}になって出て行かれる可能性が増しそう。

　

5～9日目

  • 以下の要求を満たす置き方を考えた結果、図のような形を目指すことにする。
    • 人間が1つの連結成分に残れる。
    • なるべく少ない壁の数で多くのエリアに区切れる。
    • 通路があると犬や猫が留まってしまうことが多いため、通路が少ない方が良さそう。
    • 固定位置の壁を置く処理が比較的単純。

f:id:ks2m:20220227013328p:plain

  • 比較的単純とは言いつつも、図の固定壁を作るだけでも意外と手間がかかり、ここからさらにペットがいる区画を特定して各方向の穴を埋めに行くのはさらに大変で、どんどん時間が過ぎていく。
    • 隅や辺の区画を優先。
    • ペットが多くいる区画を優先。
    • 埋めたら他にも行けなくなる区画が発生する場合は、その区画数に応じて優先度を下げる。
    • 最後の穴を埋める際は中に人が取り残されないように考慮。
    • 通行不能区画が発生する際、人間は区画数最大の連結成分に移動。
  • くらいのことはなんとか盛り込んだつもりだが、996M止まり。
  • この方針でも相変わらず最後は犬にまとわりつかれることが多く、また、4方向埋める必要がある箇所が多いせいで、特に猫には埋めている間に逃げられることが多かった。
  • なお悪いことに、閉じ込めを完遂できないと通れなくなった壁だけが残ることになり、終盤になると人の移動距離が増えたり、一度に多数の区画が到達不可になることも増えたりしている。
  • 4人同時に特定区画を目指して移動させるようなことまではできず。
  • それでも犬や猫がいないseed=0では最大6000万点程度出ることもあった。（自作ジャッジなので基本行動に偏り等はありそう）

　

  • ちょっと何かを実装すればすぐREになり、提出さえもできない時間が続く。
  • ありがちな上に原因特定が難しかったミスとして、
    • 有効な行動がない時にうっかりcontinueをしていて、ちゃんと300回出力していなかった。
    • 人1から順番に行動を決めていったら、後の方の人の壁を置く行動によって、前の方の人の移動ができなくなることを判定できていなかった。（移動前後の位置を両方とも保持しておいて壁設置可否判定をしないといけない）
    • BFSのスタート地点が壁である場合を考慮していなかった。（猫の目的地への到達可否判定がこれでおかしくなっていた）
    • 毎回BFSをすると重そうなので、目的地までの経路をまとめて決めておいたら、後からその経路上に壁を置いてしまって実行不可になっていた。
  • などがあり、ちょっとした判定の順序や添え字ミスなどによっても全く意図しない動作をすることが多々あった。
  • 人の相互作用によるものは発生確率が低いものもあり、再現すら困難だったため、最初のターンから通してシミュレーションし直してチェックできる限りのことをチェックしたりもした。

　

10～12日目

  • 犬の対処方法を思い付く。
  • 下図のように細長い領域の隅に人間全員を集め、全ての犬が寄ってきたら、一斉に出口に向かっていき、犬を振り切れたところでふたをする。というもの。

f:id:ks2m:20220227023156p:plain

  • 計算上は犬の下に向かう平均速度は1ターン当たり1マスよりは小さいと考えられるため（犬の各ターン2手目が、下に動けば+1だが上や横なら-1として働く）、人を下に動かすだけでも振り切れることはそれなりに多いのだが、上手くいかないこともあり、その場合は一度上に戻ってやり直しを行う。
  • これを祝日まで使って3日かけて実装するも、9日目の点数を上回ることはなかった。
  • 主な原因は、完全なターン数不足に陥ったこと。
  • 固定壁を横線5本と28列目の縦線だけ引き、人間が右上に全員集まるまでには約100ターン以上。6人以上いた場合に縦線も先に引かせていたら約130ターン以上を要するようになった。
  • その後犬が全部右上に集まるまでにさらに数十ターンかかることがザラにあり、多くの場合ここまでで160ターン前後かかっていた。
  • 右下まで回らせると遅いので、犬が右2列内に寄るまで(5, 27)や(10, 27)を空けておくこともしたが、効果がなくはなかったものの、焼け石に水レベル。
  • 結局、犬はまとめて対処できても残りのペットを相手にするターン数が足りず、特に猫はほとんど生き残ったまま。

　

13日目

  • 下図のような壁配置ならば、猫にも対処可能なのではと考える。
  • 初日から良い区画の作り方を色々と考えていたのだが、正方形に近い形が駄目ならば細長くした場合はどうかと思い、またそろそろ猫対策も考えたかったこともあり、猫の動きを想像してみたら、行けそうだと思えた。

f:id:ks2m:20220227031056p:plain
※右下は前回同様の犬用スペース、灰色は後からふさぐ壁
※犬の対処をした後、人間は10, 20, 30行目を横移動のみ行う

  • 猫に対処可能な理屈としては、例えば上の方にいる時に下の方が目的地になると、必ずどこかの縦に長い区画を通る必要があり、その区画が十分長ければある程度長いターン数足止めできるため、その間に人が移動してきて出入口をふさげる可能性が高い。という感じ。
  • 1行動目は最短距離という性質から、一度区画に入れば基本的に反対側の出入口を目指しているはずなので、入ってすぐ戻ってくるということがあまりない。
  • また、100ターンほどあれば結構何度も目的地が変わって行き来するため、チャンスも多くある。
  • 犬用スペースを短くしたことで、準備に要するターン数は軽減されたものの、犬を閉じ込めること自体の成功率が下がり、300ターン経過するまでずっと右下で上下運動を繰り返したということも。
  • この日の内に満足のいく実装は完成せず。

　

14日目

  • 右下に余計なスペースを作らなくても、猫と同じ理屈で犬にも対処できていると気付く。
  • むしろ犬の方が、同じ行にいる人の間で目標が切り替わり続けない限り、簡単に上下に移動してくれるまである。

f:id:ks2m:20220227034113p:plain

  • イレギュラーな部分がなくなったことで固定壁設置部分の実装も少し簡単になり、区画を閉じる部分も一旦適当にペットの数が多いところや犬や猫がいるところを優先的に置きに行く程度で済ませ、なんとかこの日深夜に提出までこぎ着ける。
  • そして一気に3.6G点まで上がり、順位も254→118位に。
  • もう1日も残っていないのに、ここに来てやっと基本形ができた感じ。
  • この形自体は共有画像で似たようなものを比較的早い段階で目にしていたのだが、突き詰めれば正方形に分割した方が固定壁が少なくて強いのではと思い込んでしまっていた。結局閉じるのが果てしなく困難だったが。
  • ずっと犬にばかり気を取られていたので、猫に対処できる有用性になかなか気付くこともできなかった。

　

15日目（最終日）

  • 固定壁だけで3割近い減点になっているので、固定壁を減らす余地がないかを考える。
  • 例えば14日目の3層構造を中央の1層だけにしてみたらどうか？
  • 犬はだいたい捕まえられ、猫も半分以上はなんとかなりそうだったが、他の3種類は厳しそう。
  • 上下の層は、縦線10本全て引くのではなく、ペットのいる付近だけに絞れば・・・などと考えもするが、もう複雑なことをしている時間はないのでやめる。
  • 14日目は3 \times 11の区画に分けていたが、幅2列いらなくない？ということで、下図のような3 \times 15を検討する。
  • 結局壁の置き方が14日目よりもさらに単純になった。14日目の時は人を往復させて置いていたが、これなら人が7人以上なら2列まとめて置きながら片道だけで済む。

f:id:ks2m:20220227155550p:plain

  • 壁増やしてるじゃんと思われるが、区画を閉じていった時に失われる面積が少なくなるため、それも込みでどちらが得かをきちんと数えることにする。
  • 結果、3 \times 11よりも3 \times 15の方が、1つ2つくらい多くの区画を消費しても同じか少し得になりそうだった。
  • ちなみに3 \times 15で上1行の15区画を消費した場合、456マスを失うので得点率は5割弱。
  • 固定壁設置パート以降の閉じ込めパートでは、3 \times 11も3 \times 15も完全に同じ実装で対処可能であったため、どちらでも提出できるように進めつつ、徐々に3 \times 15の方が若干上回り始めたので最終的にはそちらを採用する。
  • 最終日に新たに実装したこと
    • 担当分の固定壁設置を終えた人間は、全員が終えるのを待たずに閉じ込めパートに移行し始める。（正方形区画案の時はこれをやると人が人の邪魔をしてなかなか上手くいかなかった）
    • 閉じたい区画に2人セットで割り当て、上側と下側を同時に閉じるようにする。
    • 閉じたい区画がない時、将来の閉じたい区画に事前に近付いておくため、ペットがいる列の方に動く。
    • 人が6人以下の時、まず上から下に向かいながら左から10or12列の壁を作り、下から上に向かいながら残りの4or2列を作っていたが、一番右上の最後の部分は、もう一度10行目まで戻ってくるので、上に向かう時は置けるときだけ置き、置けるまで待つことをしないようにする。
    • 最初に上から下に向かいながら固定壁を設置している時、10行目に達した段階で既に真上の区画にペットがいたら閉じておく。
  • 上記の上3点はそれなりに効果があり、点数がどんどん上がっていった。
  • この辺りで、手元100ケースの実行では多くのケースで5000万点台が出ていたが、いくつかは2500万前後、1200万前後、600万前後といったケースが発生している。
  • それらのケースについて、人数と取りこぼしているペットの内訳を出力してみる。
  • 結果は、5人のケースが多いかと思いきや、比較的多くはあるものの人数が少ない場合ばかりが問題ではなく、ペットの方は犬の取りこぼしはほぼなく、牛と猫が多い。
  • 牛は足が遅すぎて、10, 20, 30行目の横通路からなかなか各区画の中に入っていってくれない模様。
  • とはいえ、打てる対策としては、牛や猫がいる区画を閉じる優先度を上げるくらい。
  • やり方としては、牛150点、豚80点、兎100点、犬140点、猫170点のように点数を付け、区画内にいるペットの合計点が区画の広さに応じた点数以上であれば閉じる対象にするという感じ。（初め牛は90点にしていた）
  • 閉じるボーダーは、序盤は右端の広い区画は240点以上、その他は120点以上程度。一応最終的に設定した点数がこのようになったが、あまり根拠のある数字ではない。
  • あとは、ターン数経過によってボーダーを下げていくのを早めたり、ボーダー以上であれば人間の現在地から近いところを優先するように変えたりしてみたくらい。
  • あまりボーダーを緩くし過ぎても、取りこぼしが減る以上に最高点が減った。


最終提出


暫定結果：4,728,988,874点、64位
最終結果：93,950,298,518点、55位、パフォーマンス2107相当
レート変動：1740→1816（+76）


終了後に出てきた上位陣の解法を見ると、自分の最終解法はだいぶ近付いてきてはいたみたい。
ただ、3層ではなく5層くらい作るべきであったようだ。

5～9日目の正方形区画案も、何気に10～12日目に列数を増やしているし、これも4箇所ふさぐのは困難なので上下2箇所だけにしてさらに列数を増やす方向に向かえば、同じような形にたどり着いたかもしれない。

最後の3日間でなんとか軌道修正して十分な結果を残すことができたが、基本ができただけでまだまだこれからの段階で終わってしまったので、回り道に時間をかけ過ぎず、12日目くらいでここまでできていればというのが心残りだった。