AtCoder Grand Contest 026 D - Histogram Coloring

問題

https://beta.atcoder.jp/contests/agc026/tasks/agc026_d

解法

高さが同じ $2$ 列のヒストグラムを考えます。
左の列の塗り方が決まっているとき、その塗り方が赤青赤青……のように交互（以下マダラと呼びます）であれば、右の列の塗り方はそれと全く同じにするか真逆にするかの $2$ 通りの選択肢があり、マダラでなければ真逆にするしかありません。
これを念頭に置いて、次のDPを考えます。

$dp[i][j]:=$ 左から $i$ 列目までを順に決めた時の、 $i$ 列目の下 $j$ マスがマダラである（下 $j+1$ マスはマダラでない）パターン数

先ほど述べたことを使い、次のように場合分けして漸化式が立てられます。

$h_{i-1} < h_i$ の場合

$dp[i][j]= \begin{cases} 2^{h_i-h_{i-1}}dp[i-1][j] & (j < h_{i-1}) \\ 2^{h_i-j}dp[i-1][h_{i-1}] & (h_{i-1} \leq j < h_i)\\ 2dp[i-1][h_{i-1}] & (j=h_i) \end{cases}$

$h_{i-1} \geq h_i$ の場合

$dp[i][j]= \begin{cases} dp[i-1][j]& (j < h_i) \\ \displaystyle 2 \sum_{j'=h_i}^{h_{i-1}} dp[i-1][j'] & (j = h_i) \end{cases}$

$2$ 冪の計算には繰り返し二乗法を使うとして、このままの計算量は $O(N (\max h_i) (\log \max h_i))$ となります。さらに遷移の仕方をよく観察すると、全ての $j$ についてパターン数を持つ必要はなく、縦軸に最低限の区切り（具体的には、各 $h_i$ の上下）を入れて、区間和をもっておけばいいことがわかります。要は座標圧縮をするわけです。すると計算量は $O(N^2 \log \max h_i)$ となり間に合います。