AtCoder Regular Contest 037 C - 億マス計算

問題

 N個の数列が二つ与えられ、それぞれa_1, \dots, a_Nおよびb_1, \dots, b_Nとする。これらを用いてNN列の表を、ij列目にはa_i \times b_jが書き込まれるように作成する。書き込まれた数字の中でK番目に大きい数字を求めよ。

解法

 K番目に大きい数字とは「その数字以下の数字がK個以上書き込まれているようなもののなかで最小の数字」である。これを二分探索する。

 ある数字X以下の数字が何個書き込まれているかは、あらかじめa_1, \dots, a_Nb_1, \dots, b_Nをソートしておけば、iを固定したときa_ib_jをかけた値がX以下となるjを二分探索で求めることができる。

 よって全体でa_1, \dots, a_Nb_1, \dots, b_Nの中での最大値をそれぞれA, Bとしたとき、計算量はO(N(\log{N})(\log{AB}))となりこの問題が解けた。

反省

 24分12秒(0WA)でAC。最初はよくわからなかったけどまずa,bをソートするんだろうなというのは思いついたところ。そしてサンプルの3個目について表を作ってみたらなんとなく各a_iに対してどこまで小さい数字かは二分探索で求めることができそうだなとわかり、また最近『K番目に大きい数字とは「その数字以下の数字がK個以上書き込まれているようなもののなかで最小の数字」』みたいな変換をARC101のMedian of Mediansでやったのを思い出して想定解がわかった。典型と言えるような変換なんだろう。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, K;
    cin >> N >> K;
    vector<ll> a(N), b(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (ll i = 0; i < N; i++) {
        cin >> b[i];
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    auto isOK = [&](ll x) {
        //x以下のものがK個以上あるか判定
        ll num = 0;
        for (ll i = 0; i < N; i++) {
            if (a[i] * b[0] > x) {
                //ここから先でx以下となることはない
                break;
            }
            if (a[i] * b[N - 1] <= x) {
                //全てx以下
                num += N;
                continue;
            }

            ll low = 0, high = N - 1;
            while (low + 1 != high) {
                ll mid = (low + high) / 2;
                (a[i] * b[mid] <= x ? low = mid : high = mid);
            }
            num += low + 1;
        }
        return num >= K;
    };

    ll ng = 0, ok = pow(1e9, 2) + 1;
    while (ng + 1 != ok) {
        ll mid = (ok + ng) / 2;
        (isOK(mid) ? ok = mid : ng = mid);
    }

    cout << ok << endl;
}