【AGC 026】B. rng_10s

問題文


コンビニエンスストアのりんごマートでは,りんごジュースを販売しています。

りんごマートはある日の朝に開店し,その時にはジュースの在庫が A本ありました。

すぬけ君は毎日昼にりんごマートでジュースを B本買います。

りんごマートでは毎日夜にジュースの在庫を確認し,C本以下だった場合,

次の日の朝までに D本在庫を追加します。

すぬけ君がジュースを永遠に買い続けられるかを判定して下さい。

つまり,ジュースを買おうとした時,必ず在庫が B本以上あるかどうかを判定して下さい。

すぬけ君以外がジュースを買うことはありません。

また,今回の問題では入力ケースは T個のクエリからなります。

制約


  • 1≤T≤300
  • 1≤A,B,C,D≤1018

考え方


  • 買えない場合

初期個数AよりBが多い場合(例.29個しかないのに30個買う)

DよりBが多い場合(夜に10個しか仕入れないのに昼に15個買うと、毎日在庫が減って底を尽きる!)

考えなければならないのが、購入した後のBの在庫数。

これがCより大きければ、買えません

例.

A=13,B=7,C=5の時、

在庫の個数が13個で、7個買ったら6個になり夜に補充もされないので買えない。

B個減らしてD個増やして..を繰り返し反復しているのでは長くて計算が間に合わないので、 何か対策を考える必要があります。 →分からないので解説を読みました。

f:id:inaba00032:20180715201008p:plain https://img.atcoder.jp/agc026/editorial.pdf

.....分からん!

考えたことをソースコードに長々とコメントアウトしてあります。

ソースコード



def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
T=int(input())
 
Query=[]
for i in range(T):
  Query.append(list(map(int,input().split())))
 
for i in range(T):
  while(True):
    if Query[i][0]%Query[i][1]>Query[i][2] or Query[i][0]<Query[i][1] or Query[i][1]>Query[i][3]:
      print('No')
      break;
    G=gcd(Query[i][1],Query[i][3]) #この倍数分の増減のみ考えれば良い
    '''
    A,B,C,DがQuery[i]の0,1,2,3に対応
    BmodG,DmodGは0(GはB,Dの約数であるため)よりmodGの世界で個数の増減はない。昼の購入で0個減少。夜の仕入れで0個増加。
    つまり、初期個数をAmodGとすると、個数は一定
    Bは買う個数であり、B-Gを考えると、買いきれない個数で出現しうる最大の個数が求まる。
    (G分の増減しかないため、B-Gが最大)
    但し、初期個数を考える必要がある。
    初期個数によってループする幅が一緒でも取りうる値は異なる。
    
    例:
    B=24,C=19,D=36 この時,G=12
    本来の個数を見るとGの倍数のみ増減することが分かります。

    A=31の場合 AmodG(本来の個数) 
    7(31)→7(7)→7(43)→7(19)→7(31)→...
    A=30の場合 AmodG(本来の個数)
    6(30)→6(6)→6(42)→6(18)→6(30)→...
    
    Bを超えない最大数について、初期個数を考慮すると、B-G+AmodGとなる。
    G>AmodGであるため、この数が購入数Bを超えることはない
    つまり、B-G+AmodG>CならばNo,そうでなければYes
    '''
    if Query[i][1]-G+Query[i][0]%G>Query[i][2]:
      print('No')
      break;
    else:
      print('Yes')
      break;

私も理解が不十分なのですが、分からないところがあればコメントして下さい!(一緒に考えます)