Codeforces ECR #003 : D. Gadgets for dollars and pounds

全完したけど、本番の解法Dは結構計算量怪しいので書き直した。
http://codeforces.com/contest/609/problem/D

問題

M種類のおもちゃがあるので、そのうちK種類を購入したい。
各おもちゃはドルかポンドで値付けされており、その価格はC[i]である。

ここで、プレイヤーはSルーブルのお金を持っている。
プレイヤーはおもちゃをN日間のどこかで買うことができる。
i日目は、1ドルの価値はA[i]ルーブル、1ポンドの価値はB[i]ルーブルである。

K種のおもちゃを購入するのに必要な最短日数を求めよ。

解法

1日に何種類でもおもちゃが購入可能なので、例えばd日の間におもちゃを購入するのであれば、ドル・ポンドそれぞれそのうち最安値の日で買えばよい。

d日でK個買えるかどうかを高速に判定できれば、あとはdの二分探索でよい。
よってそのような判定をO(N)で行おう。

最初にドルで買えるおもちゃ、ルーブルで買えるおもちゃをそれぞれ安い順に並べ、累積和を取っておく。
ドルで買えるおもちゃを安い順にx個買う場合、ルーブルで買うおもちゃは安い順に(K-x)個買う必要があり、その総額は累積和を使えばO(1)で求められる。
よってドルで買うおもちゃの個数xを総当たりすれば判定できる。

int N,M,K,S;
int A[202020], B[202020], T[202020], C[202020], RA[1000100], RB[1000100];
vector<pair<int,int> > PP[2];
ll sum[2][202020];

ll num[202020];

int ok(int d,int out) {
	int j,x,y;
	
	
	FOR(j,PP[0].size()+1) {
		int x=K-j;
		if(x<0) break;
		if(x>PP[1].size()) continue;
		if(sum[0][j]*A[d]+sum[1][x]*B[d]<=S) {
			if(out) {
				_P("%d\n",d+1);
				FOR(y,j) _P("%d %d\n",PP[0][y].second,RA[A[d]]+1);
				FOR(y,x) _P("%d %d\n",PP[1][y].second,RB[B[d]]+1);
				exit(0);
			}
			return 1;
		}
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K>>S;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(i,N) if(i) {
		if(A[i]<A[i-1]) RA[A[i]]=i;
		else A[i]=A[i-1];
		if(B[i]<B[i-1]) RB[B[i]]=i;
		else B[i]=B[i-1];
	}
	FOR(i,M) {
		cin>>T[i]>>C[i];
		T[i]--;
		PP[T[i]].push_back({C[i],i+1});
	}
	sort(ALL(PP[0]));
	sort(ALL(PP[1]));
	
	MINUS(num);
	FOR(i,2) FOR(j,PP[i].size()) sum[i][j+1]=sum[i][j]+PP[i][j].first;
	
	if(ok(N-1,0)==0) return _P("-1\n");
	int d=N-1;
	for(i=20;i>=0;i--) if(d-(1<<i)>=0 && ok(d-(1<<i),0)) d-=1<<i;
	ok(d,1);
	
}

まとめ

本番なんであれで通ったんだ。