ARC 37 C問題 億マス計算
制約からして二分探索なんだろうとは思ったが本番では解けなかった。
a,bを最初にソートしておき、付値関数C(x)として次のものを考える。
C(x): a[i]*b[j]<=xとなる組(i,j)がK個以上あればtrue、なければfalseを返す
a[i]*b[pos]<=x , a[i]*b[pos+1]>x のとき、a[i]x なるpos'について
pos>pos' が成り立つ。従ってC(x)はO(N)で計算できる。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) typedef long long ll; bool C(vector<ll> &a,vector<ll> &b,int K,ll x){ int n=a.size(); ll res=0; int pos=n-1; REP(i,n){ while(pos>=0 && b[pos]>x/a[i]){ pos--; } res+=pos+1; } if(res>=K) return true; else return false; } int main(){ int N,K; cin >> N >> K; vector<ll> a(N),b(N); REP(i,N) cin >> a[i]; REP(i,N) cin >> b[i]; sort(a.begin(),a.end()); sort(b.begin(),b.end()); ll lb=0,ub=a[N-1]*b[N-1]+2; while(ub-lb>1){ ll mid=(lb+ub)/2; if(C(a,b,K,mid)) ub=mid; else lb=mid; } cout << ub << endl; return 0; }