AtCoder Regular Contest 082 F - Sandglass

http://arc082.contest.atcoder.jp/tasks/arc082_d

問題概要

砂時計に合計X[g]の砂が入っている。砂は1秒に1[g]のペースで上から下に落ちる。砂時計はr1, r2, …, rK秒後にひっくり返される。ここでQ個のクエリ(ti, ai)が与えられるので、初めに砂時計の上の方にai[g], 下の方に(X-ai)[g]入っていた場合、ti秒後にもともと上だった方のパーツに砂が何g入っているか求めよ。

1 <= X <= 109

1 <= K <= 105

1 <= Q <= 105

解法

砂が一度でも全部どちらかに寄ってしまえば、あとの動きはaに関わらず同じになる。まだ一度も寄っていない場合はaに関する単純な一次式になる。というわけで

  • パーツAに全部寄った場合
  • パーツBに全部寄った場合
  • まだ一度も全部寄りになってない場合

の3パターンを持ちながらひっくり返しをシミュレーションしていけばよい。3番目のパターンを見ていればaがこれ以上/以下ならこっちのパーツに全部寄る、みたいな条件は出る。

感想

頑張って手元でいろいろ書いてたらできた

コード (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;


void main() {
    auto X = readln.chomp.to!long;
    auto K = readln.chomp.to!int + 2;
    auto RR = 0 ~ readln.split.map!(to!long).array ~ 10L^^10;
    auto R = (K-1).iota.map!(i => RR[i+1] - RR[i]).array;
    auto Q = readln.chomp.to!int;
    auto T = new long[](Q);
    auto A = new long[](Q);
    foreach (i; 0..Q) {
        auto s = readln.split.map!(to!long);
        T[i] = s[0];
        A[i] = s[1];
    }


    long[] sim0 = [0, X];
    long[] simX = [X, 0];
    long[] simN = [0, X];
    long ub = -1;
    long lb = 1L << 59;


    int q = 0;

    foreach (t; 0..K-1) {
        for ( ; q < Q && RR[t] <= T[q] && T[q] < RR[t+1]; q++) {
            debug {writeln([RR[t], T[q], RR[t+1]]);}
            debug {sim0.writeln; simX.writeln;}

            long ans;

            if (A[q] <= ub) {
                ans = max(0, sim0[0] - T[q] + RR[t]);
            } else if (A[q] >= lb) {
                ans = max(0, simX[0] - T[q] + RR[t]);
            } else if (t % 2 == 0) {
                ans = max(0, simN[0] + A[q] - T[q] + RR[t]);
            } else {
                ans = max(0, simN[0] - A[q] - T[q] + RR[t]);
            }

            if (t % 2)
                ans = X - ans;
            ans.writeln;
        }

        long d0 = min(sim0[0], R[t]);
        sim0[0] -= d0;
        sim0[1] += d0;
        swap(sim0[0], sim0[1]);

        long dX = min(simX[0], R[t]);
        simX[0] -= dX;
        simX[1] += dX;
        swap(simX[1], simX[0]);

        simN[0] -= R[t];
        simN[1] += R[t];
        swap(simN[0], simN[1]);

        if (t % 2 == 0)
            ub = max(ub, -simN[1]);
        else
            lb = min(lb, simN[1]);
    }
}