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

問題概要

自分の家が座標0, オフィスが座標Dにあり、N個のガソリンスタンドの座標が数列Xで与えられる。車の燃料タンクの容量がFで距離1の移動に燃料を1消費する。はじめ車の燃料は満タンで、ガソリンスタンドについたときの燃料がT未満のとき、またそのときにかぎり必ず燃料を満タンまで補給することにする。ガソリンスタンドの部分集合を選び、含まれないものは潰すとき、家からオフィスまで燃料が0未満にならないように移動できるような選び方は何通りあるか求めよ。

0 < T <= F <= 10⁹

N <= 10⁵

解法

dp(i) = 最後に燃料を補給したガソリンスタンドがi番目のときの,　i番目までのガソリンスタンドの選び方の総数

上のDPの遷移を考える。i番目のガソリンスタンドで補給して燃料満タンの状態で出発したとき、以降のスタンドは以下の3種類に分類できる（3番は明らかに関係ないので考えなくてよい）。

iからの距離が (F - T) 以下にあるスタンド
iからの距離が (F - T) より大きく F 以下であるスタンド
iからの距離が F より大きいスタンド

1の範囲のスタンドを通過するときは燃料がT以上なので補給は発生しない。つまりこの範囲のスタンドはどっちにしろ影響がないため、潰しても潰さなくてもよい。よってこの範囲のスタンドの数をkとすると、2^kの選び方がある。

2の範囲のスタンドを通過するときは燃料がT未満になっているのでスタンドが潰れていない限り必ず補給が発生する。仮にこの範囲の中に j, j+1, j+2 の3つのスタンドがあったとすると、そのままであれば次に補給が発生するのは j である。逆にいえば i の次 j+1 に止まるためには j が潰れている必要がある。i の次 j+2 に止まりたいときも同様に j, j+1 が両方潰れていなければならない。よって結局3つのうち次どれに止まる場合でも、潰し方に自由度があるのは結局1の範囲に存在するガソリンスタンドだけである。

よって上のDPの遷移は、上の j, j+1, j+2 の例をとると dp[j], dp[j+1], dp[j+2] に一律 dp[i] * 2^k を足す、という処理に落ち着く。この計算方法はいろいろやり方があると思うが、自分はDPテーブル自体をBinary Indexed Treeで持って区間加算するという感じでやった。iからの距離が(F-T)〜Fにあるスタンドの範囲を求めるのは二分探索とかしゃくとり法とかでできる。

感想

なんか細かいところで詰まってやたら時間かかってしまった

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto D = s[0].to!long;
    auto F = s[1].to!long;
    auto T = s[2].to!long;
    auto N = s[3];
    auto A = 0 ~ readln.split.map!(to!long).array;
    N += 1;

    auto P2 = new long[](N+1);
    P2[0] = 1;
    foreach (i; 0..N) P2[i+1] = P2[i] * 2 % MOD;

    auto bt = new BIT(N+1);
    bt.add(0, 1);
    bt.add(1, -1);
    long ans = 0;

    foreach (i; 0..N) {
        auto ub = A.assumeSorted.lowerBound(A[i] + F + 1).length.to!int;
        auto lb = A.assumeSorted.lowerBound(A[i] + F - T + 1).length.to!int;
        long num = bt.sum(0, i+1) * P2[max(0, lb - i - 1)] % MOD;
        bt.add(lb, num);
        bt.add(ub, -num);
        if (D - A[i] <= F) ans = (ans + num) % MOD;
    }

    ans = (ans % MOD + MOD) % MOD;
    ans.writeln;
}


class BIT{
    int n;
    long[] table;

    this(int x){
        n = x;
        table = new long[](x+1);
    }

    void add(int i, long x){
        i++;
        while (i <= n){
            (table[i] += x) %= MOD;
            i += i & -i;
        }
    }

    // [0, i]
    long sum(int i){
        i++;
        long ret = 0;
        while (i > 0){
            (ret += table[i]) %= MOD;
            i -= i & -i;
        }
        return ret;
    }

    // [l, r)
    long sum(int l, int r){
        if (l >= r) return 0;
        return (sum(r-1) - sum(l-1)) % MOD;
    }
}

nebukuro09の日記

CODE FESTIVAL 2018 qual A: D - 通勤

問題概要

解法

感想

コード (D言語)