notepad.exe

つまり覚え書き

ARC101/ABC107 D - Median of Medians

復習日記

解説その他諸々を見ながらやっていきます。

問題ページ

問題概要

長さ $M$ の数列を昇順に並べたときの $\frac{M}{2} + 1$ 番目の要素の値を中央値とする
長さNの数列の各 $(l, r) (1 \leq l \leq r \leq N)$ について $\{ a_{l}, a_{l+1}, ..., a_{r} \}$ の中央値を $m_{l,r}$ と置く
すべての $(l, r)$ に対しての $m_{l,r}$ を集めた数列を作り、その数列の中央値を求める

考え方

まず、中央値について考え方を整理します。問題概要には中央値の定義は、

長さ $M$ の数列を昇順に並べたときの $\frac{M}{2} + 1$ 番目の要素の値を中央値とする

と書かれていますが、これを言い換えると、長さ $M$ の整数列 $b$ の中央値を $x$ としたときに、

$b$ の中に $x$ 以上の要素が $\lceil \frac{M}{2} \rceil$ 個以上含まれる $x$ の中で最大の整数

であるといえます。
この「条件 $P$ を満たすものの中で最大のもの」という考え方に注目すると二分探索で解くことができることがわかります。
これは連続部分列の中央値 $m_{l,r}$ を並べた数列にも同様のことが言えて、最終的にこの問題は、

$m_{l,r} (1 \leq l \leq r \leq N)$ のうち $x$ 以上の要素は何個か？

という質問に置き換えることができます。
ここで $m_{l,r} (1 \leq l \leq r \leq N)$ について言及するように言い換えると、

$a$ の連続部分列 $a[l, r] (1 \leq l \leq r \leq N)$ のうち， $x$ 以上の要素を $\lceil \frac{r−l+1}{2}\rceil$ 個以上含むものは何通りか？

という質問になります。

次に、この質問に対してどのような解法をとるかを考えます。
毎回数えてしまうと計算量が多く間に合いません。そこで $x$ より大きい数を $1$ 、 $x$ より小さい数を $-1$ に置き換えて累積和を取ります。そうするとその区間の累積和が0以上であれば $x$ より大きい数の個数が過半数であるということがわかります。
さらに言えば、 $1$ から $M$ までの累積和を取っておけば、

$m_{l,r} (1 \leq l \leq r \leq N) = m_{1,r} - m_{1,l}$

と計算をすることで求めることができます。

最後に、区間の累積和が0以上である区間の個数を求める方法ですが、 $S_i = \sum_{j=1}^{i}{a_{i}}$ としたときに、

$S_i \leq S_j (i \lt j)$ である $(i, j)$ の組み合わせの個数

と言い換えることができます。これは反転数を求めるアルゴリズムを使うと高速に求めることができます。反転数のアルゴリズムについては蟻本のp162または螺旋本のp175に載っています。

提出コード(諸々を写経)

かなり難しい700点ですね…
これを時間内に解くだけパフォーマンスが2000を超えるので、目標にしたいところです。