intro-heuristics AtCoder Contest Scheduling
https://atcoder.jp/contests/intro-heuristics/standings
20 位。ギリギリ1ページ目に乗った
~21:00
テンプレートの準備。
rdtsc と焼きなましテンプレはコピペして、ONLINE_JUDGE があるので input() の受け取りをするかどうかを環境で切り分ける部分も先に書いておいた。
cat /proc/cpuinfo で CPU が 3.00 GHz に上がっていることを確認して rdtsc の定数をちょっと書き換えたりした。
21:00~ 21:09
A を読んでから B を解く。
やりたいことはなんとなくわかったけど、サンプルが D=5 なせいでちょっと手間取る。こういうのは const int D=365; したくなる人間なので……。
なんとか直して提出！
毎行出力させるのを忘れていました。ちゃちゃっと直した所 B 問題にも 5 分制限が掛かっててキレた。
B問題の「毎行出力させる」のはあきらかに高速化の障害になる気がするのですがどうなんでしょうか。
21:09 ~ 21:24
思考停止で一点変更焼きなましを書く。差分計算を高速化する前にとりあえず書くものを書いて提出した。 → 98.5M
score 関数も 1 日ごとに計算する形のまま、開始温度も適当。 たしかこの時点で 40 位くらいで首を傾げながら唸ってた記憶がある。
21:24 ~ 21:49
裏で時間制限 60s とかまで伸ばすと 110M 相当 (ケース平均 1.2 M くらい)くらい出ることがわかったので高速化。ただしケースごとの分散がバカでかいのであんまり当てにならないなーとか思いながら眺めていた。
score 関数で毎回開催間隔のペナルティを引く必要はないので、開催したときと全部終わった後に c * Δ * (Δ-1) / 2 を引いてあげればよい。ちなみに 1-indexed になるのでもれなくバグ祭りが開催されており、死ぬ気でバグを取って提出！
デバッグ用の早期リターンを消し忘れてた。ついでに 1-indexed バグも取りきれてなかったので除去して再提出。 → 110.9M
21:49 ~ 22:13
ここまで差分計算が全計算の差になっているので、差分だけ軽く計算する方法を考えていく。
s_i,d はすぐだが、c[i] の絡むペナルティが面倒だった。お絵かきをすると、変更する d 日目の前後 prv, nxt をなんとか持ってきて c[x] * ((nxt-d-1) * (nxt-d-2) / (d+1-prv) * (d-prv) / 2 - (nxt-prv) * (nxt-prv-1) / 2); を足し引きすれば良いことがわかる。prv nxt は set<int> + set.lower_bound で持ってきていたが 実はこれが大間違い らしく、コンテナの中の要素数が高々 20 くらいなので普通に vector でゴリゴリやるほうが速いらしい。たしかに……。
まあなんとか実装したし、回転数も 5 倍以上、 20M くらい回るし、提出！ → 106.8M なんで？？？？？？？？
22:13 ~ 22:26
また 1-indexed でバグらせていた。 21:24 の提出 (確実に Δscore が合っている submit) と突き合わせながら必死のバグ取りをして 117.5M。
22:26 ~ 22:38
ここからは温度変化管理の時間。温度管理たのしい！！！！
dscore, prob, score, maxscore を stderr に並べながら良さげに焼ききれるかを目でなんとなく眺める作業。最終盤にスコアが伸び切らない場合は緩すぎて、中盤からそこそこの値で息切れする場合は固すぎる。
またなんかバグが残ってたのを取ったりしてパラメタ調整。 118.0M
22:30くらい ~ 22:44
今更 裏で回していたスコア検証用のコードに再現性がないことに気づく。原因としては手抜き XorShift を使っていたため seed が固定できていなかった。
ちゃんとしたものを探してコピペし直し、提出用コードにも反映した。 120.0M
22:44 ~ 22:55
裏で温度管理芸人しながら 2 点変更 (2 点 swap ではなく、 1 点変更 * 2 回) したら満遍なくならないかなーと考えているうちに時間切れ。
最終的に startTemp = 1150 という中途半端な数字で 121.5M
23:00
提出時 19 位が 20 位になっていた。
その後も抜かされることはなく 1 ページ目はギリギリで死守できた。
23:03
C 問題を見る。
「日付 $d$ とコンテストタイプ $q$ をランダムに選び、$d$ 日目に開催するコンテストをタイプ $q$ に変更する」という変形操作は実はあまり良くありません。
はい。
