問題
個の数列が二つ与えられ、それぞれおよびとする。これらを用いて行列の表を、行列目にはが書き込まれるように作成する。書き込まれた数字の中で番目に大きい数字を求めよ。
解法
番目に大きい数字とは「その数字以下の数字が個以上書き込まれているようなもののなかで最小の数字」である。これを二分探索する。
ある数字以下の数字が何個書き込まれているかは、あらかじめとをソートしておけば、を固定したときとをかけた値が以下となるを二分探索で求めることができる。
よって全体でとの中での最大値をそれぞれとしたとき、計算量はとなりこの問題が解けた。
反省
24分12秒(0WA)でAC。最初はよくわからなかったけどまずをソートするんだろうなというのは思いついたところ。そしてサンプルの3個目について表を作ってみたらなんとなく各に対してどこまで小さい数字かは二分探索で求めることができそうだなとわかり、また最近『番目に大きい数字とは「その数字以下の数字が個以上書き込まれているようなもののなかで最小の数字」』みたいな変換を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; }