naoya_t@hatenablog

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

2018-07-18から1日間の記事一覧

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

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

〈ARC埋め〉600点問題 (ARC 061 E)

ABC/ARC/AGCの500点以下の問題が埋まったので600点問題に進出

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

ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。 厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に3n/10個ずつ、それより小さい(or 大きい)値が存在することが示せる。 真のmed…