ARC050-B：花束

問題

https://beta.atcoder.jp/contests/arc050/tasks/arc050_b

赤い花が R 本、青い花が B 本ある。以下の条件を満たすように花束を作る時最大いくつつくれるか？

  1. x 本の赤い花と 1 本の青い花からなる花束
  2. 1 本の赤い花と y 本の青い花からなる花束

考え方

最大の花束の数を k としよう。1, 2の花束の数をそれぞれ m, n 個作れるとして、「 k 個の花束を作れるか」という Yes / No 問題を考える。制約条件は

  • m + n = k

  • mx + n \le R
    \Leftrightarrow mx + (k - m) \le R
    \displaystyle \Leftrightarrow m \le \frac{R - k}{x - 1}

  • m + ny \le B
    \Leftrightarrow (k - n) + ny \le R
    \displaystyle \Leftrightarrow n \le \frac{R - k}{y - 1}

である。上記を満たすような最大の k を二分探索で求めれば良い。

public void solve(int testNumber, InputReader in, PrintWriter out) {

    long R = in.nextLong(), B = in.nextLong();
    long x = in.nextLong(), y = in.nextLong();

    long l = 0, r = Long.MAX_VALUE/3;
    while (r - l > 1) {
        long k = (r+l)/2;

        if (k <= (R-k)/(x-1) + (B-k)/(y-1)) {
            l = k;
        } else {
            r = k;
        }
    }
    out.println(l);
}

ポイント

  • 解を仮定して二分探索