はまやんはまやんはまやん

hamayanhamayan's blog

通勤 [CODE FESTIVAL 2018 qual A D]

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d

考察過程

1. これを思い出すので、似たようなDPを考える
2. dp[i] := i番目まで確定していて、i番目で給油をした場合の組み合わせ数
3. dp[i] += sum{i以下のjからiに到着可能で、jに給油して、iでは残りがT未満になっている} dp[j]
4. これでは給油に関係したGSしか見れていない
5. 給油に関連していないGSはどうしよう
6. 例えばdp[j]を考えると、X[j]に近いX[j+1]やX[j+2]ではガソリンスタンドがあってもなくても給油的には関係無い
7. 関係無いので、有る無しで組み合わせを考える必要がある
8. dp[i] += sum{i以下のjからiに到着可能で、jに給油して、iでは残りがT未満になっている} dp[j] * 2^(X[j]と近すぎて給油できないGSの個数)
9. これをみるとdp[j]ではなく、dp[j] * 2^(X[j]と近すぎて給油できないGSの個数)をBITで持っておけば更新はO(logN)
10. この方針で行けそうだ

解説

https://beta.atcoder.jp/contests/code-festival-2018-quala/submissions/3244005

以下の解法はBITや二分探索を使ったO(NlogN)解法だが、累積和と尺取法を使ったO(N)解法がある。
本質は変わらないが。

DPで解く。
dp[i] := i番目まで確定していて、i番目で給油をした場合の組み合わせ数
 
dp[0], dp[1], ... dp[i - 1]からdp[i]を更新することを考える。
遠すぎると、ガス欠になる。
i番目から左側で最も遠くて遷移できるGSがL番目であるとすると、これはlower_boundで探せる。
近すぎると、給油できない。
i番目から左側で最も近くて遷移できるGSがR-1番目であるとすると、これもlower_boundで探せる。
つまり、dp[L], ... dp[R-1]からdp[i]を更新することを考える。
 
dp[L]からdp[i]へ遷移するときを考えてみよう。
(L,i)の間はGSをすべて書店にするべきかを考える。
L番目で給油して、燃料がTリットル以上残る箇所は書店でなくても良い。
(L,i)の間で給油しない箇所をcntとすると、GSにするか書店にするかは2^cnt通りあるので、
dp[i] += dp[L] * 2^cnt
のように遷移することになる。
dp[L], ... dp[R-1]の総和がdp[i]となるなら単なるBITでやればいい。
遷移に係数がつくが、これは遷移元に依存した係数なので、BITに入れるときに係数を含めて入れておく。
よって、dp[L]*2^cntL, ... dp[R-1]*2^cntR1の総和がdp[i]となる。
 
i番目で給油すると、給油できなくなる箇所を探すのもlower_boundでできる。
その場合は、Xの最後に番兵を入れておこう。
 
最後にdp[0]~dp[N]をまとめると答え。

int D, F, T, N, X[101010];
BIT<mint> dp;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> D >> F >> T >> N;
    rep(i, 1, N + 1) cin >> X[i];
    dp.init(N + 1);
    X[N + 1] = inf;
 
    int ei = upper_bound(X, X + N + 1, F - T) - X;
    int cn = ei - 1;
 
    dp.add(0, mint(2) ^ cn);
    rep(i, 1, N + 1) {
        int L = lower_bound(X, X + N + 1, X[i] - F) - X;
        int R = lower_bound(X, X + N + 1, X[i] - (F - T)) - X;
 
        int either = upper_bound(X, X + N + 1, X[i] + (F - T)) - X;
        int cnt = either - i - 1;
 
        mint d = dp.get(L, R) * (mint(2) ^ cnt);
        dp.add(i, d);
    }
 
    mint ans = 0;
    rep(i, 0, N + 1) if (D - X[i] <= F) ans += dp.get(i, i + 1);
    cout << ans << endl;
}