roiti46's blog

主に競プロ問題の解説を載せてます

Atcoder Regular Contest 037 C:億マス計算

条件判定を間違えていたため本番中は通せず・・・。

問題はこちら

問題

N個の正の整数からなる数列aとbを与えられる。ai × bj (0 <= i, j < N)を昇順に並べたとき、K番目の数を答えよ。max(N) = 30000, max(a) = max(b) = 109

解法

二分探索で解ける。二分探索の下限と上限と中央値をそれぞれlow, high,midとする。

まずaとbをソートしておく。 mid以下の値の数kは、各行ごとにmid以下の数がいくつあるかを二分探索で計算できるので、NlogNで数えることができる。

ai × bjの値がほかの値と重複する場合があるので k == K とはならないケースがあることに注意する。二分探索により k >= K となるmidの最小値(つまりhigh)を計算できるので、それが答えである。

#include <iostream>
#include <algorithm>
#define REP(i,a,b) for (int i = (a); i < (int)(b); i++)
#define rep(i,a) REP(i,0,a)
typedef long long ll;
using namespace std;
 
int N, K;
long long a[30010], b[30010];
 
int main(void){
    cin >> N >> K;
    rep(i, N) cin >> a[i];
    rep(i, N) cin >> b[i];
 
    sort(a, a + N);
    sort(b, b + N);
    
    ll low = 0, high = (1LL << 61);
    ll mid = (low + high) / 2;
    while (low + 1 < high) {
        int k = 0;
        rep(i, N) {
            if (mid < b[i]) break;
            int pos = upper_bound(a, a + N, mid / b[i]) - a;
            k += pos;
        }
        
        if (k >= K) high = mid;
        if (k <  K) low  = mid;
 
        mid = (low + high) / 2;
    }
    
    cout << high << endl;
    return 0;
}

まとめ

通せなかったが、すんなり解法を考えついたのはよかった。 解法は思いつけても実装でつまずくことが多いので練習が必要だ。