AtCoder Regular Contest 072: E - Alice in linear land

,

http://arc072.contest.atcoder.jp/tasks/arc072_c

solution

後ろから見ていく。$O(N + Q)$。

$i$番目の直前で位置$a_i$に居るとして、$d_i$を変更しても計画が実行不能 $\iff$ 全ての$b \le d_i$から残りを動いて目的地に到着可能。 両辺否定すれば、$d_i$を変更しても計画が実行可能 $\iff$ ある$b \le d_i$が存在して目的地に到着不能。 特にそのようなものの最小値を$b_i$とおけば$b_i \le a_i$を見るだけとなる。

$a_i$は簡単に求まる。 $b_i$を求めるのは明らかでないが、整理すれば$b_{i + 1}, d_i$の関数の形の漸化式で求まる。

implementation

#include <cstdio>
#include <cstdlib>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
using namespace std;

int main() {
    // input
    int n, dd; scanf("%d%d", &n, &dd);
    vector<int> d(n); repeat (i, n) scanf("%d", &d[i]);

    // solve
    vector<int> a(n + 1);
    a[0] = dd;
    repeat (i, n) {
        a[i + 1] = min(a[i], abs(a[i] - d[i]));
    }
    vector<int> b(n + 1);
    b[n] = 1;
    repeat_reverse (i, n) {
        b[i] = b[i + 1] + (b[i + 1] <= d[i] / 2 ? 0 : d[i]);
    }

    // output
    int queries; scanf("%d", &queries);
    while (queries --) {
        int q_i; scanf("%d", &q_i); -- q_i;
        bool result = b[q_i + 1] <= a[q_i];
        printf("%s\n", result ? "YES" : "NO");
    }
    return 0;
}