Kazun の競プロ記録

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

AtCoder Beginner Contest 254 C問題 K Swap

AtCoder ABC ABC254 C問題 300 pts

問題

提出解答

問題の概要

長さが $N$ の整数列 $A=(A_i)_{i=1}^N$ がある.

この列に対して, 以下の操作を0回以上行い, $A$ を昇順に並び替えることができるか?

$1$ 以上 $N-K$ 以下の整数 $i$ を選び, $A_i$ と $A_{i+K}$ を入れ替える.

制約

$2 \leq K \leq 2 \times 10^5$
$1 \leq K \leq N-1$
$1 \leq A_i \leq 10^9$

解法

以下では数列の添字を1ずつ減らして 0-indexed であるとする.

まず, 次のことが成り立つ.

長さが $M$ の列 $B=(B_j)_{j=0}^{M-1}, C=(C_k)_{k=0}^{M-1}$ がある. 以下は同値である.

$C$ は $B$ のある並び替えである.
に対して, 以下の操作を回以上行い, をと一致させることができる.
- $0$ 以上 $M-1$ 未満の整数 $j$ を選び, $B_j$ と $B_{j+1}$ を入れ替える.

ここで, $K$ 個の列 $X_0, X_1, \dots, X_{K-1}$ を次のように定める.

$X_0=(A_0, A_N, A_{2N}, \dots )$
$X_1=(A_1, A_{N+1}, A_{2N+1}, \dots )$
$\vdots$
$X_i=(A_i, A_{N+i}, A_{2N+i} ,\dots)$
$\vdots$
$X_{K-1}=(A_{K-1}, A_{N+K-1}, A_{2N+K-1}, \dots )$

このとき, $A_i$ と $A_{i+K}$ を入れ替えるということは , $i$ を $K$ で割った商と余りを $q,r$ としたとき, $X_r$ の第 $q$ 項目と第 $(q+1)$ 項目を入れ替えることに対応する.

つまり, 上で述べた事実から, このことがわかる.

$A$ において, $K$ で割った余りが等しい項目同士は自由に並び替えることができる.

このことから, $X_0, X_1, \dots, X_{K-1}$ を昇順に並び替えた列を $\widetilde{X_0}, \widetilde{X_1}, \dots, \widetilde{X_{K-1}}$ とし, $A$ を昇順に並び替えた列を $\widetilde{A}$ と書くとき, $A$ を昇順にすることができるための必要十分条件は

$\widetilde{A}=\left(\widetilde{X_0}_0, \widetilde{X_1}_0, \dots, \widetilde{X_{K-1}}_0, \widetilde{X_0}_1, \dots, \widetilde{X_{K-1}}_1, \dots \right)$

である.

計算量は $\widetilde{X_0}, \widetilde{X_1}, \dots, \widetilde{X_{K-1}}, \widetilde{A}$ を求めるためのソートがボトルネックになり, $O(N \log N)$ で計算できる.