AtCoder Beginner Contest 148：D - Brick Break

問題
解法
解答

問題

https://atcoder.jp/contests/abc148/tasks/abc148_d

解法

壊すレンガの数を少なくするには残すレンガの数を増やせばよいので，できる限り 1, 2, 3, ... の列を長くすればよい．これは，次に残したい数字 k（最初は 1）を保持しながら左端からレンガを見ていき，k 以外の数字のレンガが現れたらひたすら壊し，k の数字のレンガが現れたら k++ する，という風に処理すればよい．O(N)．