ARC037 C 億マス計算

2015/04/19 (Sun) ARC AtCoder 二分探索 数学

問題

問題文

方針

$f(x)$ を表全体に含まれる $x$ 以下の数の個数と定義すると、 $f(x) \geq K$ となる最小の $x$ が答えとなります。 $f(x)$ は単調増加なのでそのような $x$ は二分探索で求めることができます。

$f(x)$ を計算するのも二分探索で可能で、 全ての行をはじめにソートしておくと、 $i$ 行目に $b_i x$ 以下の数がいくつ含まれるかを求められます。 これを各行について求めて足し合わせます。

全体の時間計算量は $O(N \log ( N ) \log ( \max a_i b_i ) )$ です。

実装

// x以下の数の個数
int f(int N, int K, vi & a, vi & b, int x){
    int cnt = 0;
    rep(i,N){
        int l = -1;
        int r = N;
        while(l+1 < r){
            int m = (l+r)/2;
            if(a[i] * b[m] <= x){
                l = m;
            } else {
                r = m;
            }
        }
        cnt += r;
    }
    return cnt;
}

int solve(int N, int K, vi & a, vi & b){
    sort(all(a));
    sort(all(b));
    int l = 0;
    int r = a[N-1]*b[N-1];
    while(l + 1 < r){
        int m = (l+r)/2;
        int c = f(N,K,a,b,m);
        dump(m,c);

        if(c >= K){
            r = m;
        } else{
            l = m;
        }
    }
    return r;
}

signed main(){
    int N,K;
    vi a(N), b(N);
    rep(i,N) cin >> a[i];
    rep(i,N) cin >> b[i];
    cout << solve(N,K,a,b) << endl;
}