問題
を初期値として
- を引く
- 以下だったらを足す
という操作を繰り返したとき以上で無限ループになるか判定せよ。
解法
1時間考えてもわからなかったので解説PDFを読んだ。以下はそのまま。
まずすぐわかる場合を省きにいく。なら初日で買えないのでfalse。ならどうあがいても減っていくのでfalse。なら全て無くなる前に必ず入荷が入り、先の条件からは仮定できるのでtrue。
残りの場合について、個数の遷移をで見ていくと
- 最初は
- 購入では不変
- 入荷すると増える
であり、これがを超えることがあるかどうかが判定結果。これの最大値はとしてであるため、これをと比較すればいい。
最後の理屈は少しわかりにくいが、解説放送を観るとわかりやすいかもしれない。
反省
tex:\mathrm{mod} \; 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; } }