以下の内容はhttps://betrue12.hateblo.jp/entry/2020/05/21/003239より取得しました。

Codeforces Round #641 (Div. 1) B. Orac and Medians

Codeforces プログラミング競技プログラミング

お題箱より。

Problem - D - Codeforces

問題概要

長さ $n$ の整数列 $a_{1}, ..., a_{n}$ が与えられる。この数列に以下の操作を0回以上行ってよい。

ある連続部分列 $a_{l}, ..., a_{r}$ を選び、それら全てをその中央値で置き換える。ただしこの問題において、 $s$ 個の値の中央値は小さい方から $\lfloor\frac{s+1}{2}\rfloor$ 番目の値とする。

ある整数 $k$ が与えられる。操作によって数列の全ての要素を $k$ にできるかどうか判定せよ。

制約

$1 \le n \le 100000$
$1 \le a_{i} \le 10^{9}$
$1 \le k \le 10^{9}$

解法

長さ $1$ のケースは最初に処理します。唯一の要素が $k$ かどうかを見れば良いです。

なるべくシンプルな手順で目標を達成できないか考えましょう。目標達成から逆向きに考えていきます。

全ての要素を $k$ にするためには、連続して2個 $k$ が並んでいる部分をどこか1箇所作れば良いです。その2個と別の1個の3個に対して中央値を取ると必ず $k$ になり、これを繰り返すと全ての値を $k$ にできるからです。
連続した2個の $k$ を作るためには、長さ2以上の区間で中央値がちょうど $k$ になるものを探して操作するか、もしくは $k$ の隣に $k$ 以上の値が置かれている部分を作れば良いです。その2つの中央値を取ると必ず $k$ になるからです。
$k$ の隣に $k$ 以上の値を置くためには、まず長さ2以上の区間で中央値が $k$ 以上になるものを探して操作し、その値を1.の手順と同様に $k$ の隣まで運べば良いです。

ここまで考えると、目標を達成するためには $a_{1}, ..., a_{n}$ について

$a_{i} = k$ である $i$ が存在する。
中央値が $k$ 以上になるような長さ2以上の区間が存在する。

をともに満たすことが十分条件であることが分かります。

そしてこれは必要十分条件になっています。中央値は元の値のうちのどれかになるので1.は必ず満たされている必要があり、もし2.のような区間が存在しなければ何度操作しても $k$ 以上の要素を増やすことができないからです。

あとはこれをチェックします。2.の条件については各要素を $k$ 以上であれば $+1$ 、 $k$ 未満であれば $-1$ に置き換えた数列を考えます。「中央値が $k$ 以上になる」は「 $k$ 以上の値が過半数存在する」と言い換えられるので、この $\pm 1$ に置き換えた数列において区間和が正である長さ2以上の区間を求めれば良く、これは累積和などを用いて解くことができます。

しかしもう少し単純な解法が存在し、実は2.の条件を確認するために調べるべき区間は長さ2または3の区間だけで十分であることが示せるので、全探索することもできます。

その理由は以下の通りです。先ほどの $\pm 1$ の表記を用います。もし長さ3の区間で過半数（つまり2個）の $+1$ を持つものが存在しない場合、 $+1$ 同士の間には $-1$ が少なくとも2個以上挟まっているはずです。つまり $+1$ の密度が一番高いケースでも

$+1, -1, -1, +1, -1, -1, +1, ...$

という並びにしかならず、これでは区間和が正となる長さ2以上の区間は絶対に取れません。よって「もし長さ3で区間和が正であるものが存在しないならば、長さ4以上でも存在しない」ということが成り立つので、長さ2または3だけを調べれば十分です。

ACコード

Submission #80785667 - Codeforces

以上の内容はhttps://betrue12.hateblo.jp/entry/2020/05/21/003239より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14