(AOJ1635) ICPC2019 国内予選-D:計数カウンタ

想定解は結構難しいと思ってしまった。

問題

解法

　「ある区間を選び、その区間の数字を同時に $1$ 増やす」という操作が $1$ 回であるとどういうことが起きるかを考えてみる。例えば、 $3$ つのカウンタがあって、すべて $a_i\lt b_i$ が成り立っていても、両端の $2$ つはたくさん押す必要があるが、真ん中の $1$ つはほとんど押さなくてよいという状況を考えてみる。このとき、両端の $2$ つを別々に押すよりも、 $3$ つ同時に押すことを何回か行った方が得をするということがあり得る。このとき真ん中のカウンタでは $M$ から $1$ に戻るということが何回か起きるが、これは目標となる $b_i$ の値を、整数 $j$ を用いて $b_i+jM$ に置き換えることにしよう。解くべき問題は、「各カウンタ $i$ について $j$ をうまく選んだとき、カウンタ $i$ の値を $a_i$ から $b_i+jM$ にするには最小で何回の操作が必要か？」というものである。 $j$ の値としては、カウンタの数である $N$ まで考えれば十分である。
　ところで、 $1$ 番目のカウンタが最適解において何回押されるかということはすぐにわかる(カウンタが $1$ つのときを考えればよいから)。 $1$ 番目のカウンタの状態が決まれば、 $1番目$ のカウンタのことは考えなくてよいので、その状態において $2$ 番目のカウンタを何回押すべきかも計算できる。このように考えてみると、端からdpをしたくなってくる。 $dp_{i,j}$ :「 $i$ 番目のカウンタまで見て、 $i$ 番目のカウンタの値を $b_i+jM$ にするときの操作の回数の最小値」としよう。
　 $dp_{i,j}$ への遷移を考えよう。基本的には、カウンタ $i-1$ とカウンタ $i$ の、各状態における押すべき回数の差分を足し合わせていくことになる。このとき、カウンタ $i-1$ の方が押すべき回数が多いということがあり得るが、その場合はカウンタ $i-1$ を「先に押しておいた」と解釈し、ノーコストでカウンタ $i$ のときの値に遷移することで解決する。カウンタ $i$ を $b_i+jM$ にするためには、そのカウンタを $(b_i-a_i)+jM$ 回押す必要がある( $j=0$ かつ $b_i\lt a_i$ の場合は除く)。この値を $c(i,j)$ としよう。 $dp_{i-1,k}$ から $dp_{i,j}$ への遷移は

$dp_{i,j} = \min(dp_{i,j},dp_{i-1,k}+c(i,j)-c(i-1,k)) \ (c(i-1,k)\lt c(i,j))$
$dp_{i,j} = \min(dp_{i,j},dp_{i-1,k}) \ (c(i-1,k)\geq c(i,j))$

となる。これでは遷移が $O(N)$ かかり、計算量は全体で $O(N^3)$ である。ICPC国内予選なら多少待てばよい(僕のチームはこれで通した)が、AOJでは通らない。
　遷移を高速化しよう。上の遷移のほとんどは「無駄」である、つまり不必要な計算であることがわかる。例えば、 $j+1 \lt k$ である $k$ では、常に $c(i,j) \lt c(i-1,k)$ が成り立つ。つまり、 $dp_{i,j}$ への遷移は $j$ の大きい方から $j+2$ までの累積minを取っておけば、 $O(1)$ で行うことができる。 $k\lt j$ の方の遷移はどうだろうか。 $c(i,j)-c(i-1,k)$ を書き下すと $c(i,j)-c(i-1,k) = (b_i-b_{i-1})-(a_i-a_{i-1})+(j-k)M$ であり、前半 $2$ 項の最小値は $-2(M-1)$ であることを考えると、 $k\lt j-2$ では、 $j$ に遷移する際にカウンタ $i$ を単独で $M$ 回以上押すことになる。しかし、カウンタ $i$ を単独で $M$ 回押すなら、カウンタ $i-1$ をさらに $M$ 回押して損がない。つまり、 $k \lt j-2$ である $k$ から $j$ への遷移は、 $k=j-2,j-1$ から $j$ への遷移に勝ることがない。従って、そのような $k$ からの遷移は計算する必要がないことがわかった。
　以上のことより、遷移として計算すべきは $k=j-2,j-1,j,j+1$ と $j+1\lt k$ だけで、これはそれぞれ $O(1)$ で可能であった。よって、dpの遷移を無事 $O(1)$ にすることができた。全体の計算量は $O(N^2)$ となり、これならAOJでも間に合う。

実装

AIZU ONLINE JUDGE: Code Review
実装は標準的。

ちゃんとやると考察難易度が高いと思う。想定解で通した通したところはすごいなあ...。