RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜 に参加しました! atcoder.jp
1週間の長期コンテストだったのですが、今回はなんと3日分の休暇を使うなど、気合をいれてきました!
結果
最初に結果をドーンするのですが、初の景品圏内に食い込めるなど、自分としては出来すぎの結果でした!
システムテスト後では28位、5033282981点でした!!
祝!!景品ゲット!!!!
日本橋ハーフマラソン2021増刊号、お疲れ様でした!
— prd🦍 (@prd_xxx) September 12, 2021
システス前暫定29位、251089960点でした!景品圏内の快挙です!!うれしい!!
解法はそのうちブログに残しますが、収穫機が常に連結を保つのと、いつ購入を打ち切るかが鍵だった気がします!#R_procon pic.twitter.com/FPpudDv6kR
重要なポイント
今回大事だったことは、だいたい以下の内容だと思います
- 収穫機の購入をいつ打ち切るか?
- 最終的に持ってるお金でスコアが決まるので、終盤で買っても元が取れないとだめ
- どこかのタイミングから「買えるけど買わない」選択をする必要がある
- 収穫機が連結しているときのボーナスが強い
- 個連結していると倍になるので、できるだけ連結な状態を保ったままにしたい
- 評価関数をどうするか?
- 収穫機を配置/移動する際に何を基準として決めるか
以下、時系列順にやったことや考えたことを記していきます
序盤~1.3M
- 今回サンプルコードが提供されると聞いていたので、ダウンロードしてそのまま提出しました (開始1分、0.23M点)
- このサンプルコードが超有難くて、コーディング時間の短縮だけでなく、問題理解の助けにもなりました
そうそう、今回のマラソン、サンプルコードがついてきたのすごくうれしかった #R_procon
— prd🦍 (@prd_xxx) September 12, 2021
整ったGameクラスと、盤面やスコアのシミュレートが書かれてて、それだけで数時間節約された気がする。
最終的に count_connected_machines() くんはリストラしちゃったけど (連結前提のコードなので)
- とりあえずサンプルコードを動かしてビジュアライザで見たりしながら、ふむふむしてました
- あと、テストケース50個作って、スコアの合計を出すスクリプトを用意しました (AHC003のときの流用)
- 今回これを序盤で用意できたのは個人的に捗りました
- 収穫機の購入をいつ打ち切るか?の問題には早めに気づいたので、スクリプト何回か回しながらとりあえずサンプルコードで収穫機を12個で打ち切るようにして提出。→1.3M
16.1M
- 適当に貪欲っぽいのをかきました
44.0M
- 収穫機の購入を34個で打ち切るようにしました
63.6M
- ビジュアライザを見ると、なんか終盤に塊はできてくれてたけどなぜか下側のほうに溜まってく傾向があった
- 連結成分をもっと戦略的に動かしたい気持ちになりました
- 連結を保ちたい
- moveはとりあえず置く→取り除くの順で考える
- いままで置いたやつに隣接してる場所で良いところに置く→そこからマンハッタン距離で一番遠いやつを取り除く
- 連結を保ちたい
- 良いところ、の評価はすぐに獲れる野菜があればその価値、そうでなければ盤の真ん中に近いのをほんのり優遇しました
- 収穫機の購入は37個までに設定しました
107.5M
- これまでは隣接してるマスしか考慮していなかったので、遠くのマスも考えたくなりました
- まず多点BFSを使って、連結を保ちながらあと何ターンでその場所に収穫機を置けるか (=距離)を求めました
- それで、
vege.v
/ 距離 の値が一番大きいマスをターゲットとして、ターゲットへ1マス近づく選択を常にしました
164.8M
- ビジュアライザを見ると、ちょくちょく連結が切れてしまっているようだった。
- moveで置く→取り除くの動きの中で、マンハッタン距離で一番遠いやつを取り除いていたが、置いたマスから連結成分をBFSして一番遠いところを取り除くことにした。→151M !
- 収穫機の上限を48個までに設定した → 164.8M
167.1M
- 序盤のムーブを改善しました
- 収穫機が1個しかないときに、隣接するところにしか動けなくて、2個めをなかなか買えてなかった(笑)
- 収穫機が1個のときは瞬間移動させた
176.5M
- ターゲットマスを決める際の評価関数の調整をしたくなりました
- おおむねこんな感じ (伝わる??)
マスごとの評価関数、そこに収穫機があることで将来的にどれぐらい嬉しいか、を考えてて、
— prd🦍 (@prd_xxx) September 12, 2021
いまx日目でy日目にそのマスに収穫機を置けたとして、
Σ(day = y~x+65日) day日めに獲れる野菜のv / (day-x+1)
を評価に使った (獲った野菜は足さない)
- (ちなみにこのときは 65日先までではなくて30日でした)
- ついでにターゲットに1マス近づける選択をするときも複数のマスから↑の基準を使って選ぶことにしました
- さらに取り除く候補が複数あるときのタイブレークも↑の基準が低いのを選ぶことにしました
236.6M
- 取り除く候補として、置いたマスからBFS的に一番遠いところを選択していたが、そうでなくても連結の切れないマスはたくさんあることに気づいた
- グラフで言う関節点でなければ、取り除いても連結が切れないので、関節点を列挙することにした
- 調べた感じLowLinkを使うのが速そうだったが、持ってなかったので一旦UnionFindで自前で書いた
- 収穫機の上限も48→50へ変更
- 暫定8位!!
- 今回の問題では、このときの改修と、上述の評価関数の組み合わせが今回うまくハマったのだと思います
うおおおおお!!!
— prd🦍 (@prd_xxx) September 7, 2021
175M → 235M で暫定8位!! きたー!! pic.twitter.com/A6DqPJJMFf
247.1M
- 評価関数のなかで、何日先までの野菜を見るかは、えいや!で30に決めてたので、これを調整して65にしました
- たくさんスクリプトを回した結果65日先が良さそうだった
- ターン数や所持収穫機に合わせて動的に変えるのはうまくできなかった
- 暫定5位!!
- まだ2日目ちょっとなのでこの後どんどん抜かれるんですが、かなり舞い上がってました。
うおおおお!! 236M → 247M、 暫定8位 → 5位!!
— prd🦍 (@prd_xxx) September 7, 2021
とても興奮してしまう pic.twitter.com/s483P0IiBg
ボツ案たち
さて、暫定5位という上振れを引いてしまい、このあたりから有効な改善策がなかなか取れなくて6日目ぐらいまでほとんど伸ばせませんでした。。
このあたりで考えたり試したりしていたボツ案たちを供養したいと思います
- passを選択肢に入れる
- これは効果が薄かったので、超極端な場合だけ採用されました (ターゲットマスで獲れる野菜に1ターン以上余裕があり、取り除くマスの評価がやたらと高い場合だけ、passをする)
- ほとんど発動することはない
- 評価関数の式をいじる
- いろいろいじりました、分母を2乗したり3乗したりいろんな定数を足したり引いたり。→効果なし。
- move処理で取り除くマスを選ぶときに、置いたマスは除外していたが、あえて除外せずに、一致した時にpassをする。→逆効果
- 終盤、この収穫機を買うことで元が取れるか?をすごく考えた
- 1個あたりの収穫機が残りのターン数でどれだけ稼げるかを推定したくなった
- 野菜の価値はターン数の関数で表せるので、期待されるスコアをその関数で分割して計算したりした
- この作戦、いろんなパラメータを試したがさほど効果がでなかった。
- 1個あたりの収穫機が残りのターン数でどれだけ稼げるかを推定したくなった
250.0M
- 収穫機を50個に固定しているのがずっと気にかかっていて、テストケースによっては48個で買うのやめたり53個まで買ったりするのが良さそうと思っていました
- これまで幅1でシミュレーションして終わりだったので、終盤をビームサーチ的に複数のシナリオを走らせるのをやりたくなりました
- Gameクラスが肥大化してたので、リファクタして小さくしつつ実装がんばりました
- 幅5で提出したらTLEだったので、50,51,52の幅3で提出しました。これで250.0M!
- 幅3でも1799ms だったので、そろそろPyPyでの実行時間を厳しく感じてきました
251.0M (最終提出まで)
- 複数シナリオを並行して進めるのではなく、1つずつ終わらせるようにしました。(chokudaiサーチ的?)
- これで、幅を3に固定することなく、高速化の度合いによっては4つや5つのシナリオを走れるかも?
- 高速化
- UnionFindで書いてた関節点列挙を、LowLinkに書き換えました
- 盤面のシミュレートで使われていた
count_connected_machines()
くんをリストラしました (どうせ全部連結なので)
- 時間を計測しつつ回せるようになった
- ただ、手元環境はジャッジ環境よりだいぶ遅く、手元環境のスクリプト回すのがあまり意味なくなってきた。ジャッジに投げていくしかない
- 提出 → 250.6M
- 収穫機49個始まりにして提出 → 250.7M
- 収穫機48個始まりにして提出 → 251.0M (最終提出)
できなかったこと
- PyPyをRustとかに書き換えれば速くなってもうちょいスコア伸びたのかな? (到底まにあわなかった)
おわり
最終的に28位という自分としては出来すぎな順位がでてとてもテンションがあがりました。楽しかったです!!
あと、マラソンを頑張るといつも思うことですが、充実感がすごいですね。(つかれたけど)
今後もやれる限りがんばってみたい気持ちになりました!!