Codeforces Round #587 (Div. 3) F. Wi-Fi

お題箱より。

Problem - F - Codeforces

セグメント木を使わない解法を…とのリクエストだったので、何通りか解法を紹介します。

問題概要

$n$ 個の部屋が並んでいて、順に番号 $1, ..., n$ が付けられている。これらの部屋全てにインターネット回線を提供したい。

回線提供には2つの方法がある。

それぞれの部屋 $i$ について、 $i$ コイン払うことでその部屋に単独でインターネット回線を提供できる。
いくつかの部屋は無線ルーターを持っていて、その部屋 $i$ については $i$ コイン払うことで区間 $\lbrack \max(1, i-k), \min(N, i+k)\rbrack$ に含まれる全ての部屋にインターネット回線を提供できる。

整数 $n, k$ と各部屋の無線ルーターの所持有無が与えられるので、全ての部屋にインターネット回線を提供するために払う合計コインの最小値を求めよ。

制約

$1 \le n, k \le 2\times 10^{5}$

解法1：セグメント木

この問題は結局、

（区間, その区間を使うコスト）の組がいくつか与えられるので、整数点 $1, ..., n$ 全てを覆う最小コストを求めよ。

という問題です。この問題をパターンとして捉えセグメント木で処理するのがたぶん一番楽です。

$dp\lbrack i \rbrack$ を「整数点 $1, ..., i$ が全て覆われるための最小コスト」とします。予め区間を右端で分類しておき、 $dp\lbrack i \rbrack$ を更新するときには $i$ を右端とするような区間それぞれに対して、

その区間の左端を $l$ 、コストを $c$ とするとき、 $\min(dp\lbrack l-1 \rbrack, ..., dp\lbrack i-1 \rbrack) + c$ で $dp\lbrack i \rbrack$ を更新（今の値より小さければ採用）する

とすれば良いです。少なくとも $l-1$ までが覆われている状態を遷移元とすることで、区間 $\lbrack l, i\rbrack$ を新たに採用して $i$ までを覆うことができます。

区間最小が取れるセグメント木にDPの値を入れることで高速に $\min$ の計算ができます。セグメント木のクエリ1回が $O(\log n)$ なので全体計算量は $O(n\log n)$ です。

この解法は後に紹介するようなこの問題特有の単調性が無くても使えるので、そういった意味でもこの解法を知っておくのがオススメです。

ACコード1

Submission #60990629 - Codeforces

解法2：スライド最小値

ルーターが覆う区間の長さは左右にはみ出る場合を除けば一定で、ルーターを置く部屋を右にずらしていくと左端も右端も単調に変化します。このような場合、先ほどの $\min(dp\lbrack l-1 \rbrack, ..., dp\lbrack i-1 \rbrack)$ の計算はスライド最小値という方法を用いて高速化できます。この場合、計算量はDP全体でならし $O(n)$ となります。

ルーターを使わない場合の遷移は単に1つ前の1点だけが遷移元になるので各点ごとに $O(1)$ で計算できます。結局全体で $O(n)$ になります。

ACコード2

Submission #61186419 - Codeforces

解法3：コストの単調性を使ってgreedy

リクエスト的にはこれが本命ですかね。このコメントを参考にしました。今回の場合はコストが右の部屋にいくほど高くなっているので、DPの遷移をgreedyに取ることができます。

DPを左（添え字の小さい方）から回すのではなく、右から回します。 $dp\lbrack i \rbrack$ を「整数点 $i, ..., N$ が全て覆われるための最小コスト」と定義します。

$dp\lbrack i+1 \rbrack$ から $dp\lbrack i \rbrack$ 方向への遷移を考えます。つまり右から $i+1$ までが覆われているので、次に採用する区間で少なくとも $i$ は覆う必要があります。

1つの方法は単に部屋 $i$ 単独で回線を引くことです。そしてルーターに関しては、実は部屋 $i$ をカバー範囲に含むルーターのうち最も左にあるものだけを考えれば十分です。これがまだカバーされていない範囲を最も遠くまでカバーし、加えて左側の部屋のルーターを使ったほうがコストが安いので、「右から $i+1$ までは既に覆われている」という前提のもとでは完全に上位互換になっているからです。

※もしDPを左から回すと、ここで「遠くまでカバーするものほどコストが高い」という状態になり、1つに確定できません。

結局 $dp\lbrack i+1 \rbrack$ からの遷移は、

単独回線を使い $dp\lbrack i \rbrack$ に遷移する。
部屋 $i$ をカバー範囲に含むルーターのうち最も左のものを使い、その左端を $l$ として $dp\lbrack l \rbrack$ に一気に遷移する。

2つだけを考えれば十分です。これで全体 $O(n)$ でのDPができます。

このDPでは選ばなかったルーター区間について遷移を飛ばしてしまうため、厳密には各点において「整数点 $i, ..., N$ が全て覆われるための最小コスト」になっていません。そのため正当性が少し理解しづらいのですが、各ステップで他と比べて必ず損をするものを切り捨てているので最終的には正しい答えが得られます。