ryotoriの精進録があと41問ですが、それを埋め終わったら幾何n本ノックをします
JMOで幾何の弱さが露呈してしまった...
ABC107-D Median of Medians
700点として置かれたDで有名です。この次の回のARCもDが700点で有名でした。
コンテスト中のAC者はABC, ARC合わせて192人とそこまで多くない方でした。この問題で重要な考察の過程を残したいためにここに記事を書くことにします。
第1段階:二分探索
二分探索で解の存在を絞り込めないかという考察をします。これは感覚的な部分もあるのですが、「中央値がX以下の部分列の個数」が求められたらうれしいという発想のもとで二分探索を念頭に置きながら考察をします。
ここで計算量的に, 実際の判定フェーズで使える計算量はO(N)くらいのものであるということに注意します。
第2段階:中央値がX以下とは?
ある部分列に関して, その中央値がX以下であるということは次のように言い換えられます。
「ある部分列に存在するX以下の要素の個数は,Xより大きい要素の個数より多い」
ここから, 現在の数列に対して次の変換を施します。
このような変換によって, 上の問いを次のように言い換えることができるようになりました。
第3段階:数列bに和が0未満の区間はいくつあるか?
区間の和が出たら累積和を取ろうとするのは条件反射のようなものです。累積和上で和が0未満であるということは, と同じことです。
あとは座標圧縮+BITで転倒数を求めることで, 中央値がX以下となる判定関数が計算量 O(log N)で実装できました。
