2/11(日) に行われた第2回RCO日本橋ハーフマラソン予選でやったことを時系列順に書き下しました。
コンテストページは こちら 。
コンテスト前
意気込み
年に数度の社会人オンサイトチャンスなので全身全霊頑張っていく所存。
まず、シンプルな山登りをバグらせずに(重要)実装すること。これで順位表半分より上には食い込めるはず。
それに一工夫加えて粘れば予選は通れるんじゃあないかなあ、という予想。
総合順位が A, B 問題の順位の掛け算ということもありどっちかでコケたら終了するので、無難に、無難に。
準備したこと/もの
- マラソン用テンプレート
- 高速な乱数生成ロジック(xorshift128)
- 時間測定用のほげほげ
- java 環境動作確認
- 前回のハーフマラソンのテストケース生成器が動くことを確認した
- 順位表スクリプトの導入
- ルールの確認
- メモ用紙 / 方眼用紙 / 筆記用具
- 糖分の摂取
コンテスト中
コンテスト開始 ～ 開始 45 分後
A 問題をやっていく。
こういう系はランダムウォークさせるだけで結構動き回ってくれると直感が言ってるので、とりあえずスムーズに実装できそうな以下を書いてみる。
- ランダムに盤面を K 個選ぶ。
- 4 方向のうちいずれの盤面でも罠にかからない方向をランダムに選び進める、を T ターン繰り返す。
- 1.〜2. を時間いっぱい繰り返し、一番スコアが良かったものを出力する。
これ自体は 30 分程度で実装でき、スコア 95032 で A 問題暫定 1 位。
2 位が 3 万点台で割と差があったので B 問題に移ろうとするも、20 秒後に 18 万点が出てきたのでもうちょっと詰めておくことにした。
今の方針だと山登りですらないので、罠にかからない方向のうち得られるコインが一番多い方向へ進むようにしてみる。
10 分程度で改修が終わり、スコアは 188285。順調。
～ 開始 1 時間半後
B 問題をやっていく。
基本的にランダム性を加えた山登りを時間いっぱいたくさん試すのがコスパ最強だと思ってるんだけど、この問題ではそういう方針の解法が思いつかない。
セクタ数、スワップ数的に数回山登りするくらいが時間的に限界じゃないかなあ。
何も良い方針が思いつかないので、とりあえずスワップ処理を実装するがてら 0～1599 のセクタを順番に並べるやつを書いてみる。
途中バグらせてタイムロスしつつ、開始 1 時間半後くらいに提出ができた。
スコアは 183251 で順位的にも真ん中くらいなので、さすがに周りは何かしらやってそう。
A 問題に提出したやつが 3.2sec くらいで終了してたのでもうちょっと攻めた時間設定にしてみるも、これは 600 点くらいしか伸びなかった。
ただまぁ総合 1 桁順位をキープできてるので心に余裕はある感じ。
～ 開始 2 時間半後
B 問題の考察を進める。
ある点について考えたとき、その点が前後の点の中間のどこかに位置すれば、前後の点との距離の和は最小になるはず。
なので、一番スコア悪化の原因になってる点を見つけて、前後の点の中間に放り込んでいけば良いような気がしてきた。
バグらせつつも上記のロジックを完成させ、スコアは 309918。この時点での B 問題の順位は確か 15 位前後だった気がする。
～ 開始 3 時間半後
B 問題が他に何も思いつかない、かつ A 問題の順位が少しずつ落ちてきたので A 問題にスイッチする。
今はかなり単純な貪欲(1ターン先しか見ない)をやってるので、ここを改善すると伸びるはず。
ということで、2 ターン先まで見る貪欲に変えてみる。
これが割と正解だったようで、スコアは 18 万点台から 20 万点後半まで伸び、総合順位も 15 位前後まで返り咲くことができた。
～ 開始 4 時間後(コンテスト終了)
A 問題を 3 ターン先まで見る貪欲に変えてみるも、スコアが落ちた。
実装が突貫(3重ループを書いた)すぎてバグか方針ミスなのか判断付かないので、諦めた。
後は乱数のシードを変えて提出してみたり、貧乏ゆすりしながら順位表を眺めたりしていた。
結果
A 問題 20 位、B 問題 50 位の総合 32 位でした。
予選通ってると良いな～～。
