HACK TO THE FUTURE 2018予選 参加記


このエントリーをはてなブックマークに追加

先週の大会に引き続きHACK TO THE FUTURE 2018予選 - HACK TO THE FUTURE 2018予選 | AtCoderにも参加しました。8時間フルで参加して23位でした。

思考ログ

まずは以下のようなgreedyに山を作る方法を試しました。

  1. 盤面Aと盤面Bとでもっとも差分が大きいマスを探す
  2. そのマスを中心とした山を取る。この時の山の高さは、盤面Bのいずれのマス目も盤面Aを超えない範囲で最大値を取る
  3. 1.に戻る

これで9.8953e9点。実装にハマってしまったお陰で、ここまでで約3時間浪費してしまいます。


次に、上記2で、800個目以降に山を作る場合は、盤面Bのマス目が盤面Aのマス目を上回ることを許すルールを追加しました。 これで9.9631e9点。


ここでビジュアライザを使うと、盤面Aの外縁部の値を、盤面Bでは多く取りこぼしていることに気付きました。そこで、まず最初に盤面Bの全体にまんべんなく山を設置することで、盤面Bの外縁部の値が小さくなることを防げるのではないかと考えました。具体的には、盤面Bを5x5の小エリア400個に分割し、それぞれの真ん中に高さ75の山を並べました。このパラメータが結構シビアで、結果に意外と影響しました。これで9.9823e9点。ここまでで大体5時間経過です。


次に、終盤で盤面Bのマス目が盤面Aのマス目を許すときに、スコアが最良となる山の高さhを1から100まで全探索して決定するロジックなどを入れました。手調整が必要なパラメータがいくつか増えてます。これも効いて、9.9901e9点まで来ました。


次に、これまで作成した各山の高さを±5の範囲で全探索して、もっともスコアが上がるhに修正する、山登りによる最適化処理を処理時間いっぱいまで行うようにしました。これも効いて、9.9946e9点。6時間半経ってようやくこの問題で何をすればよいか分かってきました。


さらに山のx位置, y位置をそれぞれ±2、つまり今の山の位置を中心とした5x5のエリア内でスコアがもっとも上がる山の位置を全探索するコードを追加しようとしたんですが、WA連発で時間を浪費したのが非常に痛かったです。バグの原因はhの有効範囲[1, 100]とx, yの有効範囲[0, 99]を誤って混同していたしょうもないミスでした。終了15分前くらいになんとかバグがとれて、9.9971e9点。


最後に、山の高さの探索範囲を±2に狭める調整をして時間に追われるように提出して、9.9972e点。これが最終スコアでした。

感想と反省

終了後の動画解説を見たところ、方針をそれほど大きく外してはなかったのが良かったです。しかしいかんせん最適化処理の必要性に気づくのに6時間半かかったのはちょっと遅すぎでした。もう少し早くこの段階にたどり着けていたとしたら、山の位置・高さを変えたときのスコア計算の高速化(現状はすべて愚直にO(N2)の計算)、パラメータ調整、焼きなましの導入など打つ手は合ったかなと思います。