[AtCoder] ABC 179 D – Leaping Tak

2020年9月25日

問題

方針

遅延評価セグメント木

動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( [L_1, R_1] \) から整数を選ぶとします。このとき、マス \( i \) から到達できるマスを \( j \) とすると、\( i + L_1 \leq j \leq i + R_1 \) となります。したがって、区間に対して \( v_i \) を加算すればいいので、遅延評価セグメント木が使えます。

今回の実装では、遅延ノードに対して剰余を取らないことに注意します。

累積和

\( d(i) \) を \( i \) マス目に行く方法の数とします。便宜上 \( d(0) = 1 \) として、マス \( N – 1 \) に行く方法の数を求めます。ここで、\( d(i) \) について考えます。区間 \( [L_1, R_1] \) から整数を選んだとき、

\[ d(i) \leftarrow d(i – L_1) + d(i – L_1 – 1) + \cdots + d(i – R_1)\]

となるので、

\[ d(i) = \sum_{k=1}^{K} \sum_{j=L_k}^{R_k}d(i – j)\]

となります。ここで、\( \sum_{j=L_k}^{R_k}d(i – j)\) は \( d(i) \) の累積和で高速に計算できるので、\( d(i) \) の累積和を \( c(i) \) とすると、

\[c(i) = d_0 + d_1 + \cdots + d_i\]

となり、

\[ d(i) = \sum_{k=1}^{K} (c(i – L_k) – c(i – R_k – 1))\]

となります。\( d(i) \) の値が確定した後、\( c(i + 1) = c(i) + d(i) \) と更新します。

コード

遅延評価セグメント木

累積和

参考