Kazun の競プロ記録

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

AtCoder Regular Contest 137 B問題 Count 1's

AtCoder ARC ARC137 B問題 400 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

0,1 からなる列 A=\left(A_i \right)_{i=1}^N がある. この A に対して, 次の操作を1回だけ行う.

  • 連続する区間 (空も認める) を選び, その区間にある要素を元が 0 ならば 1 に, 1 ならば 0 にする.

操作後の列 B に対して, \displaystyle \operatorname{score}(B):=\sum_{i=1}^N B_i とする.

操作後の列 B に対して, 可能な \operatorname{score}(B) は何通りか,

制約

  • 1 \leq N \leq 3 \times 10^5
  • A_i \in \{0,1\}

解法1

右半開区間 [l, r) に対して操作した結果を B_{l,r} とする.

ここで, i=0,1,2, \dots, N に対して, \chi_i を A_1, A_2, \dots, A_i にある 1 の数とする. すると, A_l, \dots, A_{r-1} において, 1 の数は A_{r-1}-A_{l-1} であるから,

\begin{align} \operatorname{score}(B_{l,r}) &=\operatorname{score}(A)+(r-l)-(\chi_{r-1}-\chi_{l-1})-(\chi_{r-1}-\chi_{l-1}) \\ &=\operatorname{score}(A)+(r-2\chi_{r-1})-(l-2\chi_{l-1}) \end{align}

となる.

このとき, \tau_i:=i-2\chi_{i-1} とおくと,

\operatorname{score}(B_{l,r})=\operatorname{score}(A)+\tau_r-\tau_l

となる.

解法2

ここで, 求めるべきは \operatorname{score}(B_{l,r}) の取りうる値の種類数であるが, \operatorname{score}(A) は l,r によらないから, 結局は \tau_r-\tau_l が何通り取りうるかを考えることになる.

\tau_{i+1}, \tau_i の間において,

\begin{align} \tau_{i+1} &=(i+1)-2\tau_i \\ &=(i+1)-2(\chi_{i-1}+[A_i=1]) \\ &=i-2 \chi_{i-1}+(1-2[A_i=1]) \\ &=\tau_i+(1-2[A_i=1]) \end{align}

より, \left| \tau_{i+1}-\tau_i \right|=1 であることがわかる. この事実と, \tau_i は整数であるから,

\{\tau_r-\tau_l | 1 \leq l \leq r \leq N+1\}=\{X,X+1, \dots, Y-1,Y \}

となる整数 X,Y が存在する.

解法3

最後に, この X,Y を求める. 上の議論から更に, r=1,2, \dots, N+1 をそれぞれ固定すると,

\{\tau_r-\tau_l | 1 \leq l \leq r \}=\{X_r, X_r+1, \dots, Y_{r-1}, Y_r\}

となる整数 X_r, Y_r が存在する. この X_r, Y_r は

\displaystyle X_r=\tau_r-\max_{1 \leq l \leq r} \tau_l, \quad Y_r=\tau_r-\min_{1 \leq l \leq r} \tau_l

である.

解法4

\displaystyle X:=\min_{1 \leq r \leq N+1} X_r, Y:=\max_{1 \leq r \leq N+1} Y_r とすると, 解法2, 解法3の事実も合わせて,

\begin{align} \{\tau_r-\tau_l | 1 \leq l \leq r \leq N+1\} &=\bigcup_{r=1}^{N+1} \{\tau_r-\tau_l | 1 \leq l \leq r \leq N+1\} \\ &=\bigcup_{r=1}^{N+1} \{X_r, X_{r+1}, \dots, Y_{r-1}, Y_r\} \\ &=\{X, X+1, \dots, Y-1, Y\} \end{align}

であり, Y-X+1 が解答になる.