HTTF 2018 qual - 1日9時間寝たい

9891030405点

本番の後、この記事（競プロ解法紹介～レベル別マラソンの戦い方～）を参考にして解き直したら9990441025点になりました*1

参考にして、というか書いてあることをそのまま実装しただけです……。ちなみに、本番でやったことは

初期解として、1000個の山を位置・高さランダムに生成。これを暫定的な最適解とする
新しく1000個の山をランダムに生成し、現時点での最適解とスコアを比較する
1. スコアが低くなったら新しく作ったほうは捨てる
2. 高くなったら新しく作ったほうを最適解とする

で、2.を時間いっぱい繰り返す、というものでした。

上に挙げた記事では、これをちょっと変えた戦略が紹介されています。具体的には、新しく1000個山を作り直すのではなく、1個だけ作り直してスコアを再計算→改善されたら採用というふうにします。

このように、いまの状態を少しいじってスコアが良くなるなら遷移する戦略を山登り法と呼ぶそうです。“少し”というのは色々あって、1000個山を作り直すことを“少し”と主張すればはじめの方法も山登り法になります（適当に言ってます）。

提出したコードは、山を作り直した際のスコアの再計算にO(N*N)かかってるけど、古い山・新しい山のとこだけ見ると計算量が小さくなりそう。ただ、うまく実装ができない……。

スコア計算の盤面生成パートの実装に手間取った。

マラソンの前準備としては

のやりかたを調べておいたほうがよさそう。