ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

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 かどうかを見れば良いです。

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

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

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

  1. a_{i} = k である i が存在する。
  2. 中央値が 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