Kazun の競プロ記録

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

AtCoder Beginner Contest 279 E問題 Cheating Amidakuji

AtCoder ABC279 ABC E問題 500 pts

問題

提出解答

問題の概要

各項が $1$ 以上 $N-1$ 以下の整数である長さ $M$ の列 $A=(A_1, \dots, A_M)$ がある.

次の問題を $i=1,2, \dots, M$ に対して解け.

$B=(1,2, \dots, N)$ とする.
の順に以下を実行する.
- $B_{A_i}$ と $B_{A_i+1}$ を入れ替える.
$B_j=1$ を満たす $j$ を求めよ.

制約

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

解法

$\sigma_1, \dots, \sigma_M$ をそれぞれ $A_i$ 番目と $(A_i+1)$ を入れ替える作用素とする.

$\tau_i:=\sigma_M \dots \sigma_{i+1} \sigma _{i-1} \dots \sigma_2 \sigma_1$ とする. このとき, $\left(\tau_i \right)_j=1$ となる $j$ を求めよ. なお, 作用素をいくつか合成させたものを $\gamma$ としたとき, $\gamma_j$ で $\gamma$ によって $j$ 番目の要素が何になったかを表すとする. また, 合成は右から左に行う.

$\alpha_i, \beta_i$ をそれぞれ

$\alpha_i:=\sigma_i \dots \sigma_1$
$\beta_i:=\sigma_i \sigma_{i+1} \dots \sigma_i$

とすると, $\tau_i=\beta_{i+1}^{-1} \alpha_{i-1}$ である. また,

$\alpha_i=\sigma_i \alpha_{i-1}$
$\beta_i=\sigma_{i-1} \beta_{i-1}$

である.

また, $\left(\tau_i \right)_j=1$ となるような $k$ は $\left(\alpha_i \right)_l=1$ となるような $l$ に対して, $j=\left( \beta_i \right)_l$ である.

そして, $\alpha_0$ は恒等置換, $\beta_1=\sigma_1 \dots \sigma_M$ である.

ある置換に互換をかけるような作用は $O(1)$ 時間で完了できる. よって, $i=1,2, \dots, M$ の順に $\alpha_i, \beta_i$ を更新していきながら $l$ 及び $j$ を求めるような方針によって, $O(N+M)$ 時間で計算できる.