ABC294 F問題 Sugar Water 2

二分法探索

N本とM本の組み合わせですが、最大で $NM = 2.5\times 10^9$ となりうるため、すべての組み合わせを計算して、ソートして $K$ 番目を求めるのは時間がかかりすぎます。
$K$ 番目を求めたいけれど、ソートするのが大変な場合、二分法で探索することを考えます。

ある濃度 $p$ に対して、それ以上の濃度になるのが $K$ より多ければ $p$ は求める濃度よりも小さく、 $K$ より少なければ $p$ は大きいことがわかります。
そこで、ある濃度 $p$ より濃度が大きいか小さいかを高速に判定することができるか考えてみます。

砂糖 $x$ g と水 $y$ g の濃度 $p$ は、
$\frac{100x}{x+y} = p$
です。砂糖 $a$ g と水 $b$ g の砂糖水と、砂糖 $c$ g と水 $d$ g の砂糖水を混ぜたときの濃度が $p$ 以上になるのは
$\frac{100(a+c)}{(a+c)+(b+d)} \ge p$
のときですが、この式で計算しようとすると選んだ2本のペアごとに計算することになり、大変な計算量になります。
そこで次のように式を変形します。
$\left(100a - (a+b)p \right) + \left(100c - (c+d)p \right) \ge 0$
この式では $\left(100a - (a+b)p \right)$ の項は $(c,d)$ の値に関係なく計算できます。そこで、一方の高橋君が持っている砂糖水について $\left(100a - (a+b)p \right)$ を小さい順にソートしておいて、
青木君が持っている砂糖水それぞれについて、和が 0 以上になる、つまり
$-\left(100c - (c+d)p \right) \le \left(100a - (a+b)p \right)$
を満たす個数をカウントすればよいです。あらかじめソートしておくことで二分探索で最初に条件を満たすのが何番目かを探すことができ、一つ一つ比べなくても条件を満たす個数はわかります。
濃度 $p$ が変わるたびにソートをする必要がありますが、十分高速に求められます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N, M, K = readInts()

  A = zeros(Int,N)
  B = zeros(Int,N)
  C = zeros(Int,M)
  D = zeros(Int,M)

  for i=1:N
    A[i],B[i] = readInts()
  end

  for i=1:M
    C[i],D[i] = readInts()
  end

  # 濃度 p の二分探索
  p_u = 100.0
  p_l = 0.0
  while  p_u - p_l > 1.0e-10
    p = (p_u + p_l) * 0.5

    # 濃度が p 以上の組み合わせを数える
    E = [ 100*A[i] - p * (A[i] + B[i]) for i = 1:N ]
    F = [ 100*C[i] - p * (C[i] + D[i]) for i = 1:M ]
    sort!(E)
    num = 0
    for i = 1:M
      pos = searchsortedfirst(E, -F[i])
      num += N-pos+1
    end
    if num < K
      p_u = p
    else
      p_l = p
    end
  end

  println( p_u )

end  # function solve

# main
solve()