AtCoder Grand Contest 026 B - rng_10s

問題

　 $A$ を初期値として

$B$ を引く
$C$ 以下だったら $D$ を足す

　という操作を繰り返したとき $0$ 以上で無限ループになるか判定せよ。

解法

　1時間考えてもわからなかったので解説PDFを読んだ。以下はそのまま。

　まずすぐわかる場合を省きにいく。 $B > A$ なら初日で買えないのでfalse。 $B>D$ ならどうあがいても減っていくのでfalse。 $C\ge B$ なら全て無くなる前に必ず入荷が入り、先の条件から $B \le D$ は仮定できるのでtrue。

　残りの場合について、個数の遷移を $\mathrm{mod}\; B$ で見ていくと

最初は $A \mathrm{mod}\; B$
購入では不変
入荷すると $D \mathrm{mod}\; B$ 増える

　であり、これが $C$ を超えることがあるかどうかが判定結果。これの最大値は $g = \mathrm{gcd}(B, D)$ として $B - g + A \mathrm{mod}\; g$ であるため、これを $C$ と比較すればいい。

　最後の理屈は少しわかりにくいが、解説放送を観るとわかりやすいかもしれない。

反省

　tex:\mathrm{mod} \; Bで考えるという発想が出てこなかった。毎回 $B$ は引かれるわけで、この操作で不変な量ということで $\mathrm{mod} \; B$ に着目するというのはきっと普通のことなのだろう。ずっと $D - B$ と $-B$ の2通りの操作と考えてしまっていて、たいてい操作が複数あると難しい。

　しかしそこまでたどり着いたとしても正解が導ける自信はない。gcdを考えたりするのもある種の定跡なんだろうが、まだそこまでこの手の考え方には慣れていないと感じる。もっと鍛錬を積まなくては。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

ll gcd(ll a, ll b) {
    return (b ? gcd(b, a % b) : a);
}

bool solve(ll A, ll B, ll C, ll D) {
    if (B > A) {
        return false;
    } else if (B > D) {
        return false;
    } else if (C >= B) {
        return true;
    } else {
        ll g = gcd(B, D);
        return B - g + A % g <= C;
    }
}

int main() {
    ll T;
    cin >> T;
    vector<ll> A(T), B(T), C(T), D(T);
    for (ll i = 0; i < T; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    for (ll i = 0; i < T; i++) {
        cout << (solve(A[i], B[i], C[i], D[i]) ? "Yes" : "No") << endl;
    }
}