Kazun の競プロ記録

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

AtCoder Beginner Contest 236 E 問題 Average and Median

AtCoder ABC ABC236 E問題 500 pts

問題

提出解答

問題の概要

$N$ 枚のカードがあり, 左から $i$ 番目には $A_i$ と書かれている. この [tex; N] 枚から何枚かのカードを取り出す. ただし, 2枚連続で取り出さないことは禁止されている.

可能な取り出し方全てを考えたとき, 取り出したカードにおける以下の2つの値の最大値をそれぞれ求めよ.

平均値
中央値 (ここでは, $m$ 要素の中央値は小さい方から $\lceil \frac{m}{2} \rceil$ 番目の値とする)

制約

$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$

解法(平均値)

要素数が特に決まっていない場合における平均値の最大値を求める場合, 以下の事実がよく使われる.

以下の2つは同値

平均を $X$ 以上にすることが可能である.
$B=(A_i-X)$ とした列において, 和が $0$ 以上になるような取り出し方が存在する.

この事実を満たす最大の $X$ が答えになる. そして, 条件が $X$ に関して単調減少なので, 二分探索で求めることができる.

$B=(A_i-X)$ とした列において, 和が $0$ 以上になるような取り出し方が存在するかどうかを判定する. 次のような動的計画法を考える. ${\rm DP}[i, \{T,F\} ]$ を

第 $i$ 項目までに制限した問題のうち, $i$ 項目を ( $T$ : 用いる, $F$ : 用いない) ような取り出し方の最大値

とする.

ベースケースは ${\rm DP}[i,T]=B_1, {\rm DP}[i,F]=0$ である. 更新式は

${\rm DP}[i,T]={\rm DP}[i-1, F]$
${\rm DP}[i,F]=\max({\rm DP}[i-1, T], {\rm DP}[i-1, F])+B_i$

である. これで $X$ を固定した場合の判定を $O(N)$ で求められることができるので, 計算量は適切な許容誤差を $\varepsilon$ として, $O \left(N \log \dfrac{\max A}{\varepsilon} \right)$ で求めることができた.

解法(中央値)

中央値においても, 同様に以下のような性質がなりたつ.

以下の2つは同値

中央値を $X$ 以上にすることが可能である.
$C$ の第 $i$ 項目を $X$ 以上ならば $1$ , $X$ 未満ならば $-1$ としたとき, 和が正になるような取り出し方が存在する.

下の判定問題は平均値の場合と同様にして解くことができる. よって, 答えを $O(N \log N)$ で求めることができる.

以上から, 平均値と中央値をともに $O(N \left(N \left(\log N+\log \dfrac{\max A}{\varepsilon} \right) \right)$ で求めることができる.