Codeforces Round #153 (Div. 1) (No. 251) 本番
http://codeforces.com/contest/251
Problems
A
n*にぶたんするだけ
B
操作1と操作2は置換の逆元の関係になっているので、「操作1をした後操作2をする」というのは恒等置換であるし、置換の合成は結合律が成り立つ(とかそういう感じで)ので、
状態を-k..kの数値で表せる(つまり状態がO(k)個しか無い)。
あとはDPなりBFSなりするだけ
C
考えたこと:
・数値が小さいほうが距離も小さい(小さい数で検証した)
・数がb+k以上なら、一番減らす数が大きくなるものを選べば良い(つまり考えればいいやり方は1通り)
結局出来なかった
Hack
Bを1Hackした。
他にもHackできるものがあったが、いろいろやってたら時間がなくなってしまった。
しかしAでO(n^2)やってるものを最後の最後にHackしてみたが"Invalid Input"
絶対もっときちんとHackに専念すればもっとHackできた。そうするべきだった
結果
A: 480 (00:10)
B: 796 (00:51)
Hack: +1/-0 (+100)
Rank: 126/463
Rating: 1720→1823 (+103)
コメント
もっとHackできた。すべきだった
Cは解けるべき。
