解説 | Safe Bridge

解説

危険度がa以下の橋にするための最小コストを $f(a)$ とします。 $f(a)$ はdpにより計算することができます。

$X_0=0, Y_0=0, X_{N+1}=L, Y_{N+1}=C$ とする
$dp_i$ を $i$ 番目の柱を建設するとき、それまでの柱のコストの合計の最小値と定義する
$dp_0=0,\ dp_i = \infty(i>0)$ で初期化する
$dp_i=$ ( $X_i-a \leq X_j < X_i$ を満たす $j$ について、 $dp_j$ の最小値+ $Y_i$ ) で更新する
$dp_{N+1}$ が $f(a)$ である

ここで、区間の最小値を取得する必要がありますが、セグメント木やスライド最小値で求められます。

$f(a)$ は広義単調減少なので、二分探索によって問題を解くことができます。全体の計算量はセグメント木解法なら $O(N\log N \log L)$ 、スライド最小値解法なら $O(N \log L)$ です。

実装例（segtree）

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
49
50
51
52#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using namespace atcoder;
using ll = long long;

const ll inf = 1LL << 60;
using S = ll;

S op(S a, S b) {
    return min(a, b);
}

S e() {
    return inf;
}

int main() {
    ll n, l, c;
    cin >> n >> l >> c;
    vector<ll> x(n + 2, 0), y(n + 2, 0);
    for(int i = 1; i <= n; ++i) cin >> x.at(i);
    for(int i = 1; i <= n; ++i) cin >> y.at(i);
    x.at(n + 1) = l;
    x.push_back(inf);

    auto calcCost = [&](ll maxDist){
        int leftIdx = 0;
        segtree<S, op, e> dp(n + 2);
        dp.set(0, 0);
        for(int i = 1; i <= n + 1; ++i){
            while(x.at(leftIdx) < x.at(i) - maxDist) leftIdx++;
            if(leftIdx < i){
                ll tmp = dp.prod(leftIdx, i) + y.at(i);
                dp.set(i, tmp);
            }
        }
        return dp.get(n + 1);
    };

    ll ng = -1, ok = l + 1;
    while(ok - ng > 1){
        ll mid = (ok + ng) / 2;
        if(calcCost(mid) <= c){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    cout << ok << endl;
    return 0;
}

実装例（スライド最小値）

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
49
50
51
52#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using P = pair<ll, ll>;
const ll inf = 1LL << 60;

int main() {
    ll N, L, C;
    cin >> N >> L >> C;
    vector<ll> X(N), Y(N);
    for(int i = 0; i < N; ++i) cin >> X.at(i);
    for(int i = 0; i < N; ++i) cin >> Y.at(i);

    X.push_back(L);
    Y.push_back(0);

    //危険度がmaxDist以下の橋の最小コストを計算
    auto calcCost = [&](ll maxDist){
        deque<P> que;//(pos, cost)、スライド最小値（Sliding Window Minimum)、単調増加列のみもつ
        que.push_back(P(0, 0));
        vector<ll> dp(N + 1, inf);
        for(int i = 0; i <= N; ++i){
            //dequeの先頭削除
            while(!que.empty() && X.at(i) - que.front().first > maxDist){
                que.pop_front();
            }
            if(!que.empty()){
                dp.at(i) = min(dp.at(i), que.front().second + Y.at(i));
            }
            //dequeに追加
            while(!que.empty() && que.back().second >= dp.at(i)){
                que.pop_back();
            }
            que.push_back(P(X.at(i), dp.at(i)));
        }
        return dp.at(N);
    };

    //二分探索
    ll ng = -1, ok = L + 1;
    while(ok - ng > 1){
        ll mid = (ok + ng) / 2;
        if(calcCost(mid) <= C){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    cout << ok << endl;
    return 0;
}

難易度評価

外部サイトへ移動します

Safe Bridge

解説

ユーザー解説