ひたすらバグってつらかった。。。DP 高速化系。セグ木を使ってもいいが、累積和だけで解ける。

問題概要

座標 $0$ 地点から座標 $D$ 地点へと移動する。

移動途中に $N$ 個のガソリンスタンドがあって、それらの座標は $x_1, x_2, \dots, x_N$ で与えられる。
燃料 $F$ の状態でスタートして $0$ から $D$ まで途中で一切止まることなく移動する
1 移動するごとに燃料を 1 失う
ガソリンスタンド地点を通過するときに燃料が $T$ 未満だったら一瞬で $F$ になる
ガソリンスタンドまたは地点 $D$ 以外の場所で燃料が $0$ になったらダメ

さて、ガソリンスタンドを何個か壊すことを考える。壊して良いガソリンスタンドの集合の個数を 1000000007 で割ったあまりを求めよ。

制約

$1 \le N \le 10^{5}$

考えたこと

x にスタート地点の 0 を加えて番号を振り直しておくことにする。一目見て、

dp[ i ] := i で最後に補給する場合の、i までのガソリンスタンドの立て方の総数

とすればよさそうなのはわかる。同時にこれだと $O(N^{2})$ かかりそうなのもわかる。それでも、とりあえず $O(N^{2})$ の愚直 DP を書いてみるのは良さそう。式を眺めていくことで、累積和だったり CHT だったり monotone minima だったりが見えて来る。

今回は、貰う DP の形で書くと、

各 $k$ に対して、 $k$ で補給してから $x$ [ $k$ ] + $(F-T)$ 以内の距離にあるガソリンスタンドに関しては、壊しても壊さなくても関係ないので、その範囲内にあるガソリンスタンドの個数を num として、fact[ $k$ ] = $2^{{\rm num}}$ とする
$x$ [ $i$ ] - $F \le x$ [ $k$ ] < $x$ [ $i$ ] - $(F - T)$ を満たす $k$ に対して、dp[ $i$ ] += dp[ $k$ ] × fact[ $k$ ]

各 $i$ に対して $k$ が動くので $O(N^{2})$ になる。しかし dp 式をよく見ると $k$ は連続する範囲を動いているので、累積和が使える形になっている。

sum[ $i+1$ ] = $\sum_{k=0}^{i}$ (dp[ $k$ ] × fact[ $k$ ])

とする。これを用いれば毎回の更新が $O(1)$ でできて、全体でも $O(N)$ の計算量で計算できる。

最後の答えは、

各 $i$ に対して、 $D - x$ [ $i$ ] $\le F$ を満たすならば、dp[ $k$ ] × fact[ $k$ ] を加算する

ことで求めることができる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MOD = 1000000007;

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main() {
    int N; long long D, F, T;
    cin >> D >> F >> T >> N;
    vector<long long> x(N+1); x[0] = 0;
    for (int i = 0; i < N; ++i) cin >> x[i+1];
    vector<long long> fact(N+1, 1);
    for (int i = 0; i <= N; ++i) {
        int right = upper_bound(x.begin(), x.end(), x[i] + (F-T)) - x.begin();
        fact[i] = modpow(2LL, max(right - i - 1, 0), MOD);
    }
    vector<long long> dp(N+1, 0), sum(N+2, 0);
    dp[0] = 1;
    sum[1] = fact[0];
    for (int i = 1; i <= N; ++i) {
        int left = lower_bound(x.begin(), x.end(), x[i] - F) - x.begin();
        int right = lower_bound(x.begin(), x.end(), x[i] - (F-T)) - x.begin();
        dp[i] = (sum[right] - sum[left] + MOD) % MOD;
        sum[i+1] = (sum[i] + dp[i] * fact[i] % MOD) % MOD;
    }
    long long res = 0;
    for (int i = 0; i <= N; ++i) {
        if (D - x[i] <= F) res = (res + dp[i] * fact[i] % MOD) % MOD;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CODE FESTIVAL 2018 qual A D - 通勤 (700 点)

問題概要

制約

考えたこと