[AtCoder] ABC 179 D – Leaping Tak

2020年12月12日

問題

方針

遅延評価セグメント木

動的計画法のようなことを遅延セグメント木を使って行います。\( 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) \) と更新します。

コード

遅延評価セグメント木

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 998244353;
class SegmentTree {
private:
    int n;
    vector<ll> node, lazy;
public:
    SegmentTree(int N) {
        n = 1;
        while (n < N) n *= 2;
        node.resize(2 * n - 1, 0);
        lazy.resize(2 * n - 1, 0);
    }

    void update(int i, int l, int r) {
        if (lazy[i] == 0) return;
        node[i] += lazy[i];
        node[i] %= mod;
        if (r - l > 1) {
            lazy[2 * i + 1] += lazy[i] / 2;
            lazy[2 * i + 2] += lazy[i] / 2;
        }
        lazy[i] = 0;
    }

    void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        update(k, l, r);
        if (b <= l || r <= a) return;
        
        if (a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            update(k, l, r);
        } else {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = (node[2 * k + 1] + node[2 * k + 2]) % mod;
        }
    }

    ll query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        update(k, l, r);
        if (b <= l || r <= a) return 0;        
        if (a <= l && r <= b) return node[k] % mod;

        ll sum_l = query(a, b, 2 * k + 1, l, (l + r) / 2);
        ll sum_r = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return (sum_l + sum_r) % mod;
    }

};

int main() {
    int N, K;
    cin >> N >> K;
    int L[K], R[K];
    for (int i = 0; i < K; i++) {
        cin >> L[i] >> R[i];
    }

    SegmentTree st(N + 1);
    st.add(1, 2, 1);
    
    for (int i = 1; i < N; i++) {
        ll x = st.query(i, i + 1);
        for (int j = 0; j < K; j++) {
            int l = i + L[j];
            int r = i + R[j] + 1;
            st.add(min(l, N + 1), min(r, N + 1), x);
        }
    }

    cout << st.query(N, N + 1) << "\n";

    return 0;
}

累積和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 998244353;

int main() {
    
    int N, K;
    cin >> N >> K;
    int L[K], R[K];

    for (int i = 0; i < K; i++) {
        cin >> L[i] >> R[i];
    }
    
    ll d[N]{};
    ll c[N + 1]{};
    d[0] = 1;
    c[1] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < K; j++) {
            int l = max(0, i - R[j]);
            int r = max(0, i - L[j] + 1);
            d[i] += (c[r] - c[l] + mod) % mod;
            d[i] %= mod;
        }
        c[i + 1] = d[i] + c[i];
        c[i + 1] %= mod; 
    }
    cout << d[N - 1] << "\n";
    return 0;
}

参考

AtCoder,動的計画法,累積和,遅延評価セグメント木

Posted by ヤマカサ