Kazun の競プロ記録

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

AtCoder Beginner Contest 276 C問題 Previous Permutation

AtCoder ABC276 ABC C問題 300 pts

問題

提出解答

問題の概要

$(1,2, \dots, N)$ の順列 $P=(P_1, \dots, P_N)$ が与えられる. ただし, $P \neq (1,2, \dots, N)$ である.

$(1,2, \dots, N)$ の順列における辞書式順序の観点において $P$ の直前は何か?

制約

$2 \leq N \leq 100$
$P$ は $(1,2, \dots, N)$ とは異なる $(1,2,\dot,s N)$ の順列.

解法

$X$ を $(1,2, \dots, N)$ の順列とする.

$\operatorname{prev}(X), \operatorname{next}(X)$ を $X$ の直前, 直後 (存在する場合に限ってそう書くとする) とする. また, $\operatorname{inv}(X)$ を

$\operatorname{inv}(X):=((N+1)-X_1, \dots, (N+1)-X_N)$

とする. このとき,

$\operatorname{prev}(X)=\operatorname{inv}(\operatorname{next}(\operatorname{inv}(X)))$

$\operatorname{inv}(X)$ は定義より簡単に求められる. よって, $\operatorname{next}(\bullet)$ を求める問題に帰着された.

今, $P \neq (1,2, \dots, N)$ であるから, $Y:=\operatorname{inv}(P) \neq (N,N-1, \dots, 1)$ である. よって, 次を満たすような $1$ 以上 $(N-1)$ 以下の整数 $k$ が存在する.

$Y_k \lt Y_{k+1} \gt Y_{k+2} \gt \dots \gt Y_N$

このとき, $Y_{k+1}, Y_{k+2},\dots, Y_N$ にある $Y_k$ より大きい最小の整数を $A$ , $Y_k, Y_{k+1}, Y_{k+2}, \dots, Y_N$ から $B$ を除いた長さ $(N-k)$ の列を昇順に並べた列を $Z_1, \dots, Z_{N-k}$ とする. このとき,

$\operatorname{next}(P)=(Y_1, \dots, Y_{k-1}, B, Z_1, \dots, Z_{N-k}$

である.

これにより, $\operatorname{prev}(P)$ を $O(N \log N)$ 時間で求めることができた. なお, ボトルネックになるソートについては $Y_k, Y_{k+1}, Y_{k+2}, \dots, Y_N$ がほとんど降順にならんでいることを利用すると, $O(N)$ 時間に高速化することが出来る.