AtCoder Regular Contest 037 C - 億マス計算

ARC037に参加。Bでバグらせてちょっと時間食いましたがいつも通りCまで通してまぁOKという感じでした。「いつも通り」とか言ってるけど最近Cが簡単だからじゃないですかね…

問題:C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder

解法:まずAとBをソートする。考え方としては,ある数xは小さい方から何番目の数になるかということを考えて,2分探索することによって高速に小さい方からK番目の数を求める。
このやり方で問題になるのは「xが小さい方から何番目になるかということをどうやって求めるか」ということになるが,これは以下のようにやることができる。
Bはソートされているので,A[i]に対してA[i]*B[j]<=xになるのはどのjからかということはやはり二分探索で求める。
以下ソースコード

const int MAXN = 30030;
ll a[MAXN], b[MAXN];
int N, K;

int calc(ll num) {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        ll p = (num+a[i]-1)/a[i];
        int low = -1, high = N;
        while (high - low > 1) {
            int med = (high + low) / 2;
            if (b[med] >= p) high = med;
            else low = med;
        }
        ret += high;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < N; i++) {
        cin >> b[i];
    }
    sort(a, a+N);
    sort(b, b+N);
    ll low = -1, high = 1LL<<62;
    while (high - low > 1) {
        ll med = (high + low) / 2;
        if (calc(med) >= K) {
            high = med;
        } else {
            low = med;
        }
    }
    cout << low << endl;
    return 0;
}

前にupper_boundに対して嫌な思い出(Codeforces Round #296 (Div. 2) C. Glass Carving - mayoko’s diary)があったのでupper_boundは使わなかったが,普通upper_boundは二分探索してくれるらしいので問題なく使えばよかったですね。