Gus@topcoder

SRM 526.5 practice

11:27

o x opened: 159.61 pts. 遅い上に500がsystest failした。ひどい。あと頭文字がかぶるとファイル名の補完が効きにくい。得点を名前にするとかにしたほうがいいのかもしれない。

• 250 24分 159.61 pts
• 500 34分 265.50 pts - 265.50 pts
• 1000 opened

出たら265位くらい。 rateが下がるはず。

250

素直に引いていって、残りが3以下になったら最後の飴を決定し、引いていった飴を素直に足してゆく。

足してゆくところが自明じゃないので二分探査した。

O(log N * log N) くらいで終わるはず。

足してゆくところの条件が頭で理解できずにすごく苦労した。250であることを考えると、もっと簡単に書けると思うのだけれど。

Editorialを見た。みんな時間がかかったらしい。あと、恐ろしく簡単な答えがあることを理解した。

500

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に任せるべき。

1000

• Grundy数を覚えていない。たしかxorするはず。→あってた。
• 任意の部分集合がGrundy数非ゼロって何?
• 時間切れ。

二番目の条件は、xor演算で線形空間を考えた時に線形独立、だった。これが思いつかないとは大学を離れて時間が経ちまくっているな。

まだ面積最小値を取る方法がわかっていない。

本番5人提出正解者なしなので解説を読もう。

追記: 読んだ。

本家解説および日本語訳 by ogiekakoさん

理解した。理解したけどすごいなこれ。