Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Regular Contest 156 A問題 Non-Adjacent Flip

AtCoder ARC156 ARC A問題 400 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

\texttt{0}, \texttt{1} からなる長さ N の文字列 S がある.

以下の操作を 0 回以上行うことによって, S の全ての文字を \texttt{0} にすることは可能か? 可能ならばその操作回数の最小値を求めよ.

  • 1 \leq i \lt j \leq N, j-i \geq 2 となる整数 i,j を選び, S_i, S_j それぞれについて, \texttt{0} ならば \texttt{1} へ, \texttt{1} ならば \texttt{0} に変更する.

T 個のテストケースについて答えよ.

制約

  • 1 \leq T \leq 2 \times 10^5.
  • 3 \leq N \leq 2 \times 10^5.
  • S は \texttt{0}, \texttt{1} からなる長さ N の文字列.
  • T 個のテストケースにおける N の総和は 2 \times 10^5 以下.

解法

1 回の操作における S にある \texttt{1} の数の変化は +2, \pm 0, -2 のどれかである. よって, 偶奇は常に一定であり, 最終的に目指すべき文字列は S にある \texttt{1} の数が 0 個の文字列である.

よって, K を 「 S にある \texttt{1} の数」とすると目標を達成するための必要条件は K が偶数である.

これ以降, K は偶数であるとする.

  • N=3 のとき, 操作可能な i,j の選び方は (i,j)=(1,3) に限る. よって, S=\texttt{000} か S=\texttt{101} のみ目標を達成可能で, それ以外は目標達成不可能である. そして, この 2 つの文字列における最小回数はそれぞれ 0,1 である.
  • N \geq 4 とする.
    • K=0 のとき, 既に目標を達成しているので, 最小回数は 0 である.
    • K \geq 4 のとき, S_i=\texttt{1} である i を昇順に i_1, i_2, \dots, i_{K-1}, i_K としたとき, j=1,2, \dots, \frac{K}{2} に対して, i_{j+\frac{K}{2}}-i_j \geq (j+\frac{K}{2})-j=\frac{K}{2} \geq 2 であるから, j=1,2, \dots, \frac{K}{2} に対して S_j, S_{j+\frac{K}{2}} を \texttt{0} にすることを繰り返せば良い. また, これが最小回数を達成する.
    • K=2 のとき
      • S に連続する部分列として \texttt{11} を含まないとき, 2つの \texttt{1} がある添字の差は 2 以上であるから, 1 回の操作で目標を達成できる. なお, 1=\frac{K}{2} である.
      • S に連続する部分列として \texttt{11} を含むとき
        • S に連続部分列として \texttt{0011} を含むとき, この部分に着目して次のように操作すると, K=2 であるから, 目標を達成できる. \texttt{0011} \to \texttt{1010} \to \texttt{0000}. しかも, この 2 回がこれが最小回数である.
        • S に連続部分列として \texttt{1100} を含むとき, 上の場合と同様にして 2 回が最小回数である.
        • S に連続部分列として \texttt{0011}, \texttt{1100} を含まないとき, K=2, N \geq 4 という場合分けの条件も合わせると, これを満たすのは S=\texttt{0110} しかない. これは次のようにして 3 回が最小回数になる. \texttt{0110} \to \texttt{1111} \to \texttt{1010} \to \texttt{0000}

これらをまとめると, 求めるべき解答は 文字列 T が文字列 S の連続部分列であるということを T \in S と表すことにすると,

\begin{cases} \begin{cases} 0 & (S=\texttt{000}) \\ 1 & (S=\texttt{101}) \\ \text{不可能} & (S \neq \texttt{000}, \texttt{101}) \end{cases} & (N=3) \\ \begin{cases} \text{不可能} & (K: \text{奇数}) \\ \frac{K}{2} & (K: \text{偶数} \land (K \neq 2 \lor \texttt{11} \not \in S)) \\ 2 & (K=2 \land (\texttt{0011} \in S \lor \texttt{1100} \in S)) \\ 3 & (S=\texttt{0110}) \end{cases} & (N \geq 4) \end{cases}

となる.

時間計算量は O(N) 時間である.