\(\left\lceil \frac{N}{K} \right\rceil\) 行 \(K\) 列でできたマス目を考えます。 以下、このマス目の上から \(i\) 行目、左から \(j\) 列目のマスを \((i,j)\) と呼びます。

元のマス \(n\) と、新たなマス目の \(\left( \left \lfloor \frac{n}{K} \right \rfloor + 1,m + 1\right)\) を対応させます。ここで \(m\) は \(n\) を \(K\) で割った余りとします。

このとき、”進む” 動作はどうなるかを考えます。

\(a \times K + b\) マス進む動作は、マス目上で下に \(a\) マス、右に \(b\) マス進む動作と対応します。但し、進んだ先のマスを \((c, d)\) として \(d > K\) の場合、実際は \((c+1,d-K)\) に進むことにします (制約上 \(b \leq K\) のため、\(d-K \leq K\) です) 。

DP を行うことを考えます。\(\mathrm{dp}[i]\) を

\(\mathrm{dp}[i]\) := マス \(i\) まで進むのにかかるコストの最小値

と定義します。\(\mathrm{dp}[1]=0\) です。

このとき、遷移は次のようになります。

• \(i\) から一度の “進む” 動作でたどり着けるマス \(j\) 全てについて、\(\mathrm{dp}[j]\) を \(\min(\mathrm{dp}[j], \mathrm{dp}[i]+C_i)\) に置き換える。

この遷移が先ほど考えたマス目上でどうなるかを考えます。

\(\mathrm{dp}[i]\) から一度の “進む” 動作でたどり着けるマスの集合は、マス目上で高々 \(2\) つの矩形領域で表すことができます (右に進み過ぎた場合を考える必要があるため、\(1\) つの矩形領域で表すことができない場合があります) 。そのため、ある矩形領域に対して上の置き換えを高速に行うことが出来ればこの問題を解くことができます。

これは、双対セグメント木を二次元に拡張したもので行うことができます。計算量は \(O(N \log^2 N)\) となります。提出コード (C++)

また、移動を逆順に見ることで “矩形領域内の最小値を求める、一点を更新する” ことができるデータ構造を用いて解くこともできます。二次元に拡張したセグメント木を利用すると、計算量は \(O(N \log^2 N)\) です。提出コード (C++)