Kazun の競プロ記録

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

AtCoder Regularr Contest 133 B 問題 Dividing Subsequence

AtCoder ARC ARC133 B問題 500 pts

問題

提出解答

問題の概要

$1$ から $N$ の並び替え $P,Q$ が与えられる. 以下を満たすような整数列 $I,J$ における長さの最大値を求めよ.

$|I|=|J|$
$1 \leq I_1 \lt I_2 \lt \dots \lt I_{|I|} \leq N$
$1 \leq J_1 \lt J_2 \lt \dots \lt J_{|J|} \leq N$
$Q_{J_i}|P_{I_i}$

制約

$1 \leq N \leq 2 \times 10^5$
$P,Q$ は $(1,2, \dots, N)$ の並び替え.

解法

動的計画法を考える. ${\rm DP}[i,j]$ を第 $i$ 項目までみて, 特に $P_i$ と $Q_j$ をマッチングさせるような取り出し方のうちの長さの最大値をする.

ベースケースは ${\rm DP}[0,0]=0$ で, 更新式は

${\rm DP}[i,j]=\begin{cases} 0 & (Q_j \not | P_i) \\ \displaystyle \max_{\substack{1 \leq k \lt i \\ 1 \leq l \lt j}} {\rm DP}[k,l ]+1 & (Q_j | P_i) \end{cases}$

である.

このとき, 答えは $\displaystyle \max_{1 \leq i,j \leq N} {\rm DP}[i,j] ( \geq 1)$ である.

ここで, $1 \leq k \lt N$ において, $Q_j|P_k, Q_j|P_{k+1}$ ならば, ${\rm DP}[k,j] \lt {\rm DP}[k+1,j]$ であるから, in-place に更新することによって, 動的計画法の配列は $j$ に関する情報のみでよい.

そして, $Q_j|P_i$ となる $(i,j)$ の組の数は, 調和級数から, $O(N \log N)$ である.

また, 更新式は $i$ を固定するごとに, $l=1,2, \dots, j-1$ の区間における最大値を求めることになる.

よって, Segment Tree を利用することにより, 計算量 $O(N (\log N)^2)$ で求めることができた.