Kazun の競プロ記録

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

AtCoder Beginner Contest 234 D 問題 Prefix K-th Max

AtCoder ABC ABC234 D問題 400 pts

問題

提出解答

問題の概要

$(1,2, \dots, N)$ の並び替え $(P_1, \dots, P_N)$ が与えられる. $i=K,K+1, \dots, N$ に対して, 以下を求めよ.

$P_1, \dots, P_i$ において $K$ 番目に大きい整数

制約

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

解法

各 $i$ ごとに $K$ 番目を求めていくと, 計算量 $\Theta(NK)$ で間に合わないが, 出力すべき整数は単調増加になっている. また, $i$ においての答えを $A$ とする.

$P_{i+1} \lt A$ ならば, $i+1$ のときも $A$ である.
$P_{i+1} \geq A$ のときは, $P_1, \dots, P_{i+1}$ での $K$ 番目の値は, $P_1, \dots, P_i$ の $A$ より大きい最小の整数である.

単調増加であることも合わせて, $P_{i+1} \geq A$ のとき, $A$ から条件を満たすかどうかをみるという処理にすることで, 計算量 $O(N+K)$ で求めることができる.