Google Code Jam 2008 Qualification Round : B. Train Timetable

続いて２問目。
http://code.google.com/codejam/contest/32013/dashboard#s=p1

A駅からB駅と、B駅からA駅のダイヤ、および折り返しにかかる時間が与えられる。
このダイヤを運行するのに最少の電車数を答える問題。

これは貪欲に、残ったダイヤのうち一番早い時間から電車が１つ出発し、AとBを交互に往復させてできるだけ多くのダイヤを満たす、という処理を繰り返せばよい。
Aが開始の場合とBが開始の場合があるので注意する。

int T,NA,NB;
int S[301],E[301];
int vis[301];


void solve(int _loop) {
	int i,j,k,resa,resb;
	int a,b,c,d;
	
	T=GETi();
	GET2(&NA,&NB);
	FOR(i,NA) {
		scanf("%d:%d %d:%d",&a,&b,&c,&d);
		S[i]=a*60+b;
		E[i]=c*60+d;
	}
	FOR(i,NB) {
		scanf("%d:%d %d:%d",&a,&b,&c,&d);
		S[i+100]=a*60+b;
		E[i+100]=c*60+d;
	}
	
	ZERO(vis);
	resa=resb=0;
	while(1) {
		//開始を求める
		int s=999999;
		k=0;
		FOR(i,NA) if(s>S[i] && !vis[i]){ s=S[i]; k=i;}
		FOR(i,NB) if(s>S[i+100] && !vis[i+100]){ s=S[i+100]; k=i+100;}
		if(s==999999) break;
		if(k<100) resa++;
		else resb++;
		
		while(1) {
			vis[k]=1;
			int nt=E[k]+T;
			s=999999;
			int nk=0;
			if(k>=100) {
				FOR(i,NA) if(s>S[i] && nt<=S[i] && !vis[i]){ s=S[i]; nk=i;}
			}
			else {
				FOR(i,NB) if(s>S[i+100] && nt<=S[i+100] && !vis[i+100]){ s=S[i+100]; nk=i+100;}
			}
			
			if(s==999999) break;
			k=nk;
		}
	}
	
	_PE("Case #%d: %d %d\n",_loop,resa,resb);
}

まとめ

よくありそうな問題だけど、開始地点がAでもBでもいいってのは斬新。