きろく

特筆すべき記録のまとめ

AtCoder Grand Contest 026 : B - rng_10s

 

問題

B - rng_10s

りんごマートはある日の朝に開店し,その時にはジュースの在庫が A 本ありました。 すぬけ君は毎日昼にりんごマートでジュースを B 本買います。 りんごマートでは毎日夜にジュースの在庫を確認し,C 本以下だった場合,次の日の朝までに D 本在庫を追加します。

を繰り返すとき、永遠にすぬけ君がジュースを買い続けられるかどうかを判定する問題。

 

解法

明らかに 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;
}

f:id:babcs2035:20180716145742p:plain