Codeforces Round #618 C. Water Balance

Problem - C - Codeforces

問題概要

※0-indexedで記載します。

実数列 $a_{0}, ..., a_{n-1}$ が与えられる。（初期状態では各要素は正整数）

この実数列に対して、「ある連続する区間を選び、その区間に含まれる要素全てをそれらの平均で置き換える」という操作を好きな回数繰り返す。

これによって得られる辞書順最小の数列を求めよ。

制約

$1 \le n \le 10^{6}$
$1 \le a_{i} \le 10^{6}$

解法

操作区間の形を限定する

操作する区間が入り組んでいるととても考えづらいので、まずここを解消します。実は以下のことが成り立ちます。

最適解を実現する操作列で、操作区間が互いに重ならないようなものが存在する。

このような性質を証明するための常套手段である、「操作区間が重なっているような操作区間は、必ず解が悪くならないような別の形に変形できる」という論法を使います。

簡単のため、2つだけ区間が重なっている状態を考えます。もし一方の区間が他方の区間を完全に包含している場合は、小さい方の操作は意味がないので消去できます。つまり重なり方として考えるべきは2通りです。

f:id:betrue12:20200211132654p:plain

操作した区間を積み上げていくイメージで、後に操作した区間のほうを上側に書いています。ここで例えばケース1のほうを考えると、以下のように場合分けすることで、解を悪くせずに区間数を1つ減らすことができます。

もし $A \lt B$ ならば、2回目の操作において $a_{2}, a_{3}$ の値が増えてしまっている。そのため2回目の操作を行わないほうが解をより良くできる。
もし $A \ge B$ ならば、1回目の操作の右端を $a_{5}$ にして2回目の操作を消去することで、解をより良く（もしくは変わらないように）できる。

ケース2のほうも同様に考えることができます。

実際の操作列はたくさんの操作区間が入り乱れている可能性がありますが、この性質を使って1つずつ区間数を減らしながら重なりを解消していくことができます。先ほどの操作区間を積み上げた図において、上にあるものから順番に処理していくイメージです。

区間数が無限に減るということはないので、最終的には有限回の変形で必ず重なりが存在しない形にできます。これで証明できました。

貪欲解とスタック解

操作区間が重ならないことを前提とすると、最適解は以下のように前から貪欲に決めていくことができます。

操作区間のスタート地点を $s = 0$ とする。
$a_{s}, ..., a_{t}$ の平均値が最も小さくなるような $t$ を求め、この区間を操作する。（便宜上、複数ある場合は最も小さい $t$ としておく）
これで $a_{s}, ..., a_{t}$ の値は確定したので、 $s$ に $t+1$ を代入して、同じことを繰り返す。

ですがこの操作をシミュレートしていくのは大変です。代わりに以下のようなアルゴリズムを考えます。

前から順番に要素を追加していきます。そしてこれまで追加した要素を、操作した区間（あるいは1つだけの要素）の平均値と長さを持ったブロックを順に並べたものとして記録しておきます。

f:id:betrue12:20200211144343p:plain

新しく要素 $a_{i}$ を足す時には、まず $(a_{i} \times 1)$ としてブロックを末尾に足します。そして「末尾2つのブロックについて、後のブロックの値のほうが小さい」という性質を満たす限りこの2つのブロックをマージすることを繰り返します。

f:id:betrue12:20200211153605p:plain

これは各ブロックをスタックに格納することで、全体 $O(n)$ で実現することができます。

先に紹介した前から貪欲に確定させていく方法を「貪欲解」、後に紹介した方法を「スタック解」と呼ぶことにします（実際はどっちも貪欲だと言えなくもないですが…）。この2つの解法によって同じ解が得られることを証明します。

貪欲解における操作区間 $\lbrack s, t\rbrack$ それぞれについて、スタック解において

$a_{s}$ が追加されたときに、より前の要素とマージされないこと
$a_{t}$ が追加されたときに、区間 $\lbrack s, t\rbrack$ が1つのブロックになるまでマージされること

を示せば良いです。このうち $a_{s}$ については、前の要素とマージされるということはより良い解ができてしまうということなので、貪欲解の最適性からそれはないことが分かります。

スタック解において要素を追加する直前のタイミングでは、ブロックの列においてその値は単調増加になっています。 $a_{t}$ が追加された直後、あるいはそこからブロックがいくつかマージされた状態において、各ブロックの値の大小関係は以下のようになっています。

f:id:betrue12:20200211145532p:plain

$t$ の最適性より、 $a_{s}$ を含むブロックの値よりも $a_{s} , ..., a_{t}$ の平均のほうが小さくなります。そしてマージされていないブロックの値は単調増加になるので、図より $t$ を含むブロックは区間 $\lbrack s, t\rbrack$ に存在するブロックの中で最も小さい値になっているはずです。そのため必ず1つ手前のブロックとのマージが起こります。これを繰り返して、区間 $\lbrack s, t\rbrack$ が1つのブロックになるまでマージされます。