エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
AtCoder ARC #101 : D - Median of Medians - kmjp's blog
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
AtCoder ARC #101 : D - Median of Medians - kmjp's blog
時間通りには参加しませんでした。 https://beta.atcoder.jp/contests/arc101/tasks/arc101_b 問題 M要... 時間通りには参加しませんでした。 https://beta.atcoder.jp/contests/arc101/tasks/arc101_b 問題 M要素の整数列B[1..M]の中央値は、Bを昇順に並べたときのfloor(M/2+1)番目の値と定義する。 ここでN要素の整数列A[1...N]が与えられる。 Aの部分列はN*(N+1)/2通りあるが、これらの中央値からなる数列を作ったとき、その中央値を求めよ。 解法 AtCoderでは以前もあったが、中央値に関する問題は二分探索で解くとよいことが多い。 二分探索で、「解がv以上になるかどうか」を判定するには、Aの中身をv未満なら0、v以上なら1としたとき、中央値が1になるかを判定すればよい。 この際、N*(N+1)/2通りのうち半数以上で中央値が1になればよいことがわかる。 括弧列に似た要領で、0/1のどちらが多いかはBIT等をつかえばO(