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)

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