SRM 443

うぉぉぉぉぉぉ
ターゲットktkr

300

始点と終点で円の内外が異なれば、その円の境界を必ず１回はまたぐ必要があり、またそのような円の個数回で始点から終点にたどり着けるので、それが最小
296.94

1000

600>1000の法則があるのかは知らないが、1000からやることにした
てきとーに行列作って累乗するだけ…なんだが、TLEがちょっと厳しくて間に合わない…
もう倍速くらいになれば間に合いそうだったので、C++に切り替えようと思って書き直してたら、文字列のsplitの仕方がわからないorz
よく考えたら%演算の回数を減らせば何とかなりそうだったので、オーバーフローしない程度に足してから一気に%するようにしたら間に合った
513.32

600

0がi個、1がn-i個の状態から１手で移動できる状態は
i + K - 2 * min(K, i)
i + K - 2 * min(K, i) + 2
...
i + K - 2 * max(0, K - n + i) - 2
i + K - 2 * max(0, K - n + i)
であるから、奇数と偶数に分けておけば連続した範囲がすべて可能ということになる
あとは、TreeSetでまだ到達していない状態をもっておいて、subsetで次の状態を取り出していけばよい
各状態について高々１度しか取り出されず、それにO(log n)かかるので、全体でO(n log n)
提出してから、状態nを加えるのを忘れてたことに気づいたが、よく考えたらnに移動できるのはn-kからのみで、nからはn-kにしか移動できないので、なくても問題がなくってせーふ
479.66

Challenge

いきなり600が落とされまくって出遅れたorz
600で偶奇分けをしていない人がいたので、手元で時間のかかるケースを作成して撃墜
偶奇分けしてるけどset使ってない人がいたので、撃墜したらよーくみたらループにbreakがあってTLEしなかったorz
+25.00

撃墜前の段階でトップだったのに撃墜で２人に抜かれて合計1314.92の3位orz
2958 → 3030
つぎの目標はトップ１０入りだーーー