ARC050 B問題：花束

問題. 花束

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

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

解法．二分探索

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

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

　条件1.　k≤s1+s2$k\le s_1+s_2$
　条件2.　xs1+s2≤R$x{s}_1+s_2\le R$
　条件3.　s1+ys2≤B$s_1+y{s}_2\le B$
　条件4.　0≤s1,s2$0\le s_1,s_2$ （s1,s2$s_1,s_2$ は整数）

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

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

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

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

ソースコードを表示

#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;
}

上の条件式の同値変形を直感的に解釈すると 解説 のようになるけど，正しさは数式を上の様に変形したほうが分かりやすいと思う．
上の定式化の幾何的解釈を考えると面白いけど図とかを書くの大変なので書きたくなーい．