解いた問題

2/18/2013

SRM569 Div1 Medium

500

O(n) の貪欲で解ける。
操作は、"Kの倍数を作る"、"全部上の階へ渡す"、"(倍数にならなくても)とにかく上の階から持ってくる"、の3パターンがある。
倍数を作れるなら極力そうした方が良いのは直感的に明らか。
m 階に注目しているとして、m 階に m - 1 階から幾人か上がってきている場合、彼らはその階で消費する必要がある。
その際、上の階からKの倍数にならないとしても全員を持ってきた方が、それより上の階で消費されるべき人数を減らせる。

苦戦した。貪欲は難しいと再認識した。

2/14/2013

SRM570 Div1 Easy

250

プログラムを何週か実行してこれまでと同じ向きで停止できれば、以降はそれの繰り返しになる。
実行回数 T を割り切れない様な周期での繰り返しになる場合は、残りを普通に実行してしまえばいい。