AtCoder Grand Contest 014 C 「Closed Rooms」

問題文

C - Closed Rooms

 

隣り合う部屋に移動することをK回まで繰り返す→閉じられている部屋をK個まで開ける→隣り合う部屋に移動することをK回まで繰り返す→...

という行動をする訳だが、一番最初の移動を除けば「閉じられている部屋をK個まで開ける→隣り合う部屋に移動することをK回まで繰り返す」の繰り返しになるので、全ての部屋が開いているとしてよいことになる。このとき、各部屋から外につながっている部屋までの最短距離は簡単に計算できる。一番最初の移動で辿り着ける部屋から外につながっている部屋までの最短距離のうち最小のものをdとすると、答えは1+floor(d/K)になる。