Codeforces 417 B. Sagheer, the Hausmeister

codeforces.com

n階m部屋と両脇に階段(よって全体の幅はm + 2)の建物がある。最初は1階の左はじにいる人が各階の電気をすべて消し、上にのぼる、次の階もすべて消し上にのぼる…を繰り返してすべての部屋の電気を消す。最初に点いている部屋が与えられる時、最短の距離を求めよ。

ある階を消し終わって右端にいる時の最短距離及び左はじにいる時の最短距離を仮定すると、次の階はそれらの二つを使って求められるのでdpになる。最後の階だけは端の階段に戻らない、最初の階は一番右にある電気のついてる部屋 or m+1というところを気をつける。dpの遷移自体はO(n)。単に入力の読み込みだけがO(nm)。