ARC050 B問題：花束 - 忘れても大丈夫

問題. 花束

$R$ 個の赤い花と $B$ 個の青い花がある． $x$ 個の赤い花と1個の青い花からなる花束と，1個の赤い花と $y$ 個の青い花からなる花束の2種類の作り方がある．作ることのできる花束の個数の最大値を答えよ．

制約： $1 \le R, B \le 10^{18}$ ，　 $2 \le x, y \le 10^9$

解法．二分探索

1種類目の花束の個数を $s_1$ ，2種類目の花束の個数を $s_2$ とおくと次のようのな整数計画問題となる．
　　 $\max$ 　 $s_1 + s_2$
　　s.t.　　 $x s_1 + s_2 \le R$
　　　　　 $\,\,\,s_1 + y s_2 \le B$
　　　　　 $\,\,\,0 \le s_1, s_2$

ただし， $s_1, s_2$ は整数変数である．ここで，目的関数値 $s_1 + s_2$ が $k$ 以上となるような $s_1, s_2$ が存在するかを考える．すなわち，次の条件を満たす解が存在するかを考える．

　条件1.　 $k \le s_1 + s_2$
　条件2.　 $x s_1 + s_2 \le R$
　条件3.　 $s_1 + y s_2 \le B$
　条件4.　 $0 \le s_1, s_2$ （ $s_1, s_2$ は整数）

条件2の両辺に $s_1$ を足して条件1を用いて整理すると， $s_1 \le \frac{R - k}{x - 1}$ となる．同様に条件3に対して整理すると $s_2 \le \frac{B - k}{y - 1}$ となる．この条件を書き直すと次のようになる．

　条件1'.　 $k \le s_1 + s_2$
　条件2'.　 $s_1 \le \frac{R - k}{x - 1}$
　条件3'.　 $s_2 \le \frac{B - k}{y - 1}$
　条件4'.　 $0 \le s_1, s_2$ （ $s_1, s_2$ は整数）

条件2'と条件3'は $s_1$ と $s_2$ に対して独立な式である．また，条件1'を満たすためには $s_1, s_2$ はできるだけ大きな値を取るほうが良い．また，条件4'より $s_1, s_2$ は整数であることから，
　 $s_1 = \lfloor \frac{R - k}{x - 1} \rfloor$ ，　 $s_2 = \lfloor \frac{B - k}{y - 1} \rfloor$
となる．これは条件2', 3', 4' を満たすので後は条件1'を満たすかどうかを判定すればよい．したがって， $k$ を固定すると定数時間で判定でき，条件を満たすかどうかは $k$ に関してある値で二分されるので二分探索で答えを求めることができる．

計算時間： $O \left( \log (\min(R, B)) \right)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    ll R, B, x, y;
    cin >> R >> B >> x >> y;

    ll lb = 0, ub = min(R, B) + 1;
    while (1 < ub - lb) {
        ll m = (lb + ub) / 2;

        ll set1 = (R - m) / (x - 1);
        ll set2 = (B - m) / (y - 1);
        bool can_make = m <= set1 + set2;

        if (can_make) lb = m;
        else ub = m;
    }

    cout << lb << endl;

    return 0;
}