ARMERIA

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

AtCoder Beginner Contest 145 F - Laminate

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

お題箱より。

解法

問題で最小化すべき値である「塗る操作の回数」を「コスト」と呼ぶことにします。また各 $H_{i}$ の値を「高さ」と呼ぶことにします。

説明をやりやすくするため、0列目に $H_{0} = 0$ である列が存在すると考えます。

$H_{i}$ の値が確定した後、コストがいくつになるかを考えます。これは隣り合う $H_{i}, H_{i+1}$ のうち、 $H_{i} \lt H_{i+1}$ である箇所について $H_{i+1} - H_{i}$ を合計したものになります。

これは下図のように高さ $H_{i}$ のマスを順番に並べたときに、左側に露出している壁の長さの合計と思うことができます。コストがこの値になることは、この壁になっているマスを塗るためには必ずそれぞれ1回ずつ塗る操作が必要であること、またこの壁から右側に続く限りのマスを塗ることで必ず全てのマスを塗ることができることから示せます。

f:id:betrue12:20191130171015p:plain

またこのことから、高さの変更操作をする列を決めた時、それらは1つ前の列と同じ高さにすることが最適であることが分かります。これは直感的には「上図のようにでこぼこしているほうがコストが高くなるので、でこぼこを減らすのが良い」と理解できます。証明は、高さを変更する列の前後がどういう高さ関係になっているかで場合分けするとできます。

これまでの考察で得た材料として、以下の特徴が分かりました。

コストの加算要素は、隣り合う2つの箇所の関係だけから計算される。
高さを変更する際には、1つ前の列と同じ高さにすれば良い。
- つまり、元々の $H_{i}$ として存在する値以外に高さを変更することは考えなくて良い。

このことから、1つ前の高さだけを持つようなDPを考えることができます。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack$ ：インデックス $i$ の列まで見て、一つ前の列の高さが $H_{j}$ と同じ値であって、これまでに値を変更した回数が $k$ であるときの、それまでのコストの最小値

※添字 $j$ で表現している高さの状態の持ち方については、座標圧縮をするほうが発想としては自然かもしれません。今回はソートされている必要がないので上記のようにすると実装が少し楽になります。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack$ からの遷移は、以下の2つだけを考えれば良いです。

$H_{i+1}$ の値をそのまま採用する。コストを $\max(0, H_{i+1} - H_{j})$ 増加させて、 $dp\lbrack i+1 \rbrack\lbrack i+1 \rbrack\lbrack k \rbrack$ に遷移する。
$i+1$ 列目の値を $H_{j}$ に変更する。コスト据え置きで、 $dp\lbrack i+1 \rbrack\lbrack j \rbrack\lbrack k+1 \rbrack$ に遷移する。

状態数が $O(N^{2}K)$ で遷移が定数通りなので、全体計算量 $O(N^{2}K)$ で解くことができます。

ACコード

Submission #8708066 - AtCoder Beginner Contest 145