# 2022/02/12～2週間　AHC008(MC Digital)

https://atcoder.jp/contests/ahc008

### 2/12(土)
[感触]
なるべく多くのテリトリーを作るゲーム。
ベストは動物を四隅に追い込んでしまうこと。
「動物は人も動物も通過できる」ので、追い込み漁が使えない。
さらに、「隣接するマスにペットが居るマスを選ぶことも出来ない」ので、
タイミングを見て設置も難しい。
→うなぎ筒のような仕掛けがいいかも。

犬はくっついて来て離れないので、対処が必要そう。

うなぎ筒はちょっと無理そう。ターンが足りない。
それよりは、人が斜めに並んで四隅に向かって段々壁を敷くのが良さそう。

運悪く抜けたやつは、囲んで小さい範囲に押し込めてしまう。

移動確率

囲碁の知見が活きそう。
斜めに置く「カケ」が方向の制限に良い。

周辺には壁を置かない。ここまで回り込んで来たら一気に囲う。

とりあえず右下に追い込むコードを書く。
ゾーンディフェンスっぽいことをした方が良さそうなので、
5人前提で20%ずつわりふる
→うーん、適当にカケるだけじゃ全然まとまらん。

個別捕獲を考える
こういうのは当然狙う。
端に追い詰めるイメージ。

だだっ広いと捕獲が難しい。
最初に端に寄せるための補助を敷く。

[アイディア]
済・犬は誘導できるので、最初に閉じ込めてしまった方が楽そう。
・猫も後半は予測が効きそう。
・鶏は序盤追い詰めても暴れるので後半でいい。

閉じ込め順序
犬>牛>豚>>猫>鶏

### 2/13
eijirouさんが、ダブルスコア付けて2,027,135,417点。2G点。
理論値が10Gなので、最終5Gくらいはでるはず。

補助の発展
4マス開けて斜めに引くと、4人で楽に抑えられる。
ツーマンセル行動をさせればいいから楽。
全体はこう。

seed=0～99を回して調整。補助が多いと時間がかかったので減らした。
最遅がseed=9、turn129。
iehnさんが上げてたこれが強い。
ただ、ランキングのスコアは1,649,412,760点、1.6G。ちょっと置くのに時間がかかり過ぎか。
https://twitter.com/arimasenu/status/1492766522699583492
↑
犬も随時閉じ込めながらこれができそう

takoshiさんの、ゲームAIって感じ。
69,444,444点なので、5G超え狙える。
https://twitter.com/takoshiiiiiiiii/status/1492788191195447298

rabotさんが4,139,194,443点、4G。

クロスより、ひし形の方が四隅を使えて良さそう。
[アイディア]
犬は最初中央に集めたいので、
☆初めから端で待たずに、中央に寄って待った方が良さげ。

iehnさんが続投。完封できるようになった。
55,444,444点。ランキングスコアも3G出てたので、完封できてそう。
https://twitter.com/arimasenu/status/1492871668922216448

フリーでの捕獲アイディア
移動だけに絞ったパターンと、壁置きも可能なパターンとに分ける。
☆人の周囲を壁配置可能マスとして、動物の捕獲可能性から評価をつける。
☆貪欲を3回まわせば、大体ベストな動きになるだろう。

☆壁配置の評価は、動物の存在範囲を絞れる度合いで評価したらいい。
☆本来、一人での対応と二人での対応は本来作戦を変えた方が良さそう。
まずは一人での対応を作る。(動物に対して、担当を一人だけ付けるようにする。)

適当に壁を置く。
2マス目に置き続けてもダメだった。
動物の開けてる側に廻り込むようにする。

### 2/14
フリーでの捕獲をできるようにしたい。
動物の捕獲までの段階に分ける。
1. フリー
2. 8方向のうちいくつかが塞がれてる
3. 捕獲間近(特定行動したら捕獲できる)

それぞれの段階に応じて取るべきポジションが変わる。？

動物に対して、ある程度エイやでラインを引いてしまう。

内側から閉じて、外に回って捕獲。

捕獲の評価関数。
壁の有無での存在確率で評価。
2乗した値に定数をかけたものをスコアにするとか。
動物個別ではなく、一気にやっちゃっていい。
上手く壁の設置にコストを設けたら、バランスするんじゃないか。
動物が近くて置けない事もあると思うので、行動の期待値最大化のビムサ。
☆動物毎に存在確率分布は個別に出す。
自身に影響ある範囲の壁が更新された時、再計算したらいい。
→猫が鬼門。挙動からざっくり目的地を推測して無理やりはめてしまうのが良さそう。

初期の敷設について、最初の計算でベストな形状を求められそう。

[仕様理解]
犬は、1ターン目の移動で目的人に到達したあと、2ターン目にランダム行動するっぽい。到達可能な人がいる限り2回行動ということ。
ターン開始時点で目的人だと次の人を選ぶので、やはり人はかたまって待ち構えるのが良さそう。
→1マス以上人から離れることが無い。
→中央から引き続けたら、確率的にどこかで勝てる。

[リファクタ]
済・壁が置けるかどうか、盤面で明示的にわかるのでboadで持つ。
済・outMap判定が無駄なので、周囲1マス壁の32*32盤面で持つ。

ふくちゃんさんの
境界線上4択できるのがいい。

ymatsuxさんが4.8Gで1位。
これは結構サチってきた。

### 2/15
ymatsuxさんが5.3Gで1位。
### 2/16
debugできるようにコメント機能を使って、入力を全出力するようにした。
適当に追っかけて、seed=0は全部捕まえられた。
62Mなのでこれでも悪くない。

seed=1は 8/20 しかできない。
やはり猫を追いかけてしまうと不毛。
次に全部捕まえられたのがseed=82、しかも猫は偶然大きく囲えただけ。
犬と同じように上手く捕まえる仕組みが必要。
猫の特性上、エリアの広い所に行くので、わざと狭い通路を作ってやると良いかも。
極端なものではこんなの。

真ん中で区切るので、犬もそこで捕まえる。
真ん中に幅2マスの筒を作って、そこで捕まえると高さが稼げそう。
いや、やはり斜めに切り取るのがいい。
四隅で犬を捕獲したあと、斜めに沿って道を作る。

猫を移動させたいので、猫のいるエリアの動物から捕まえる。

### 2/17(木)
こんな感じ。左下が犬用。
小道は13本作れるので12匹の猫はなんとかなる。
確率上、それ以上は考え難いが、最大の猫19匹犬1匹のパターンはテストした方が良さそう。
ここまでできた。

### 2/18(金)
1位、eivourさんが来た。5.56G。
Terryさんが奪還。5.76G。

猫を捕まえる。

### 2/19(土)
phocomさんが奪還。5.91G。
猫を捕まえる。
とりあえず組んだけど、時間がかかりすぎる。
犬を捕獲してから右上まで埋めるのが苦しい。
左下の捕獲と右上の壁は先に作る。
左下、一段上げた。

seed=5、ラスト1匹が最後まで通過しなかった。

seed=0~99で12ケースで猫を逃した。
唯一うまくいったseed=16、78Mなのでめちゃいい。

猫の逃す確率を下げたい。
こんな風に、別の動物に邪魔されがち。バリケードを作るか？
バリケード。
だめ、巻き込み多発。ベースの回転が必要かも。
ToDo
済・猫が近い時、通路からどく。
済・ひとつ伸ばすか
済・置いて猫が閉じ込められるなら置く。
済・壁は先に置いちゃう。(暫定)
済・中央線に対して動物よりも手前にいる状態で置く

[アイディア]
☆犬1匹の時は、猫と同じ扱いで良さそう。
済・やはり大雑把に区画で区切って広範囲を閉じるやつを考えた方がいいか？

### 2/20(日)
猫は最初が一番の捕獲時。

フリー捕獲は、一番中央踏切に近いやつからにする。
↓赤い点が中央踏切。

ToDo
済・捕獲対象を中央踏切から
　→1/3は60Mが出るようになった気がする
済・スコア計算をちゃんと作る
済・スコアの平均を出せるようにする
　→0～99でave31M。3Gはいってる。
☆・猫の4人体制

今、猫未捕獲エラーは0~99で3ケース。
いずれも猫が多い。初動4人体制が必要。

とりあえず、フリー捕獲の確度を上げていく。
30M代の1匹逃している系を詰める。
済・残りターンが無くなってきたら、捕獲ラインを上げる。
済・一度に複数確保できるならその分捕獲ラインを上げる。
　→0～99でave43M。4Gはいった！
済・猫用の通路、余分にもたせて他動物も捕獲する。
済・猫用の通路、置ける壁を置いて閉じ込められるなら置く。

TERRYさんが奪還、5.98G。

兎とかだと、追いかけっこが始まっちゃうので下図黄色があるとストッパーになりそう。
0～999の1000ケースやってave42M。

済・ストッパー実装
　→不整合がいろいろ起きたので、点数低いやつから確認。
　→うーん、不要かも。ストッパー無しで。

点数が低いのは、動物が17以上で犬の少ない巨大ケース。
犬以外の動物数で確認する。
→犬以外で15以上になると大変っぽい。
　ただ、犬以外が少なくてもダメなやつもある。確認。
→猫担当のバグを回収。47M。

TERRYさんが6G！6.01G。

☆・最後に引いて広く閉じ込める

→いくつか調整して。48M。

数が多い時の埋め込みを考える
iehnさんの54M。
https://twitter.com/arimasenu/status/1495032396563226625

犬を捕まえてからだと賢くやらないと間に合わない。(300ターン)

強実装だなぁ。。。
先にコードテスト。
AtCoder環境で1000ms、300MBくらい。
余裕はありそう。

埋め込み。seed=1で250で敷き終わり。
ぎりぎりかなぁ。。。
3段だと足りないから、斜めに通路の入った2段にしよう。
犬がいないから通路に居座ることはないはず。

### 2/21(月)
2段これでいく。同じく赤点が始点。

動物がいる所だけ生成したらいいかも。
必ず壁から作って、途中で捕まえられるする。
壁側に生成開始点を置いて、必要になったら都度指示する。
壁を作りきった時にフリータイムにして、近くに捕獲可能な動物がいたらする。

### 2/22(火)
2段の埋め込みを作る。作った。
けど、そう上手いこといくわけじゃなさそう。
まだ詰めは必要だけど、安定して20M以上がでるわけじゃない。1Mとかもある。
メイン戦略側に妥協案を入れたほうが良さそう。
いちおう埋め込みだけで0～999でave40M。

犬以外が17匹以上の条件でかけたら、48.8M。全然あがらん。

やはりメイン側で妥協案を考える。
やばい系のときだけ埋め込みで。

0～99で、31ケースが捕まえきれてなく、13ケースが残り1。
これを減らす方向で考える。

[アイディア]
・最後にのこった動物を丸ごと閉じ込める。
・最短経路を右手法と左手法でやって、互いの距離が最も近い点が節になる。節を見つけて塞いでしまう。

### 2/23(水)
メイン処理の詰め。
済・基礎作りきる前に猫の捕獲体制に入る。
済・猫の通路に入った動物は、猫捕獲完了後は通路にも壁を置けるようにする。
その他細かい挙動直して、ave51.6M。

どうもまだフリー捕獲の挙動が甘すぎて、単純にターンが足りてない。

済・とりあえずラスト20ターンは壁置きまくり作戦
　→だめだった。
済・中央線付近の壁設置許可をちゃんとする
済・targetの動物より、中央線に近い位置に戻る
済・捕獲マス調整
　→10マスまで下げて52.1M。
済・同時置きを考慮
済・終わりが迫ったら、手前の動物まで下がる
他、挟み込みの差異のバグなんかを直してave53.1M

初期の壁の効率が結構大事かも。
犬捕獲までで130ターンかかっているケースがあり、それだとターンが足りなそう。
→設置順序を壁を考慮した順序にしたら、ave54.2。
　先に全体効果のあるこっちからやるべき。
→複数人巡回セールスマン問題とはちょっと違いそう。
　犬の誘導があるので、左下の滞在が長い方が大事。
→一列残していたのを、最初から埋めてave55.1M。

seed=51、猫を捕まえて214ターン目、残りの動物が多すぎるので大きく囲いたい。
例えば、ラインを引き、間が空かない範囲で狭めるのとか。
人は必ずラインより中央線側にいるようにする。
→実装がどうも興が乗らない。。。
→壁を急いで張るなら、斜めより縦横の方がはやい。

[アイディア]
・初期配置をちゃんと考える
・猫通路にいるやつを猫と同じように挟む(偶然じゃなく狙う)
済・捕獲ラインを状況に応じて上げる
→だめだった。10マスがベストっぽい？
済・兎はもっと前から壁をはる
　→上がった。55.4M。
・確殺処理を考える。
　そこに置けば捕獲できるのが明確にあるなら、優先的に対応する
・取れるケースをしっかり点取るのも大事そう。
　→壁を置かずに待つようにするとか。設置条件変えるだけだと厳しい。
・抜け出しを防ごうと、通路を作ってしまうことがある。
　通路は置くと完全に塞がるので、先にいってる人が帰らないとおけない。

猫用の通路の終点判定がバグってた。
→直したら点数が下がった。太い所は置かない方がいい？

### 2/24(木)
1万ケース走らせてcheck。
済・中央線潰した時の挙動でエラー
済・中央線周りの挙動でエラー
・最後まで犬を捕獲できないseed=7070、8446、9131
　→レアすぎるので置き

エラー個別になおして55.45M。
1万ケースでは55.27M。
捕獲ラインの段階を増やした10→30→100。55.66M(1万ケース)
こっから4M上げるのにどうするか？
→事故をへらすしか無い？

序盤に中央線付近に居座られると動けない。
済・CAT要員がいるなら無視で良さそう。
済・左上と右下のエリアに動物がいるなら最低一人ずつ付く
→56.24M
その他直して56.48M

済・ラスト、閉じ込められるところまで下がる、seed=1
・犬1匹の時は、もっと狭い範囲でやる。
・最後一人閉じ込めても最大で20%減なだけ。半分以上減るよりありでは？
・初動、priolityQueに人を入れて左下到達ターンの短い人から壁を割り振るとか。

### 2/25(金)
1万ケース走らせて、2件エラー直して55.80M。
→さらに直して55.79M。

済・最後、閉じ込められる地点まで下がる。下がる途中でもっと近い所も見つかるはず。
→seed～99は60M出るけど、seed～999で56.0Mになる。
・特に中央線付近の牛を追っかけて壁を張っていくと幅1の通路になり、牛が邪魔で塞げなくなる。

今、1000ケースで56.12Mになっている。

とりあえず確殺無しのもので提出。57.51M。
テストケース側の方が甘そう。
あとの時間を確殺を磨くのに使うか、個別ケースを見ていくか。
初動の順番をちゃんとするのやりたい。犬捕獲の平均ターン数ではかるか。

[アイディア]
・犬の捕獲、端まで壁で埋めると詰まりやすい。どうせ近くにいくので開けておくとか。
・確殺点まで下がっている間、塞ぐと美味しい場所がある場合は塞ぐ。
済・確殺点が中央線まで下がる時は諦めて囲い込みを狙う。
・中央への最短経路の各マスから壁を伸ばして、壁数の少ない箇所を探すとか。

確殺ありで1000ケース56.30M。こっちでいこう。

### 2/26(土) 最終日
1万ケース走らせて、エラー直して56.27M。よし。
エラーなおしたので100ケース、60.42M。
48: R= 1
50: Low= 7M
51: R= 6
3件しかでなかった。
1000ケースで、56.62M。
1万ケースで56.38M。

犬捕獲のやつやる。
seed～99で、一番おそいのが83の129T。
やはり壁の設置順が遅そう。
いま犬捕獲の平均ターンが96turn。

seed～999でみたが、dogoutの遅さとスコアの低さが連動してる。やはりこれが効果的っぽい。

済・最終左下に到達するのが早い人から、未設置壁のうち近いものを貪欲で取っていく。
　→53M、賢くない。
済・上記を後ろに追加ではなく、ベストな位置に差し込むようにする。
　→54M、人同士が離れてたほうが良さそう。
・右上だけじゃなく、左下の初期ポジを入れる
→初期位置が壁の人が悪さしてた。
→どうしても無駄な移動をしてしまう
→最後に残るやつが厄介なので、最後の数個は最短で振るとか。
→やっぱだめ捨てる。
犬捕獲の平均ターンはseed～99で94turnになって、スコアも微増。

残り1時間。
1000ケースやって56.8M。
犬の捕獲口あけるやつやるか。
→ときおりいいけど、色々と悪化するポイントもわかったので取り下げ。
　犬の少ないケースなら刺さってそうだけど調整できん。

1000ケース56.8Mの出して終了。
seed=1はこんな。50M
抜群に上手く言ってたのがseed=82。82M

暫定順位

[反省]
最終日は初期壁配置が、謎の最適ルールになってたっぽいのに気付かなかったのが敗因。
フリー捕獲と、ターン数が足りない時の妥協に手を入れたほうが伸びた。
方針は当たってたと思う。
かなりスパゲッティコードになったのと、if文ミルフィーユをやってしまった。
もうちょっと綺麗な評価ができればいいんだけど、細切れにやるのは難しい。

それにしてもwleiteさんとTERRYさんのデッドヒートが熱かった。
3回くらい変わってた。

## 感想戦
wleiteさんもTERRYさんも、直線で短冊を作って効率的に囲うっぽい。
https://twitter.com/terry_u16/status/1497512298100838400

4マス確保しているのは豚用っぽい。
TERRYさんは小さいケースでフリー捕獲もやってるとのこと。

もっとヒューリスティックなアプローチが強いと思ってたけど、違った。

これ好き。犬猫より圧倒的牛。
https://twitter.com/_phocom/status/1497514826418900993

wleiteさんがいつもの作ってくれてた。
https://twitter.com/wleite/status/1498796559747665921
https://tc-wleite.github.io/ahc008.html
こうみると、小さいケースで最強でやはり動物が多い時が弱かった。
埋め込み方式で切り替えるのは良かったが、そっちの詰めが甘かった。