長いので問題ページ参照
公式の解説がメチャクチャ詳しいので、問題ページのリンクから読みましょう。
以下は終了後の提出。
1日目から貪欲で埋めた後に、どの日をどのコンテストタイプに変更するかをランダム抽選で山登り。
変更時のスコア差分を計算して、更新許容閾値を超えたら更新。閾値は-3000→0にループが進む毎に線形に増やしていく。
これで最高 115,832,333 点。
その後、以下の変更を試す。
スコア差分の計算方針の中で難しいのは、コンテスト開催間隔が空いたときの不満度。 ある日にコンテストを新しく開催/削除した際の増減分は、その日より前・後に直近で開催した日があれば計算できる。
あるコンテストの、1日あたり満足度の低下量
・c,e日目に開催していた場合
_-~
_-~
_-~ _-~
_-~ _-~
---------------------
c e
・d日目にも追加で開催した場合（d日目で0にリセットされ、翌日からまた増加）
_-~ _- _-~
_-~ _-~ _-~
---------------------
c d e
つまり、この平行四辺形の面積分だけ低下量は減る
_-~| 縦: Ci x (d-c)
_-~ | 横: e-d
_-~| _- _-~
_-~ |_-~ _-~ → Ci x (d-c) (e-d) だけ満足度は増える
---------------------
c d e
よって前後に直近で開催した日がわかればよい。これは、C++でのstd::setなどのデータ構造をコンテスト毎に作ると $O(\log{D})$ で取得可能。
だが、ここがヒューリスティックコンと普段のコンテストの感覚の違うところだが、 今回、数値はランダムに決められているので、まず貪欲に埋めた時点で、 そこまで大きな間隔が空くコンテストは存在しないだろう（あっても少数だろう）と言える。 開催間隔が空くことに依る満足度低下は日数の2乗で効いてくるので、よほど $c_i$ がアンバランスでない限り、 開催間隔の空いたコンテストを放置することのデメリットが大きくなる。
なので、何日目にどのコンテストを開催したかを記録する配列を、$d$ 日目の前後に線形に探索しても $O(問題数)$ くらいで出現すると期待できる。
... 3 4 ... 8 1 3 5 ... 2 7 3 ...
c d e
実装量が多く添字を取り違えやすいデータ構造を使うのと大きく変わらない計算量で、単純な線形探索で調べられる。
それならとりあえずは単純な実装でも十分だよね。特に今回は2時間コンテストで、手早い実装が大事。
コスト計算と更新の実装だけでほぼ時間を使い切ってるんだよなあ。
その他
print(file=sys.stderr) ができないtime.time() が使えない時間の使い方としては、
というのが基本かなあ。
ハイパーパラメータチューニングには、以下のようなツールもあるらしい。