ARC115-E LEQ and NEQ 解説
面白かった。
解説
まず、愚直な DP を考えてみる。「$dp[i][j] =i$ 番目までで、$j$ で終わっているときの、ここまでの置き方の通り数」とすると、自明に解けるが、これでは当然通らない。
$A_i$ を座標圧縮して、同じ区間に含まれる数はまとめて扱えるので、DP は $O(N^2)$ にできる。高速化はできたが、これでもまだ遅い。「$dp[i][j]=i$ 番目までで、$j$ 以下で終わっているときの、ここまでの置き方の通り数」と定義し直すと、DP の遷移式は次のようになる。
- $dp[i][j]=dp[i-1][A_{i-1}]j-dp[i-1][\min(A_{i-1}, j)]$
ここで出てくる $\min$ の場合分けで計算量が増大しているので、これをなんとかして高速化できないか考える。 この式をまた同じように展開してやると、
- $dp[i][j]=dp[i-1][A_{i-1}]j-(dp[i-2][A_{i-2}]j - dp[i-2][\min(A_{i-2}, j)])$
となる。このように、展開を続けていくと、一番最後の項以外が $j$ でくくれて、これは累積和で高速化可能である。 どこまで展開すればよいかがわかればよいが、これは、$A_j < A_i$ となるような最大の $j$ を見つけるクエリに高速に答えられればよい。これは、stack に値を積んで管理していくと、ヒストグラム上の最大長方形を求めるアルゴリズムと全く同じ原理で、ならし $O(1)$ で処理できる。
これで、この問題が $O(N)$ で解けた。
