o x opened: 159.61 pts. 遅い上に500がsystest failした。ひどい。あと頭文字がかぶるとファイル名の補完が効きにくい。得点を名前にするとかにしたほうがいいのかもしれない。
出たら265位くらい。 rateが下がるはず。
素直に引いていって、残りが3以下になったら最後の飴を決定し、引いていった飴を素直に足してゆく。
足してゆくところが自明じゃないので二分探査した。
O(log N * log N) くらいで終わるはず。
足してゆくところの条件が頭で理解できずにすごく苦労した。250であることを考えると、もっと簡単に書けると思うのだけれど。
Editorialを見た。みんな時間がかかったらしい。あと、恐ろしく簡単な答えがあることを理解した。
max(|x|, |y|) = k なる範囲R_k 内では、どの場所でも雪玉の個数の期待値及び美しさの期待値は同じ。両者を保持して、新たな呪文が唱えられるたびにその値を更新してゆく。O(maxRange * numranges) みたいなオーダー。
バグは以下のとおり。
const int w = range * 2 + 1; const int area = w * w; const double next_x2 = double(amount * (amount + area - 1)) / (double(area) * area);
最後の分子がint32をオーバーフロー。area * areaの方は最大ケースを入れた時に気づいたのに。
そもそもint使うべきではない。long longにしておくかdoubleに任せるべき。
二番目の条件は、xor演算で線形空間を考えた時に線形独立、だった。これが思いつかないとは大学を離れて時間が経ちまくっているな。
まだ面積最小値を取る方法がわかっていない。
本番5人提出正解者なしなので解説を読もう。
追記: 読んだ。
理解した。理解したけどすごいなこれ。