SRM631Div1Easy
問題
サイズNの各要素が'B'か'W'の2次元の配列が与えられる。各行に対して以下の操作が可能である。
- 全ての'W'を'B'にする
- 全ての'B'を'W'にする
列にN/2より大きく連続で同じ要素が並ばないようにするための最小の操作回数を求めよ。
解法
条件にひっかかるためには、N/2+1の長さが必要となる。これを悪配列と呼ぶ。各列の悪配列どうしは2個以上の同じ行の要素が存在する。そのため、一回の操作である値の悪配列を全てなくすことができる。操作をすることで新しい悪配列が生成されることがある。しかし、同様の性質を持っているので一度の操作でなくすことが可能である。
よって、答えは0,1,2のどれかになる。
計算量
O(N)
