TopCoder SRM 372 Div1 Easy RoadConstruction

問題

n本の車線のそれぞれに車の列がある。
車は以下のようにして順に車線から出る。

• 同じ車線で、自分より前に車がいる車は出られない
• より低い番号の車線に、出ようとしている車がいる車は出られない
• 最初自分が車線の最初にきたら、一度だけより高い番号の車線の車に道をゆずる
• 以上のどれにも該当しない車が出る。

このとき、'D'の車の前に車線から出る車は何台か、求めよ。

制約条件

車線の数≦50
それぞれの車線にいる車の数≦50
車は一文字のアルファベットで表される。別の車が同一のアルファベットを持つ場合がある。

方針

定義にしたがって実装する。
車に適当にユニークなIDを割り振った。
道を一度ゆずった車のIDは覚えておき、二度目は譲らずに自分が出るようにする。

再帰で書いた。

ソースコード

set<int> s;
vector<vi> c;
int func(int a,int b){
	for(;a<c.size()&&c[a].empty();a++);
	if(a==c.size())return -1;
	
	if(s.count(c[a][0])){
		int res=c[a][0];
		c[a].erase(c[a].begin());
		return res;
	}
	s.insert(c[a][0]);
	int res=func(a+1,b);
	if(res==-1){
		res=c[a][0];
		c[a].erase(c[a].begin());
		return res;
	}
	return res;
}
class RoadConstruction {
	public:
	int getExitTime(vector <string> currentLanes) 
	{
		int a=0;
		c=vector<vi>(currentLanes.size());
		map<int,char> ch;
		rep(i,currentLanes.size())rep(j,currentLanes[i].size()){
			c[i].pb(i*100+j);
			ch[i*100+j]=currentLanes[i][j];
		}
		s.clear();
		
		for(;;){
			if(ch[func(0,0)]=='D')return a;
			a++;
		}
	}
};