Kodamanと愉快な仲間たち : Z - Dishes 2

小技を組み合わせて解いていく問題。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/dishes-2

問題

N個の正整数対(A[i],B[i])が与えられる。
このうちのいくつかを選択し、(前者の総和)×(後者の総和)がKを超えるようにしたい。
最少で何個の整数対を選べばよいか。

解法

A[i]*B[i]≧Kになるような整数対があれば解1確定なので、それ以外の場合を考える。
この場合、整数対についてA[i]とB[i]のどちらかは√K以下である。
そのため、求める解において、Aの総和とBの総和の少なくともどちらかは2√K以下である点に留意する。

そこでまず以下を考えよう。
f(sa, n) := n個の整数対を選んだ時、A[i]の総和がsaの場合におけるB[i]の総和の最大値
g(sb, n) := n個の整数対を選んだ時、B[i]の総和がsbの場合におけるA[i]の総和の最大値

sa*f(sa, n)≧Kまたはsb*g(sb, n)≧Kを満たすsa,sb,nがあればそれが解になる。
この場合、sa,sbは上記推察より2√Kまで調べればよいので、このDPはO(NK)になる。
ただこれでもまだ足りない。

解が大きい場合、同じ構成の対を複数回取ることが考えられる。
逆に複数回取らないなら、M種類の異なる対を選ぶとA[i]とB[i]の少なくとも片方は√M以上にならないといけないので、A[i]やB[i]は割と多くなる。
この推考を元に、先のf(sa,n)やg(sb,n)を埋めるのを高速化しよう。
同種の整数対を複数取るケースは個数制限ナップサック問題に落とし込めるので、1個1個個別にDPするよりまとめて行えて早くなる。

int N,K;

map<int,int> B[2][1010100];
set<pair<int,int>> S;
ll dp[2010][2010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x>>y;
		if(1LL*x*y>=K) return _P("1\n");
		B[0][x][y]++;
		B[1][y][x]++;
		S.insert({x,y});
	}
	
	int R=S.size();
	int cand=2*sqrt(K/R)+1;
	
	int ret=1<<20;
	FOR(i,2) {
		FOR(x,2010) FOR(y,2010) dp[x][y]=-1LL<<60;
		dp[0][0]=0;
		for(x=1;x<=1000;x++) {
			vector<pair<int,int>> V;
			FORR(m,B[i][x]) V.push_back(m);
			reverse(ALL(V));
			if(V.size()>cand) V.resize(cand);
			int num=0;
			ll sum=0;
			FORR(m,V) num+=m.second,sum+=1LL*m.second*m.first;
			while(V.size()>=2 && x*(num-V.back().second)*(sum-1LL*V.back().second*V.back().first)>=K) {
				num-=V.back().second;
				sum-=1LL*V.back().first*V.back().second;
				V.pop_back();
				ret=min(ret,num);
				cand=min(ret,cand);
			}
			FORR(m,V) {
				for(y=0;y<=2000;y++) {
					for(r=y/x;r<=cand;r++) {
						if(r!=0 && y>=x) break;
						deque<pair<int,ll>> D;
						int num=r;
						for(int b=y;b<=2000;b+=x) {
							
							if(D.size()&&D.front().first+m.second<num) D.pop_front();
							while(D.size() && D.back().second+(num-D.back().first)*m.first<=dp[b][num]) D.pop_back();
							if(dp[b][num]>=0) D.push_back({num,dp[b][num]});
							if(D.size() && dp[b][num]<D.front().second+(num-D.front().first)*m.first) {
								dp[b][num]=D.front().second+(num-D.front().first)*m.first;
								//cout<<"!"<<x<<" "<<b<<" "<<num<<" "<<dp[b][num]<<endl;
							}
							if(dp[b][num]>=0 && b*dp[b][num]>=K) ret=min(ret,num);
							num++;
							if(num>=cand || num>=ret) break;
						}
					}
				}
			}
		}
		
		/*
		for(x=1;x<=2000;x++) for(y=1;y<=2000;y++) if(dp[x][y]>=1) {
			cout<<i<<" "<<x<<" "<<y<<" "<<dp[x][y]<<" "<<(x*dp[x][y]>=K)<<endl;
		}
		*/
		for(x=1;x<=2000;x++) for(y=1;y<=2000;y++) if(y<ret && dp[x][y]>=0 && 1LL*x*dp[x][y]>=K) {
			ret=y;
		}
		
	}
	if(ret==1<<20) ret=-1;
	cout<<ret<<endl;
	
	
	
}

まとめ

お疲れ様でした。