ferinの競プロ帳

競プロについてのメモ

AGC026 B - rng_10s

AtCoder 競技プログラミング 要復習

問題ページ

思考過程

  • よくわからないのでサンプルを試してみる
  • i日目の昼にxで回ってきたら次に補充されるタイミングには x%b 個になってそう
  • x%b > c であれば補充できず、mod bなのでb未満なので続けられなくなる
  • よくよく考えてみると b > c のときとかがこの計算はやばそう
  • a,b,c,dの大小関係からやばそうなケースを場合分けして計算できないかと考える
  • まずa<bのときは1日目から買えない
  • 次にb>dのときはジュースの総数が減っていくのが明らかなので無限には続かない
  • c>=b のときは昼にb個未満の状態で回ってくることはないため補充が追いつかなくなることはない
  • したがって c < b < d のケースのみ考えればよい
  • このケースであれば上で述べたx個で回ってくれば補充されるタイミングではx%b個になることが言えそう
  • 補充されてx%b+d個で回ってきたあとで補充されるタイミングでは(x%b+d)%b = (x+d)%b個になる
  • 同様に考えていくと補充されるタイミングでは (x+kd)%b 個になる
  • 最初はx=aで開始する
  • したがって (a+kd)%b > c を満たすような正の整数kが存在するかどうか判定する問題になった
  • b,dが互いに素なら 0 <= (a+kd)%b < b の全ての数を取りうることが言えそう
  • gcdの倍数しか取らないみたいなことが言いたい
  • どうやって変形してもわからない
    -----解説を見た-----
  • 考察方針はあってたみたいで最後のパートは b-gcd(b,d) + a%g が (a+kd)%b が取りうる最大になるらしい
  • これがcより大きければ答えはNoでc以下であれば答えはYesとなる

解説に載ってる証明を少し考えてみる。(A+kD)%B は mod gで考えると常にA%gとなるはず。したがって答えとしては(gの倍数) + A%g の形になる。mod BなのでB-1以下となるという前提で考えるとB-gより大きいgの倍数が来ることはありえない。したがって(A+kD)%Bの上界がB-g+A%gであることが言える。

gcdまでは思いついたがそのあとの式変形を思いつく気がしないので要復習

gcdを思いつくのは

  • A-Bx+Dy の形からベズーの補題、拡張ユークリッドあたりで-Bx+Dyはgcd(B,D)の倍数になる
  • 上と同様に kD % B はgcd(B,D)の倍数になる
    あたり？
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using PII = pair<int, int>;
template <typename T> using V = vector<T>;
template <typename T> using VV = vector<V<T>>;
template <typename T> using VVV = vector<VV<T>>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll INF = (1LL<<60);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool used[10000];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int t;
  cin >> t;
  REP(test, t) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if(a < b) {
      cout << "No" << endl;
      continue;
    }
    if(b > d) {
      cout << "No" << endl;
      continue;
    }
    if(b == d) {
      if(c >= b) {
        cout << "Yes" << endl;
      } else {
        if(a%b <= c) cout << "Yes" << endl;
        else cout << "No" << endl;
      }
      continue;
    }
    if(c >= b) {
      cout << "Yes" << endl;
      continue;
    }
    int g = __gcd(b, d);
    int ma = b - g + a%g;
    if(ma > c) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
  }

  return 0;
}