RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 参加記
問題
結果
最終5,214,965,972点で14位。暫定は259,015,342点で17位。
解法
収穫機7個以下の時
収穫機が少ない時には、価値の高い野菜に直接移動した方が効率が良い。ポリオミノの置き方を全列挙し、一番資金を稼げる配置を計算する。ポリオミノの最後の1個が、その時点での盤面で価値最大の野菜に置かれるように限定する。
収穫機8個以上の時
連結を保ちながら、次に取る野菜へ移動させていく。次にどの野菜を取るかをビームサーチで探索する(ビーム幅12)。次にどの野菜を取るかを決めたら、そのノードはターゲットの野菜を取るまでターンを進める。考えるべきは、ビームのソート方法・次にどの野菜を取るか・どの収穫機を動かすか・収穫機をどこに動かすか・収穫機の購入をいつ止めるか、の5つ。
1. ビームのソート方法
収穫機が多い順、同じなら資金の多い順にソートする。
2. 次にどの野菜を取るか
基本的に価値の高い野菜を取りたいが、遠すぎると効率が悪くなる。なので、距離d・価値vの野菜の評価値をv*0.8dとして、評価値の高い野菜3つを次に取る候補とする。距離が収穫機の個数より遠い野菜はそもそも候補に入れないようにした。
3. どの収穫機を動かすか
取り除いても連結性が保持されるものが候補となる。候補が複数ある場合は、動かさなかった場合に次に収穫される野菜の価値が最小のものを動かす。次に収穫される野菜は、収穫機の個数ターン先までしか見ない(例えば収穫機が10個だとして、その収穫機が50ターン後には同じ場所にはいなさそう)。
4. 収穫機をどこに動かすか
ターゲットの野菜までの最短のマスに動かす。候補が複数ある場合は、どれを動かすかの時と同様に、そのマスで次に収穫される野菜の価値が最大のマスに動かす。次に収穫される野菜は、収穫機の個数ターン先までしか見ない。
5. 収穫機の購入をいつ止めるか
購入を止めるタイミングを830・840・850ターン目の3パターン試して、もっとも良かったものを採用する。830〜850にしたのはその辺りで止めるのが最適なケースが多かったから。個数ベースではなくターンベースなのは、ビームサーチと相性が良いから(実装が楽だから)。
ざっくり時系列
1日目
問題を読む。当たり方針思いつかないと勝負にならなそうなので、思いつけるように祈りを捧げながら眠る。
2日目
連結を保ちながら動かすのが良さそうと思い実装する。次にどの野菜を取るかは適当に評価値を決めて貪欲に取っていく。226Mで5位くらい。とりあえず良さげな方針を思いつけたので一安心。
3・4日目
評価値を色々いじるけど、最初の適当に決めたのが強すぎて改善できない。
5日目
ビームサーチを実装して247Mで順位表1ページ目に戻る。いつもずっと2ページ目にいるから気分が良い。
6日目
細かいところを改善して253M。土日が残ってるけど、アイデアは尽きて本質的な改善はもう無理そう。
7・8日目
ひたすら1000ケースでのパラメータ調整と、バグ死しないか大量テストケースでチェック。259Mまで上がる。
反省点
やっぱり上位勢と比べると工夫が足りない…。未来を考慮したマスの評価とかもしたけど上手くいかなかった。シンプル解法+パラメータ調整で赤行けるかみたいになってきたな。
