【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個増やして..を繰り返し反復しているのでは長くて計算が間に合わないので、 何か対策を考える必要があります。 →分からないので解説を読みました。
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;
私も理解が不十分なのですが、分からないところがあればコメントして下さい!(一緒に考えます)