codeforces.com 問題 You are a given an array 𝑎 of length 𝑛. Find a subarray 𝑎[𝑙..𝑟] with length at least 𝑘 with the largest median. Then, output the maximum median you can get. 解説 まず「中央値がxにできるか」という判定問題をO(N)で解くこと…

問題へのリンク 問題概要 長さの数列について、以下の操作を繰り返し全ての要素をにできるか判定せよ。 数列の区間について、全ての要素をその区間の中央値に置き換える。 ただし、中央値は区間の長さをとすると、小さい方からとする。 解説 色々実験してみ…

問題 方針 単調性 判定問題 区間の中央値がX以上になる条件 区間列挙の解決策 実装 問題 長さNの数列が与えられる。この中の全ての連続部分列における中央値の中央値を求めよ。 問題へのリンク 方針 単調性 二分探索する。 中央値がX以上となる区間の数が全…