Kazun の競プロ記録

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

AtCoder Regular Contest 136 B問題 Triple Shift

AtCoder ARC ARC136 B問題 400 pts

問題

提出解答

問題の概要

長さ $N$ の列 $A,B$ が与えられる. $A$ に対して次の操作を $0$ 回以上行い, $B$ と一致させられるか?

$1$ 以上 $N-2$ 以下の整数を $1$ つ選ぶ. $A_{i}, A_{i+1}, A_{i+2}$ をそれぞれ $A_{i+2}, A_i, A_{i+1}$ に置き換える.
制約
$3 \leq N \leq 5000$
$1 \leq A_i, B_i \leq 5000$

解法1 (必要十分条件)

まず, $A,B$ において出現回数が異なる整数が異なる場合は明らかに不可能である. 以降では $A,B$ は (条件に沿うとは限らない) 並び替えで一致するとする.

このとき, $A$ が $B$ に一致させることができることと, 適当な 偶置換 $\sigma \in \mathfrak{A}_N$ が存在して, $A^{\sigma}=\left(A_{\sigma(i)} \right)=B$ となることである.

これを証明する. このとき, $(i, i+1, i+2) \in \mathfrak{A}_N$ が $\mathfrak{A}$ を生成することを証明すれば良い.

$\alpha=(\alpha_i) \in \mathfrak{A}_N$ において, $\alpha_i=N$ であるとする. このとき, 適当な $(i, i+1, i+2)$ たちをかけ続けることにより, $\alpha_N=N$ とすることができる. これを $N, N-1, \dots, 3$ に注目することにより, $i \geq 3$ ならば, $\alpha_i=i$ にすることができる. 残りは $\alpha_1, \alpha_2$ についてだが, $2$ 要素の置換において偶置換は恒等置換しかない. そして, 偶置換同士の積も偶置換であることから, $\alpha_1=1, \alpha_2=2$ である.

よって, $\beta_j \in \mathfrak{A}_N$ で $\beta_r \beta_{r-1} \dots \beta_1 \alpha={\rm id}_N$ となるものが存在する. このとき, $\beta_j^{-1}=\beta_j^2$ なので,

$\alpha=\beta_1^2 \dots \beta_{r-1}^2 \beta_r^2$

であり, $\mathfrak{A}_N$ は $(i, i+1, i+2)$ で生成されることがわかった.

解法2 (判定)

解法1に引き続き, $A,B$ は (条件に沿うとは限らない) 並び替えで一致するとする. その並び替えを $\sigma$ とする.

$A$ に出てくる要素が互いに異なるとき, この $\sigma$ は唯一である. 従って, $\sigma$ が偶置換ならば肯定的で, 奇置換ならば否定的である.
$A$ に出てくる要素において重複が存在するとき, $\sigma$ が偶置換であるとき, そのまま肯定的である. $\sigma$ が奇置換のとき, 仮定から, $i \neq j$ で $A_i=A_j$ となるものが存在する. よって, $\tau:=\sigma~(i~j)$ とすると, $A^{\tau}=A^{\sigma}=B$ であり, $\tau \in \mathfrak{A}_N$ である.

この判定法から, 以下のことを判定すれば良い.

ある置換 $\sigma \in \mathfrak{S}_N$ が存在して, $A^{\sigma}=B$ となるか?
$A$ に重複があるか?
$A$ に重複がないとき, 上の $\sigma$ は偶置換か?

最後の偶置換かどうかについては転倒数の偶奇を見れば良い. この転倒数を求めるパートがボトルネックになり, 計算量 $O(N \log N)$ で求めることができる.