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; }
まとめ
通せなかったが、すんなり解法を考えついたのはよかった。 解法は思いつけても実装でつまずくことが多いので練習が必要だ。