Kazun の競プロ記録

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

AtCoder Beginner Contest 257 C問題 Robot Takahashi

AtCoder ABC ABC257 C問題 300 pts

問題

提出解答

問題の概要

$0,1$ からなる長さ $N$ の文字列 $S$ と長さ $N$ の整数列が与えられる. 実数 $X$ に対して, $f(X)$ を以下で定める時, $\displaystyle \max_{X \in \mathbb{R}} f(X)$ を求めよ.

以下を満たす以上以下の整数の個数をとする.
- 次のうち, 少なくとも (実はどちらか) 一方が成り立つ.
  - $f(X) \leq W_i$ かつ $S_i=1$
  - $f(X) \gt W_i$ かつ $S_i=0$

制約

$1 \leq N \leq 2 \times 10^5$
$S$ は $0,1$ からなる長さ $N$ の文字列
$1 \leq W_i \leq 10^9$
入力は全て整数

解法

今回, $W_1, \dots, W_N$ が整数であることから, 以下が成り立つ.

$\displaystyle \max_{X \in \mathbb{R}} f(X)=\max \{f(-M), f(W_1), \dots, f(W_N), f(M) \}$

ただし, $M$ は十分大きい定数とする.

実際, 各 $i$ に対して, $f(X)$ に対する寄与の有無は $X=W_i$ を堺にして変わるから, 上のような等式が成り立つ.

よって, 各 $X$ に対して, $f(X)$ を高速に計算できれば良い.

$S_i=0$ であるような $i$ のみからなる $W$ の部分列と $S_i=1$ であるような $i$ のみからなる $W$ の部分列をそれぞれ $C,A$ とする. すると, $f(X)$ は以下の和である.

$C$ にある $X$ 未満の整数の個数
$A$ にある $X$ 以上の整数の個数

$C,A$ は共に不変なので, 最初にソートしておくと, 二分探索によってこれらを各 $X$ に対して, 計算量 $O(\log N)$ 高速に求める事ができる.

以上から, $C,A$ を最初にソートしておくと, 各 $X$ に対して $f(X)$ を $O(\log N)$ 時間で計算できるので, 求めるべき最大値を $O(N \ log N)$ 時間で計算できる.