読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #377 Div2 D. Exams

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

問題

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

試験の無い日はいずれかの試験の勉強ができる。
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は取れたものの最初無駄なコードを書いてしまったものが多い。
他の人の短いコードを読むのは勉強になる。

広告を非表示にする