ARC050 B - 花束 - mini notes

B - 花束

概要

赤い花がR本、青い花がB本ある。次の2種類の花束を好きなだけ作るとき、2種類の花束の合計の個数の最大値を求めよ。

赤い花がx本、青い花が1本の花束
赤い花が1本、青い花がy本の花束

制約

1 ≦ R, B ≦ 10^18
2 ≦ x, y ≦ 10^9

方針

2分探索を使う。

整数kについて、k個の花束が作れるかを考える。
条件を下記のように言い換えてみる。

赤い花がx-1本、赤い花が1本、青い花が1本の花束
赤い花が1本、青い花が1本、青い花がy-1本の花束

すると、k個の花束の1と2の内訳をどのようにしても、赤い花・青い花は少なくともk個ずつ使うことになる。
なので、赤い花の残りR - k個をすべて1の花束にあて、青い花の残りB - k個をすべて2の花束にあてたときに、それがk以上になることを確認すればよい。

感想

解説通りです。
cond内のR - k < 0 || B - k < 0 ではじくというのはなにげに重要です。

解答

Submission #4901952 - AtCoder Regular Contest 050

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll R, B;
ll x, y;
 
bool cond(ll k){
	// bool ret = ((R - k) / (x - 1) + (B - k) / (y - 1)) >= k;
	// cout << k << "," << ret << endl;
	if(R - k < 0 || B - k < 0) return false;
	return ((R - k) / (x - 1) + (B - k) / (y - 1)) >= k;
}
 
// condを満たす最大のxを求める(upper_bound)
// 全てのxが条件を満たさない場合は-1を返す(-1はとりえない値)
ll upper_bound_cond(){
	ll lb = -1;
	ll ub = LLONG_MAX / 2;
 
	while(ub - lb > 1){
		ll mid = (lb + ub) / 2;
 
		if(cond(mid)) lb = mid;   // Answer is in [mid, ub)
		else ub = mid;            // Answer is in [lb, mid)
	}
 
	// now lb + 1 = ub
	return lb;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
 
	cin >> R >> B;
	cin >> x >> y;
 
	cout << upper_bound_cond() << endl;
}