第2回 RCO日本橋ハーフマラソン 予選 - 第2回 RCO日本橋ハーフマラソン 予選 | AtCoder に参加しました。結果は16位で、青コーダーの自分にしては健闘。去年の本戦のパラレル | AtCoderでも2位という今後二度と取れそうもない順位が取れてしまっていたので、適当な解法をいかに早く投げるかが重要なこの形式は自分に合っているのかもしれません。
以下、問題Aと問題Bの思考ログです。実際はAとBを行ったり来たりしていました。
問題A - ゲーム実況者Xの挑戦
とりあえず完全ランダムに移動する解を投げて、6499点。
次に試したのは、制限時間いっぱいまで「ランダムな盤面選択＋ランダムに移動」を試して、点数がベストなものを選ぶ解法です。これで19677点。しばらくの間、なぜかマップの番号が1始まりであると勘違いしていたことが原因で点数の計算が合わず苦戦。実装完了まで1時間くらい無駄にしてしまいました。
次に、制限時間いっぱいまで「ランダムな盤面選択＋greedyに移動」を何度も試して、点数がベストなものを選ぶ解法を実装しました。ここで「greedyな移動」とは、上・下・右・左のうち、罠にかからない方向であり、かつ、コインがもっとも多くとれる方向を選ぶ移動法です。これで119800点。
終了間際に、「100個の盤面のうちよい盤面だけからランダム選択した方がスコアが上がるのではないか」と考えました。初期位置から取得可能なコインの数が多い盤面を良い盤面と定義し、100個の盤面から良いm個の盤面のみを使う方法を実装しました。しかし手元でmの値をあれこれ変えてもあまり効果は出ず、むしろスコアが下がることも。かろうじてスコアが上がった m = 95 を採用して、124540点。これが最終スコアで、52位でした。
心残り
本番中にvisualizerで挙動を確認すると、周囲にコインがなくなったときにプレイヤーの位置が振動してしまっていました。本番中に試しに2手読みを実装しましたが、かえってスコアが低下しました。バグがあったと思われます。
あと、たまにはランダムにプレイヤーを移動させることや、最終ターンが近づいたときに死人がでることを許容して移動させるようにすることも試そうと思っていましたが、記憶から落ちていたのと時間がなかったのとで実装できませんでした。
問題B - ゲーム実況者Xのデフラグ
最初は焼きなまし系の最適化問題かなと思いましたが、よく見ると、データの書かれているセクタ数16000に対してスワップ回数が4000回なので、半数以上のセクタは一度も移動されないということに気付きます。なので、以下の操作を4000回繰り返す解法に割と素直に行き着きました。
- 全データセクタについて、フラグメントスコア（＝そのセクタの前のセクタとの距離と、そのセクタの後のセクタとの距離の和）を計算
- フラグメントスコアが最大のデータセクタを選ぶ
- 選んだデータセクタのswap先を全通り試し、もっとも全体のフラグメントスコアが改善するswap先を見つけ、そことswapする
最初はswap先を空セクタに限定することでプログラミングの難易度を下げ、225356点。次に、swap先をすべてのセクタから求め、380776点。これが最終スコアで、7位となりました。最終解の提出直後は一瞬総合5位くらいになれたので、このときがいちばん興奮しました。
心残り
何らかのランダム性を追加してスコアが上がらないかとも一瞬考えましたが、Aの検討を優先しました。
次回に向けたメモ
- 「コードに加えた変更」と「手元のサンプルでのスコア」と「サーバのスコア」とをメモっておく。すると、手元のサンプルでのスコアをもとにサーバのスコアが予想できるようになる。各提出タイミングでのコードもコピーしてとっておくとよい。
- 上の状態を作るために、できるだけ早めに解答を作ってサーバに投げたい。とはいえ、あまりに簡単な解だと時間のムダかもしれず匙加減が難しい
- 手元のサンプルは基本的に最初からジェネレータに封入されている1個で十分
- Emacsはやめて最初からVisual Studioを使おう
参考URLs
- RCOスタッフによる模範回答
ハーフマラソン予選、私の回答です。A:302527/B:426768 （時間は無制限でやってます）https://t.co/wfufJsDS1chttps://t.co/NuBijfvEQK
— 2018年こそ夏バテにならない (@tomerun) 2018年2月13日
