AGC026-B:rng_10s(600)

問題

https://beta.atcoder.jp/contests/agc026/tasks/agc026_b

最初在庫が a 本ある。在庫から b 本減らす。c 本以下の時、在庫に d 個補充する。という操作を繰り返し実施した時、常に在庫が b 本以上あるかどうかを判定せよ。

  • 制約 1 <= t <= 109
    1 <= a,b,c,d <= 109
    入力値は整数

まず自明なケースを処理する。

(i) a - b < 0
一回目に b 本減らすときに在庫が負になるので false.

(ii) b > d
補充する本数よりも減らす本数のほうが小さいのでいずれ在庫はなくなる。false.

(iii) b <= c (a >= b, b <= d)
減らしたタイミングでは常に補充されるため、在庫がなくなることはない。true.


それ以外のケースについて考える。よって仮定は

  • b <= a
  • b <= d
  • c < b

としてよい。

ある時の在庫数を x とする。在庫が負になるタイミングについて考察すると、

c < x < b

である。つまり、在庫が c より大きいので補充はされないが、b よりも小さいので、次の b を減らす操作で在庫数が負になる数である。
x がこの範囲に入りうる場合は false.そうでない場合は true と考えることができる。よって c よりも大きい最小の x について考える。

x は最初の在庫数 a から、任意の回数分 d 足して、任意の回数分 b 引くことができるので g = gcd(b, d) とすると

x = a % g + k * g

と表すことができる。

c < x < b となる x が存在する時、c よりも大きい最小の x が b 未満になっていることを確認すればよい。半開区間 [c + 1, b) で考えよう。

c+1 以上の最小の x は

c + 1 <= a % g + k * g
(c + 1 - a % g) / g <= k
∴ k = ceil((c + 1 - a % g) / g)

として x = a % g + k * g であることがわかる。これが x < b となっていれば false, そうでなければ true である。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int t = in.nextInt();
            while (t-- > 0) {
                long a = in.nextLong();
                long b = in.nextLong();
                long c = in.nextLong();
                long d = in.nextLong();

                if (a < b) {
                    out.println("No");
                    continue;
                }

                if (d < b) {
                    out.println("No");
                    continue;
                }

                if (b <= c) {
                    out.println("Yes");
                    continue;
                }

                long g = gcd(b, d);
                long k = (c - a % g + g) / g;
                if (a % g + g * k < b) {
                    out.println("No");
                    continue;
                }

                out.println("Yes");
            }

        }

        long gcd(long a, long b) {
            return (b == 0) ? a : gcd(b, a % b);
        }

雑記

  • 不定方程式の形 ( a * x + b * y = n )では、g = gcd(x, y) を取ることで g * l = n のように変数をへらすことができるので考察しやすくなることがある。
  • mod B の操作は実は思いつかなくても解ける。