yukicoder : No.949 飲酒プログラミングコンテスト

ちょっと苦戦。
https://yukicoder.me/problems/no/949

問題

2人で問題を解くことを考える。
それぞれi杯のお酒を飲んだ後の貢献度をA[i],B[i]とする。
A,Bはいずれも単調減少である。

これからN個の問題を解くことを考える。
それぞれの難易度はD[i]とする。

問題を解くにあたり、2名のどちらかがお酒を1杯飲む。
その後、両者の貢献度の和が難易度以上であればその問題を解ける。
問題を解く順番は任意で良く、同じ問題は2度解けないとき、2人で最大何問の問題を解けるか。

解法

先に問題の難易度を降順で並べておく。
当然、難しい問題は早めに解いた置いた方が良い。

f(x,y) := 2人がx,y杯お酒を飲み、計(x+y)個の問題を解いた状態に到達したとき、その状態に至る最後の問題のうち最も若い番号
とする。f(x,y)からf(x,y+1)またはf(x+1,y)に遷移することを考えよう。
一見O(N^3)に見えるが、尺取り法の要領で均しでO(N^2)に収まるはず。

int N;
int A[3030];
int B[3030];
int ok[3030][3030];
int D[3030];
int pre[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N+1) cin>>A[i];
	FOR(i,N+1) cin>>B[i];
	FOR(i,N) cin>>D[i];
	
	sort(D,D+N);
	reverse(D,D+N);
	FOR(x,N+1) FOR(y,N+1) pre[x][y]=N+1;
	pre[0][0]=-1;
	
	int ma=0;
	FOR(x,N+1) FOR(y,N+1) if(pre[x][y]<=N) {
		ma=max(ma,x+y);
		FOR(i,2) {
			int nx=x+(i==0);
			int ny=y+(i==1);
			if(nx<=N && ny<=N) {
				
				for(j=pre[x][y]+1;j<N;j++) if(A[nx]+B[ny]>=D[j]) {
					pre[nx][ny]=min(pre[nx][ny],j);
					break;
				}
			}
		}
	}
	cout<<ma<<endl;
}

まとめ

貢献度0はまだしもマイナスとは。