Kazun の競プロ記録

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

AtCoder Regular Contest 151 A問題 Equal Hamming Distances

AtCoder ARC151 ARC A問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

{\tt 0}, {\tt 1} からなる文字列を 01 列と呼ぶことにする.

長さ N の 01 列 S, T がある.

同じ長さの文字列 X,Y に対するハミング距離を \operatorname{dist}(X,Y) と書くことにする.

長さ N の 01 列 U で \operatorname{dist}(S,U)= \operatorname{dist}(T,U) となるものは存在するか? 存在するならばこのような長さ N の 01 列 U のうち, 辞書式最小であるものを求めよ.

制約

  • 1 \leq N \leq 2 \times 10^5
  • S,T は長さ N の 01 列

解法1 (存在条件)

まず, \operatorname{dist}(S,U)=\operatorname{dist}(T,U) となる U が存在することの特徴づけを考える.

必要条件から考える. \oplus を排他的論理和とすると, 2 を法にして,

\displaystyle \begin{align*} \operatorname{dist}(S,T) &\equiv \bigoplus_{i=1}^N (S_i \oplus T_i) \\ &=\bigoplus_{i=1}^N ( (S_i \oplus U_i) \oplus (U_i \oplus T_i) ) \\ &=\bigoplus_{i=1}^N (S_i \oplus U_i) \oplus \bigoplus_{i=1}^N (U_i \oplus T_i) \\ &\equiv \operatorname{dist}(S,U) \oplus \operatorname{dist}(T,U) \end{align*}

である. よって, \operatorname{dist}(S,U)=\operatorname{dist}(T,U) となる U が存在するならば, \operatorname{dist}(S,T) は偶数でなくてはならない.

十分条件について考える. \operatorname{dist}(S,T) が偶数であるとして, 2K:=\operatorname{dist}(S,T) とする. このとき, S_i \neq T_i となる i を昇順に 1 \leq j_1 \lt j_2 \lt \dots \lt j_{2K-1} \lt j_{2K} \leq N とする. このとき, U を

U_i:=\begin{cases} S_i & (i=j_1, j_2, \dots, j_K) \\ T_i & ({\rm otherwise}) \end{cases}

とすると, \operatorname{dist}(S,U)=\operatorname{dist}(T,U) である.

以上から, \operatorname{dist}(S,T) が偶数であることが U が存在することの必要十分条件である.

解法2

\operatorname{dist}(S,T) が偶数であるとする. 十分条件のときの議論をよくみてみると, S_i \neq T_i となる i のうち, K 個が S 側, 残りの K 個を T_i 側, 残りは任意であるような文字列 U が \operatorname{dist}(S,U)=\operatorname{dist}(T,U) となり, 逆に \operatorname{dist}(S,U)=\operatorname{dist}(T,U) であるような文字列 U はこの条件を満たす.

よって, 次の問題を考えることになる.

次の条件をみたすような文字列 U のうち, 辞書式最小であるものを求めよ.

  • j=1,2, \dots, 2K のうち, U_{i_j}=S_{i_j} となる整数 j の個数が K 個, U_{i_j}=T_{i_j} となる整数 j の個数が K 個

S_i=T_i であるような i についての条件は特にないので, 辞書式最小のためには U_j=0 としなければならない.

j=1,2, \dots, 2K の順に[tex: U{i_j}=S{i_j}] となる整数 j の個数が K 個, [tex: U{i_j}=T{i_j}] となる整数 j の個数が K 個とすることが不可能にならないように U_{i_j}=0 と優先的に割り当てるようにする.

このようにして出来上がった文字列 U が条件を満たし, 辞書式最小になる.