Kazun の競プロ記録

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

AtCoder Beginner Contest 231 C 問題 Counting 2

AtCoder ABC ABC231 C問題 300 pts

問題

提出解答

解答1 (二分探索)

解答2 (クエリ先読み)

問題の概要

正の整数の列 $A=(A_1, \dots, A_N)$ が与えられる. $q=1, \dots, Q$ それぞれに対して, 以下の問に答えよ.

$A$ の要素のうち, $x_q$ 以上の要素はいくつか?

制約

$1 \leq N,Q \leq 2 \times 10^5$
$1 \leq A_i, x_q \leq 10^9$
入力はすべて整数

解法

解法1 (二分探索)

$A$ を降順にソートしたものを $A'$ とする. このとき, 任意の実数 $y$ に対して, $A'_s \geq y \gt A'_{s+1}$ となる整数 $s$ が存在する (ただし, $A'_0=+\infty, A'_{N+1}=-\infty$ とする). ここで, $A$ にある $y$ 以上の要素は, $A'$ がソート済みなので, $s$ 個であることがわかる.

よって, この $s$ を求める問題に帰着できた. この $s$ は, 二分探索というもので長さ $N$ の列に対して, 計算量 $O(\log N)$ という非常に高速に求めることができる.

以上の方針を $y=x_1, \dots, x_Q$ それぞれに対して実行することで, 計算量 $O( (N+Q) \log N)$ で求めることができる.

解法2 (クエリ先読み)

長さ $N+Q$ の列 $B$ を

$B=( (A_1,\infty), (A_2, \infty), \dots, (A_N,\infty), (x_1,1), (x_2,2) \dots, (x_Q,Q))$

とし, $B$ を辞書式の意味で昇順に並べた列を $B'=( (p'_i, t'_i) )$ とする. このとき, 以下のようにして求めることができる.

$X \gets N$ とする.
に対して, 以下を順に実行する.
- $t'_i=+\infty$ の場合, $X$ を $1$ 減らす.
- $t'_i \lt +\infty$ の場合, 第 $t'_i$ 問目の答えは $X$ である.
$q=1,2, \dots, Q$ の順に, 第 $q$ 問目の答えを出力する.

計算量は $O( (N+Q) \log (N+Q))$ である.