AtCoder Regular Contest 101 D - Median of Medians
解けませんでした。そろそろ本番で700点問題を通せるようになりたい。
解法
答えを二分探索します。「の中央値が
以上かどうか」が判定できれば、それを満たす最大の
が答えとなります。
「の中央値が
以上かどうか」というのは、「
の中の区間のうち、
以上の要素が半数以上を占める区間が半数以上かどうか」と言い換えられます。
そのような区間の数を知るには、中の各要素を
以上ならば
、
未満ならば
と置き換え、その累積和の転倒してない数を求めてやればよいです。
全体の計算量はとなります。
反省
まず「の中央値が
かどうか」を求めようとしました。
を
で置き換えたやつの累積和の転倒してない数を求めればよさそうだと思いましたが、これをやるのに
かかるので、
を各
について試すとなると厳しいです。
を小さい要素から順に見て、差分を計算する……など考えましたが、うまくいきませんでした。
条件を緩くして二分探索に落とすという発想が一切出なかったところに頭の弱さを感じます。数え上げの問題などにも似たようなのがあるので慣れなきゃダメですね。
コンテスト直後ナーバスになって弱音を吐く僕↓
答えを二分探索する系の問題一生慣れる気がしない
— ウォンバット (@wombat_packer) 2018年8月25日
