RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 に参加しました。
問題は農場王X。連結成分を動かす問題でした。
暫定スコアは218M点で提出519人中80位、システスはまだです。
問題
16×16のグリッド上に野菜が生えてくるので、収穫機を置いたり動かして収穫してね。
収穫機は連結すると収穫時の収入が連結数倍になるよ。
1つの野菜は1～20ターンくらいで枯れて、全体ターンは1000だよ。
良かった、100ターンで岩になる野菜なんて無かったんだ。
考察
毎ターン平均5本生えて、平均10ターンもつので、任意の日に野菜が50個ある計算。
50/256は多いので、終盤は入れ食い状態になりそう。
となると、連結数を保ったままヘビゲームのように動くのが強いかな。
ただ頭と尻尾を固定する必要はなくて任意の場所に動かせるので多頭ヘビゲーム…ヒドラゲーム？*1
それから、空きマスを右往左往するのは弱いので、野菜に近い状態が嬉しい。
もっとしっかり言うと、多くのセルに対して近い状態が良い。
団子になるより、伸びた方が嬉しい。これはMM128っぽい。
全マスに対してM手以内にアクセスできる配置にして、そこから小さい操作を繰り返すのが強いとかありそう。
実装
現在～収穫機数(+購入1)ターン後の状態の野菜を見て、
遠隔地にジャンプするパターンとヘビ移動するパターンでそれぞれ収入を計算して貪欲。
遠隔地ジャンプは雑計算で、ヘビ移動は移動を縦横それぞれ1方向に限定したDP。
ヘビ移動は1ターンあたりの利益が高いマスに向かって動くが、利益があるマスまで移動したら一旦停止して再考する。移動元は塊を壊さない中で目的地に近く、将来の利益が低い場所とする。
ここまでやって約2億点。
あとは以下のような改良をするしかなさそう。
・読みの精度を上げる（主に移動元）
・複数手読みする
・お気持ちで良い感じに誘導する
全部それぞれ問題があって、移動元のシミュレーションは厳密に最適解を出すには処理時間がきつく、複数手読みも何をもって1手にするかが上手くはまらないと延長線上の2つを選ぶだけになり、そもそも移動元が正確でないと複数手読んだところで精度が低い。お気持ちパラメータは調整地獄。
上手く方針が定まらず、以下のようになった。
・全マスに4手でアクセスできるように固定盤面を作る
・消滅までの余裕ターンごとに0.1%ペナルティ
・将来の見込み的なものをお気持ち評価に加える
将来の見込みは移動完了後に出現する次の野菜の[価値/出現までの時間]や、将来的に固定となる場所に極小の固定値を加算。
固定盤面はこんな感じでH字に。上下端まで固定する設定にしているけど、偶然踏んだときに固定するので上下端まで固定されないことも多い。水平部分は収穫機20で固定されて、垂直部分は収穫機が増えるごとに少しずつ固定する。
没方針
・移動元の利益を逃す分も計算する
速度の都合で前計算と実移動で別ロジックを使った結果、外した方が強い状態に。悲しい。
・DP範囲を遠くまで伸ばす
遠い≒不味いで、短い動作を複数することも考慮できなくなるのであまり効果が無い？
・序盤のジャンプ移動を上手く連続動作できるようにする
色々やってみたけど誤差レベルだった。
・購入を連続動作の途中でも可能にする
何故か劣化した。なんで？
・出現待ちを伴う挙動は避ける
劣化した。
・複数手読み
移動元の計算を高精度でやるのが前提だったのと、確実に上がるビジョンが見えなかったので断念。順位表を見た感じ（コドゲ勢が強かったので）当たりっぽさはあったんだけど…。
他の人の解法を見て
収穫機の連結はUnionFindでチェックしていたが、グラフの関節点と橋を求めるという方法があるらしい。
あとはやはり、上位陣はビームサーチなどで複数手読む人が多かった。
感想
解法の自由度が高い分、実装は重いのに道が見えなくて苦しいところがありました。
DP+貪欲で取れる点は取った気がしますが、工夫で伸ばすフェーズがお気持ちばかりなのでもうちょっと何とかしたかったですね…。
しかし順位だけみるといつものAHCよりは順調で、やはりMMに近い問題だったなと思いました。
*1:それは別のカテゴリでは。
