AtCoder Grand Contest 026 : B - rng_10s
問題
りんごマートはある日の朝に開店し,その時にはジュースの在庫が 本ありました。 すぬけ君は毎日昼にりんごマートでジュースを 本買います。 りんごマートでは毎日夜にジュースの在庫を確認し, 本以下だった場合,次の日の朝までに 本在庫を追加します。
を繰り返すとき、永遠にすぬけ君がジュースを買い続けられるかどうかを判定する問題。
解法
明らかに Yes, No の場合があるのでそれを除いて考える(A >= B, D >= B, C >= B)。ここで、ジュースを追加するかどうかの目安の C より大きく、B 以下だと No になるので、これにいつか当てはまるかどうかを判定したい。
B ずつジュースは減っていくので mod B で考える。y = (A + Dx) mod B のグラフで考えると可視化されて個人的に分かりやすい(1本で繋がらないグラフになる)。あとはこの関数の最大値を知りたい、となるのだがこれが分からない。解説を読み、気持ちで B - gcd(B, D) を最大値とすると何故か通る。証明できない。
解答
Submission #2854653 - AtCoder Grand Contest 026
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;
LL T, A, B, C, D;
LL gcd(LL a, LL b)
{
if (a < b) std::swap(a, b);
LL r = a % b;
while (r != 0)
{
a = b;
b = r;
r = a % b;
}
return b;
}
int main()
{
in >> T;
rep(loop, T)
{
in >> A >> B >> C >> D;
if (A < B || B > D) out << "No" << std::endl;
else if (C >= B) out << "Yes" << std::endl;
else if (D%B == 0) out << (A%B <= C ? "Yes" : "No") << std::endl;
else
{
LL max = (B - A % B) - gcd(B, D) + A % B;
out << (max <= C ? "Yes" : "No") << std::endl;
}
}
return 0;
}