CODE FESTIVAL 2018 qual A D

D - 通勤

問題

数直線状の道路があり，座標 $0$ に車が停まっている．車のガソリンタンクの容量は $f$ で，1 進む毎にガソリンを 1 消費する．なお車は負方向に走ったり，走る以外の方法でガソリンを消費することはできない．

また道路上にはガソリンスタンドが $n$ 箇所あり， $i$ 番目のガソリンスタンドは座標 $x_i$ にある．

ガソリンが満タンの状態からこの車は正方向に移動するが，ガソリンスタンドのある座標に着く度に以下のルールに則ってガソリンを補給する．

ガソリンの残量が $t$ 以上なら補給しない．
そうでなければガソリンを満タンまで補給する．

ガソリンスタンドの部分集合で，それら全てを潰しても車がガソリンを切らすことなく $d$ に着けるようなものの個数を求めよ．

制約

$0 \lt t \leq f \leq 10^9$
$1 \leq n \leq 10^5$
$0 \lt x_1 \lt \cdots \lt x_n \lt d \leq 10^9$

考察

$dp_i =$ 「$i$ 番目のガソリンスタンドでガソリンが満タンのとき， $d$ まで到達できるような $i + 1$ 番目以降の潰し方の数」とする．ここで，

$$ \begin{aligned} j &= \min \{j' \mid x_i + (f - t) \lt x_{j'} \} \\ k &= \min \{k' \mid x_i + f \lt x_{k'} \} \end{aligned} $$

とする．すると，

$(i, j)$ はスルーするので潰すか否かを自由に選べる．
$[j, k)$ は少なくとも 1 つは残さないといけず，残した中で一番前にあるものにてガソリンが満タンになる．

となる．後者で一番前に残ったものがどれかで場合分けすると，

$$ dp_i = 2^{j - i - 2} \sum_{k' = j}^{k-1} dp_{k'} $$

となる． $j, k$ はupper_bound()で求められて，DP テーブルは後ろから埋めていけば区間和にセグ木を使うことで十分高速に更新できる．

後は $d$ の扱いが厄介．普通はガソリンスタンドとみなして，距離 $f - t$ 以内にあるときは(潰すか否かを自由に選べないので)除外するみたいな工夫が要る．

実装例

提出 #8114412 - CODE FESTIVAL 2018 qual A

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

template <int MOD>
class ModInt { ... };

template <class Data, class Operator>
class SegmentTree { ... };

constexpr int MOD = 1e9 + 7;
using mint = ModInt<MOD>;

int main() {
    int d, f, t, n;
    std::cin >> d >> f >> t >> n;

    std::vector<int> xs(n);
    for (auto& x : xs) std::cin >> x;
    xs.insert(xs.begin(), 0);
    xs.push_back(d);

    SegmentTree<mint, mint> seg(
        n + 2, 0,
        [](mint a, mint b) { return a + b; },
        [](mint e, mint a) { return e; });

    seg.update(n + 1, 1);
    for (int i = n; i >= 0; --i) {
        int x = xs[i];
        int j = std::upper_bound(xs.begin(), xs.end(), x + f - t) - xs.begin();
        // (i, j): arbitrary chosen

        if (j == n + 2) {
            seg.update(i, (mint(2) ^ (j - i - 2)));
            continue;
        }

        int k = std::upper_bound(xs.begin(), xs.end(), x + f) - xs.begin();
        // [j, k): either of them is chosen

        seg.update(i, (mint(2) ^ (j - i - 1)) * seg.query(j, k));
    }

    std::cout << seg.query(0, 1) << std::endl;
    return 0;
}