Codeforces #377 Div2 D. Exams

すんなり解けて良かった。
http://codeforces.com/contest/732/problem/D

問題

N日間の各日には、M種類のうちいずれかの試験が行われる可能性がある。
あなたは何日かの試験に参加し、最終的に全種類１回ずつ試験に受からなければならない。

試験の無い日はいずれかの試験の勉強ができる。
i番の試験に受かるには、事前にA[i]日占有して試験勉強をしなければならない。
全試験に合格するには、最短何日かかるか。

解法

二分探索で解く。
各試験は、できるだけ遅い日程で受ける方が試験勉強の時間が確保できてよい。
よって終わりの日を決めると、各試験を受ける日が確定する。
後は試験時間が確保できるか見ていけば良い。

以下のコードは後ろから見ていって、先頭までさかのぼった際に必要な試験時間が確保できるか見ていっている。

int N,M;
int D[101010];
int A[101010];

int did[101010];
int P[101010];
int ok(int d) {
	if(d<=0) return 0;
	
	ZERO(did);
	int a=0;
	int i;
	int prac=0;
	for(i=d-1;i>=0;i--) {
		if(D[i]>0 && did[D[i]-1]==0) {
			prac+=A[D[i]-1];
			did[D[i]-1]=1;
			a++;
		}
		else {
			prac=max(0,prac-1);
		}
	}
	if(a<M || prac>0) return 0;
	return 1;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>D[i];
	FOR(i,M) cin>>A[i];
	
	if(ok(N)==0) return _P("-1\n");
	int ret=N;
	for(i=20;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i;
	cout<<ret<<endl;
	
}

まとめ

今回ACは取れたものの最初無駄なコードを書いてしまったものが多い。
他の人の短いコードを読むのは勉強になる。