ARC037 C - 億マス計算

問題：C - 億マス計算

解答：Submission #11627090 - AtCoder Regular Contest 037

解法：愚直にai * bjを全て計算してソートすると空間計算量・時間計算量ともに厳しい。

ai * bjを全て列挙し、昇順ソートした数列をvとする。 K番目に位置する数xが持つ特性として、当たり前ではあるが「vのK番目の値をau * bvとすると、x ≧ au * bv」の条件を満たす数のなかで最も小さい数ということである。また、ある数yがau * bv以上であるというのは、「vの中でy以下の数の個数がk個以上」ということである。

上記の条件は単調性をもつため、二分探索が適用できる。「vの中でy以下の数の個数がk個以上」の条件を確認する際は、aiを固定してai * bj ≦ xを満たすbjがいくつあるかを計算するが、これはbj ≦ x / aiとして配列bを二分探索すればよい。