Tenka1 Programmer Contest 2019：C - Stones

問題

atcoder.jp

解法

黒の右には白はないので，操作後の石の列は「白白白白白...」か「黒黒黒黒黒...」か「白白白...黒黒黒...」となる．よって，左から何個かを白にして，そのほかを黒にすればよい．この「何個」を 0 ~ N まで試せばよい．操作しなければならない回数は，白の石の個数を累積和で持っておくことで O(1) で計算することが出来る．全体で O(N)．

解答

atcoder.jp