RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜

暫定スコアは203,976,037点。98位。

追記: 本番スコア 4,076,304,118点。99位。

動きの様子。

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 203,540,639点 暫定98位
運で飛び賞の賞品当たってくれ～ #R_proconhttps://t.co/o54fhQhhPv pic.twitter.com/H2pKaKj8S7

— kusanoさん@がんばらない (@kusano_k) September 12, 2021

やったこと

• ビーム幅333のビームサーチ
• 盤面の評価関数は、
  • 資金
    • 840ターン未満は、所持している資金＋収穫機の購入に使った金額（総獲得金額）
    • 840ターン以降は、所持している資金のみ
  • 収穫機の存在する区画で、この先の一定（＝現在の収穫機数とした）のターンに生える作物の金額の合計
  • 収穫機の存在する区画に隣接する4区画で、この先のターンに生える作物の金額の合計
  • 乱数
  • 上のものほど重みが強い
• 収穫機は常に全て隣接させ、木にする
  • 木にすることで、収穫機を取り除いても連結かどうかの判定が、次数が1かどうかだけになる
    • 最終的に、連結している収穫機を数える処理が、ソースコードから消えた
  • ただし、2x2の区画のうち3区画に収穫機があるときに、残り1区画に置いて田の字にする or そこから取り除くのは許す
• 移動元は、移動先ごとに1個ずつランダムに選ぶ
• 840ターン未満ならば、収穫機を買えるときは常に買う
• 840ターン以降は収穫機は買わない

感想

2億点を超えている上位陣の解法を見ても、わりと皆やっていることが異なっていて、問題のバランス調整がすごい。

しかし、そうなると、自分に何が足りなかったのかが良く分からない。1位は2.8億点超えで、大きく負けている。上位陣が皆同じ事をしていれば、それが足りなかったということなのだけど……。

動いている様子を見ていても、高得点の作物を取り逃しているので、それを取りに行く何かが必要だったのかもしれない。探索だけだと深さが足りないので、評価関数で頑張って遠くに取りに行くとか、収穫機を良い感じに配置するとか。作物の価値は一様ランダムではなく、価値の対数が一様ランダムなので、高価な作物は数が少ない。

作物の価値の図。

時系列で詳細

コミットログを見ながら、だらだら書いていく。

問題考察

まずは問題を眺めてみる。

フィールドにランダムに何かが発生して、それを集めるという、定番っぽい問題。ただし、収穫機が連結していればその数が収穫時のポイントに乗算される。（え、どういうこと。収穫機が集まれば収穫能力が上がるというのは分かる気がするけど、収穫機が1個でも1ターンで作物は消えるんだよな……。まあ、どうでもいいか。）

作物を多く収穫する → 収穫機がたくさん買える → 収穫できる作物が増える×収穫金額の乗数も増える　というループが回るので、コードの少しの差がスコアに大きく響きそうな問題設定。普段のAtCoder Heuristic Contestは、適当なコードでも1位の半分くらいの点数は取れる設定になっていることが多く、それとは異なる。「1位のスコアの半分。これは方針が全然違うのでは？」みたいな感覚が狂う。

長期コンテストは1%未満の差を競う感じになりがちだけど、今回はそうならないよう、スコアが派手に変わることを意図して調整してみました（点が突然倍になったりしたら、楽しいので）#R_procon

— tomerun (@tomerun) September 12, 2021

意図的にこういうスコアにしていたらしい。たしかに、最初のほうでスコアの桁が増えていったのは楽しかった。

焼き鈍し（1,434,474点）

ビームサーチしてくれという問題に見えるけれど、ビームサーチつらそうなんだよな……。移動させる手は、（収穫機のある区画数）×（収穫機の無い区画数）通りあり、数万とかになる。こんなんまともに動かないでしょ。「焼き鈍しか～？」と（このときは）考えていた。

とりあえず、出力する手順をそのまま焼き鈍し。移動先に収穫機が無いなど、不正な手順になってしまったら弾く。全然スコアは取れない。まあそうでしょう。

焼き鈍し考察

ランダムに変更した移動する手がだいたい不正な手順になってしまうのが一番の問題。移動元を、座標ではなく、どの何番目にかった収穫機か？にしたらどうだろう。こうすれば、不正な手にはならなくなる。

今回の問題では、最後のほうを除いて、収穫機が買えるときに買って損することは一切無い。移動の手があったとして、そのターンで収穫機が買えるならば、移動先に買った収穫機を置けば、移動元に収穫機が残る分だけ得。

なので、収穫機を購入する手をなるべく前に移したい。移す先がパスならば簡単。そうではないときも、上手く工夫すれば、収穫機の存在する区画が真に増えるようにできる。

伝わるだろうか。横軸が時間、縦軸が区画。

逆に、手順の変更によって買えるのが遅くなったときは……どうするんでしょうね。

面倒そうなので、結局実装はしなかった。

移動先の配列を焼き鈍し（75,768,308点）

（移動元は無しで）移動先の配列を焼きなますことにした。この移動先の配列から、収穫機を購入可能なときは購入する、購入不可能ならば最も最後に移動した収穫機を移動元にして、実際の手順を生成する。どのように書き換えても、（移動先にすでに収穫機が存在するとき以外は）validな手順となる。

収穫機を買えるときには常に買っているので、このままでは、良い手順になって獲得資金が増える → 最後の最後に高額な収穫機を買ってスコアダウン　ということが起こりうる。評価対象は、総獲得資金（所持資金＋収穫機の購入に使った金額）しよう。この評価方法で焼き鈍し、最後に、後ろから順に収穫機を買わなかったことに（＆この収穫機の移動をパスに変更）して、終了時の所持金額最も多かったものを最終結果とすれば良い。

スコアが50倍以上になった。すごい。それでもトップの1/3くらいだけど

最も古い収穫機を常に移動元にしているところ、移動先の配列に、移動したこととして移動元として選択されるのを遅らせるみたいな情報を追加すれば、任意の手順をこれで表現できるかな、とか考えていた（未実装）。

ビームサーチ（77,530,801点）

焼き鈍しの初期値は、左上から右下まで順に舐めていくのを繰り返すものだったのだけど、これがだいたいそのまま残っていることが多かった。これを見て、ようやく、収穫機が連結になっていない状態なんて使いものにならないことに気が付いた。連結になっているという制約なら、選択可能な手もだいぶ減るので、ビームサーチができそう。

ちなみに、最初の数十ターンを手で解こうとしてみると、収穫機が一塊になっていないほうが金が稼げる。ここを別扱いで頑張るとどのくらい最終的なスコアが変わるんだろうな。ということで、10ターン目くらいに天からお金が降ってくるようにして動かしてみたけど、たいしてスコアは変わらなかった。連結という制約を外して探索するのは簡単だけど、後から連結に戻すのがちょっと面倒なので、常に連結ということにした。最初のほうは別扱いにしている人は多かったので、やるべきだったかもしれない。

雑に実装して焼き鈍しを超えた。ビームサーチのほうが将来性がありそう。

最後の100ターンは金額をスコアに（108,657,580点）

所持金額＋収穫機購入金額をスコアとして最終ターンまでの手を生成し、後から購入を無かったことにしていた。これだと、稼ぎどころの最終局面で、収穫用の収穫機が消えたり、連結がバラバラになったりする。最後のほうはスコアを変えれば良いだけだな。1億点突破

配列を2次元から1次元に

machine[N][N] → machine[N*N]。2次元扱いが必要な箇所って実はそんなに多くなくて、スコア計算とかでは2重ループを回すのが面倒なだけになることが多い。適当なタイミングで直そうと思っていた。

隣接区画との差分は、int d[4] = {-1, 1, -N, N}という配列で表せるのだけど、範囲外の対処が必要。

1. x = pos%N, y = pos/Nで一旦変換
2. 周囲一区画分壁を作る
3. 全区画について隣接区画をテーブル化

どれが速いかは盤面のサイズなどでも変わってくるはず。1より3が速かったので3にした。そういえば、2は試していなかった。まあ、せっかく16x16=256でキリが良いし……。

連結の判定方法を変更（112,904,449点）

「収穫機を移動 → 連結かどうか判定」としていた。これだと手ごとに連結判定が必要で遅い。取り除いても連結のままの収穫機を探して移動元とし、移動先は（移動元以外の）連結器と接しているかどうかだけ見るようにした。連結の判定回数が今盤面にある収穫機数になる。

こういう手が不可能になるけれど、まあ、そんなに変わらないだろ。

この辺でMLE。vector<vector<State>> state(T)みたいな配列で状態を持ち、次のターンに生成した状態を詰め込んで、ソートし、state[next_turn].resize(BEAM_WIDTH)みたいなことをしていた。resizeしてもメモリは解放されないからな。使い回し用の配列を使って、最後にBEAM_WIDTH個だけ移動するようにした。

スコア計算用スクリプトを追加

今まではいちいちAtCoderに投げていた。もうプログラム内で計算しているスコアにバグも無いだろう。50ケースで実行してデバッグ用に出力しているスコアを集計するスクリプトを書いた。以降の点数は手元の50ケース。

諸々（126,059,342点）

同じ状態をビームに残しても無駄である。そのためにハッシュ値を計算して、同じものは弾いていた。盤面の状態は、作物と収穫機の配置である。作物の状態って、収穫したものはお金に変わっているから、お金だけ見て高いほうだけ残せば良いよね。ということで、収穫機の配置だけをハッシュ対象に。

状態を入れているmap<Hash, State>をunordered_mapに。普段は気にしていないけれど、そういえば、std::mapは要素をキーでソートした順で保持するから遅いんだった。

移動元最大8個×移動先　で手を生成していたけれど、移動元なんてどれを選んでも良くて、8個も要らないだろ。3個に。代わりにビーム幅を8から32に。

最後100ターン以前は、収穫機を買えるときは、買う手だけ生成している。最後100ターンは、買う手＋移動。買うというのは移動元が-1の移動としていた。で、他の移動元と同様にランダム3個の中で選択対象にしているけれど、選ばれない場合も多い。常に選ばれるようにしたほうが良いかな。

収穫機を買わないようにする閾値を調整（135,918,124点）

そういえば、「最後100ターン以前は収穫機を必ず買う」の、100ターンは適当に決めた値だった。手動パラメタ調整。

850ターンで。

将来の作物を考慮（142,870,393点）

そりゃ考慮したほうが良いだろう。ある収穫機を次に移動するのは、収穫機数ターン数後くらいになる期待値が高いだろう。ということで、収穫機ターン数後までの作物の金額を追加。収穫機数を掛けてはいない。このくらいでバランスが良いか？　累積和をあらかじめ計算しておいて差分計算。アルゴの知識が生きる。将来に行くほど指数的に重みを減らして足し合わせるとかがもっと良さそうだけど、累積和での計算ができない。

ついでに、周囲4区画分も加えるようにした。

最後のほうで収穫機を買う手は無し（142,870,393点）

収穫機を買う手は常に生成するようにしたけれど、冷静に考えてみると、この時点での評価関数は所持金額なので選ばれるわけが無いな。無駄。事実、購入する手は全く選択されていなかったのでスコアの変動は無し。

移動元を3個から1個に（156,232,868点）

ついでにビーム幅を16から32にしているけど、これが無くても減らしたほうがスコアが伸びた。

良い移動先があったときに、その移動先の移動元3個分がビームを埋めちゃうんだな。

移動元を移動先ごとにランダムに選ぶ（174,704,823点）

移動元をランダムに1個選んで、それに対する移動先を生成していたところを、移動先に対して別々にランダムに1個移動元を選ぶようにした。

これでスコアが大きく伸びるということは、移動元もけっこう重要で、ランダムなどではなく、もっとちゃんとするべきだったのでは…… 　最後までこれはこのまま。

ここでビーム幅を32から48にしているので、その分もある。

ソートを高速化（180,555,964点）

Visual C++でプロファイルを取ってみたら、ソートが遅かった。vector<State>をソートしていたので、vector<State *>をソートするようにした。だいぶ速くなったので、ビーム幅を48から64に。

高速化（188,705,290点）

bool machine[N*N]を舐める処理が地味に重かった。収穫機の位置の配列を用意するようにした。ビーム幅を64から96に。

収穫機の配置が木になるようにする（192,857,373点）

移動元の選択にしか使っていないとはいえ、収穫機が連結かどうかの判定が重い。

収穫機を木にすれば良いのでは。つまり、

• 収穫機を置くときには、他の収穫機1個と隣接するようにしか置かない
• 取り除く収穫機は、他の収穫機1個と隣接しているものだけ

実際、動いている様子を見ていても、サイクルができていることなんてほとんど無いし。

ただし、2x2だけはときどきあって、その分スコアが若干落ちるので、2x2はがんばって許容する。

連結している収穫機を数える関数が消えた。気持ち良い。

だいぶ高速になったので、ビーム幅を96から128に。

これが締切り前日32時。

ビーム幅可変

起床。もうアイデアが無いな……。

最初か最後のどちらかだけ、ビーム幅を増やすというのはどうだろう。収穫機台数が後々まで効いてくる最初のほうか、作物の金額がインフレする最後のほうか、どちらが重要なのか良く分からん。試すしかない → どちらを増やしてもあまり変わらず。まあ、そうなるようにバランス調整がされているか。

高速化（201,204,109点）

そういえば、移動先ごとに移動元を1個にしたことが効いているのか、同一盤面がほとんど生成されなくなったので、map<Hash, State>は削除。

あと、ソートとかの処理が地味に重くて、要素数を見たら1万個近くになっている。スコアの低い状態は後から捨てるだけなので、現在保持している状態のスコアを別にsetに持って、その最小値よりスコアが小さい状態は配列に突っ込むのを止めた。

ここら辺の高速化で、ビーム幅を128から256に。2億点突破

購入しない閾値を調整（202,675,534点）

スコアが伸びた分、最適な閾値が変わっているかもしれない。

スコアが伸びると、最適な閾値は速くなるのか？　あるいはたまたまか。信じよう。850 → 840。

ターン数ではなく、収穫機の台数、あるいはその組み合わせという手もある。でも、試してみても、スコアが減るか全く変わらないかなので止め。

考えてみれば、全ての入力で一律の閾値にするというのに無理があったのかもしれない。入力ごとに閾値を複数通り試している人もいた。

ビーム幅増加（205,268,726点）

256 → 300。

ビーム幅増加（203,259,572点）

まだ行けるかな？　300 → 333。

ビームサーチ、焼き鈍しと比べてTLEの心配があるんだよな。いや、ビームサーチでも、chokudaiサーチなり、ビーム幅を時間を見ながら変えるなり、緊急用に時間オーバーしそうなら打ち切ってとりあえず何らかの出力をするなり、手はあるのだけど、アルゴリズムに時間がそのまま組み込まれている焼き鈍しよりはちょっと面倒。まだシステムテストが終わってないので、一抹の不安はある。