drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ 二分探索 転倒数 BIT データ構造 中央値(メディアン)に関する問題 K番目を求める AtCoder AtCoder700点 ABC-D 黄色diff ARC-D グラフテク:下駄を履かせて負辺除去 数列 解空間:O(N^2)通りの選択肢 区間 累積和 考察：操作・条件・目的関数を言い換える けんちょん本演習問題 0と1の問題 考察：変数変換 操作:一斉に±aする NoviSteps2D 「 番目の値を求めよ」「メディアンを求めよ」といった問題では、二分探索法が有効なことが多々ありますね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 この数列の連続する区間として考えられるものは 個あります。そのそれぞれの区間について、区間内の値のメディアンをとります。 このようにして得られる 個の値のメディアンを求めてください。 制約 二分探索へ 次の判定問題を解くことを考えてみましょう。この判定問題に対する答えが "Yes" となる最小の が答えとなります。 数列の連続する区間 () であって、その区間内の数値のメディアンが 以下であるようなものが 個以上存在するならば "Ye… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2018%2F09%2F08%2F011500" title="AtCoder ABC 107 D - Median of Medians (ARC 101 D) (2D, 黄色, 700 点) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/80936665/1516148889515660 Hatena Blog https://hatena.blog 2018-09-08 01:15:00 rich https://drken1215.hatenablog.com/entry/2018/09/08/011500 1.0 100%