ARC 037 C - 億マス計算

問題

問題概要

100マス計算のようなマスが与えられる。その中で積の値が、小さいほうから数えて、K番目に位置する値を求めよ。

解法

editorialがわかりやすい。

AtCoder Regular Contest 037 解説 from AtCoder Inc.

www.slideshare.net

答えをmidとすると、積がmid以下の数が、K個以上になる最小のmidが答えとなる。midはを大きくすれば、積がmid超える数も単調増加であるので、midの値を二分探索で解ける。mid以下の数を数える方法は、i行目の中で掛け算してmid以下の数は、ai * bj <= mid つまり、 bj <= mid / ai となる。よって、bの中で、mid / ai となる数を調べればわかる。その数はbをソートしておけば、二分探索で高速に求まる。このようにすれば、全体の中での積がmid以下となる数も求まる。

ミス

できなかった。

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const ll INF = 1e18;

int n, k;
int main(void){
    cin >> n >> k;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    ll l = 0, r = INF + 1;
    while(r - l > 1){
        ll mid = (l + r) / 2;
        ll cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            //ai * bj <= mid  bj <= mid / ai
            auto it = upper_bound(b.begin(), b.end(), mid / a[i]);
            //bの中で、k / ai　以下である個数を足す
            cnt += it - b.begin();
        }
        if(cnt < k){
            l = mid;
        }else{
            r = mid;
        }
    }

    for (ll pos = l; pos <= r; ++pos)
    {
        ll cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            //ai * bj <= mid  bj <= mid / ai
            auto it = upper_bound(b.begin(), b.end(), pos / a[i]);
            //bの中で、k / ai　以下である個数を足す
            cnt += it - b.begin();
        }
        if(k <= cnt){
            printf("%lld\n", pos);
            return 0;
        }
    }
}