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]); } }