naoya_t@hatenablog

いわゆるチラシノウラであります

〈過去問埋め〉技術室奥プログラミングコンテスト #3

技術室奥プログラミングコンテスト #3(出てないやつ)
https://beta.atcoder.jp/contests/tkppc3
の問題を見てみた

続きを読む

中央値の中央値 (median of medians)

ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。

厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に\frac{3}{10}n個ずつ、それより小さい(or 大きい)値が存在することが示せる。

真のmedianの近似として、適当なpivotの選択に使える。
(配列の中でk番目に小さい値を選ぶときに使える。k=n/2とすれば当然真のmedianも求まる。quicksortのpivotにも使えるけど乱数でやったほうが速いとか。最悪計算量は減らせるけど)

原理は割と簡単

続きを読む