kmjp's blog

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

Google Code Jam 2014 Round 3 : C. Crime House

本番Smallだけ解いたけど、Largeは手が出ず。
https://code.google.com/codejam/contest/3024486/dashboard#s=p2

問題

初期状態で何人かの人が建物の内外にいる。
そこで、人の出入りのN行のログが与えられる。
出入りログでは、人の移動方向とそのIDを含む。
ただし、一部のログは人がマスクをしておりIDが不明であった。

ログを満たすような人の出入りは可能か。
また、可能なら最後に建物にいる最小人数を答えよ。

解法

ログが成り立たないのは、すでに建物内にいる人が再度建物に入ろうとしたり、逆に建物外の人が再度外に出ようとするログがある場合である。

Smallであれば、ログ中でIDが不明な場所に総当たりで既知のIDまたは新規IDを割り当て、ログを再生して矛盾が起きないか試せばよい。
Largeの場合はログが長くこの手法では間に合わない。

まず、最初から建物内にS人いると仮定する。
この場合、0人から初めて、ログの先頭に"E 0"をS個追加した、と仮定してログを再生すればよい。
Sを0~Nまで増やしていき、矛盾なくログを再生できる最小のSを求めると、その時のログ再生後の建物内人数が答えとなる。

基本的に、以後のログを先読みし、矛盾が起きにくくなるように不明なIDに人を割り当てる。
ログは以下のように再生する。

  • "E x"または"L x"、すなわちIDが判明している場合:
    • そのIDの人を建物内外に移動させる。矛盾する動きが生じる場合、再生は失敗である。
  • "E 0"の場合:
    • もし、「現在建物外にいるけど、そのIDの次のイベントが"L"の人」がいたら、そのうち次のイベントが最も近い人のIDを割り当て、建物に入れる。
    • 上記「~~人」が誰もいなければ、適当に空きIDの人を新規に生成し、建物に入れる。
  • "L 0"の場合:
    • もし、「現在建物内にいるけど、そのIDの次のイベントが"E"の人」がいたら、そのうち次のイベントが最も近い人のIDを割り当て、建物から出す。
    • 上記「~~人」が誰もおらず、かつ現在建物内にいて、以後イベントがない人がいたら、その人を建物外にだし、最終的に建物に残る人を減るようにする。
    • 上記どちらのケースでもない場合、現在建物内にいる人のうち、次のイベントが最も遅い人を(次のイベントまでにまた建物内に戻ってくることを期待して)建物外にだす。

"E 0"のケースと"L 0"のケースで微妙に処理が違うのがポイント。
それ以外はあまりややこしいことはなく、単に先読みを行うだけである。
O(N^3)かかるコードだけど何とか間に合う。

void solve(int _loop) {
	int f,i,j,k,l,x,y,s,t;
	
	int N;
	pair<char,int> Q[1001];
	int S[3005]; // 0-out 1-in
	vector<int> E[3005];
	int pos[3005];
	int NE=0, NL=0;
	
	_P("Case #%d: ",_loop);
	cin>>N;
	FOR(i,N) {
		cin>>Q[i].first>>Q[i].second;
		if(Q[i].first=='E') NE++;
		else NL++;
		if(Q[i].second>0) E[Q[i].second].push_back(i);
	}
	
	FOR(s,N+1) {
		t=s+NE-NL;
		if(t<0) continue;
		
		set<pair<int,int> > TBE,TBL;
		ZERO(S);
		ZERO(pos);
		FOR(i,3005) if(!E[i].empty()) {
			if(Q[E[i][0]].first=='L') TBL.insert(make_pair(E[i][0],i));
		}
		
		int nid=2001;
		FOR(i,s) {
			if(TBL.empty()) S[nid++]=1;
			else {
				pair<int,int> p=*TBL.begin();
				TBL.erase(TBL.begin());
				x=p.second;
				S[x]=1;
				if(pos[x]<E[p.second].size() && Q[E[x][pos[x]]].first=='E') TBE.insert(make_pair(E[x][pos[x]],x));
			}
		}
		int ng=0;
		FOR(i,N) {
			x=Q[i].second;
			if(x==0) {
				if(Q[i].first=='E') {
					if(TBL.empty()) {
						S[nid++]=1;
						continue;
					}
					pair<int,int> p=*TBL.begin();
					TBL.erase(TBL.begin());
					x=p.second;
				}
				else {
					if(TBE.empty()) {
						FOR(y,3005) if(S[y]==1 && pos[y]==E[y].size()) break;
						if(y!=3005) {
							S[y]=0;
							continue;
						}
						FOR(y,3005) {
							if(S[y]==1 && pos[y]<E[y].size() && Q[E[y][pos[y]]].first=='L') {
								if(x==0 || E[y][pos[y]] > E[x][pos[x]]) x=y;
							}
						}
						if(x==0) {
							ng=1;
							break;
						}
					}
					else {
						pair<int,int> p=*TBE.begin();
						TBE.erase(TBE.begin());
						x=p.second;
					}
				}
			}
			
			if(Q[i].first=='E') ng=S[x]==1, S[x]=1;
			else ng=S[x]==0, S[x]=0;
			if(ng) break;
				
			while(pos[x]<E[x].size() && E[x][pos[x]]<=i) pos[x]++;
			if(pos[x]<E[x].size()) {
				if(S[x]==0 && Q[E[x][pos[x]]].first=='L') TBL.insert(make_pair(E[x][pos[x]],x));
				if(S[x]==1 && Q[E[x][pos[x]]].first=='E') TBE.insert(make_pair(E[x][pos[x]],x));
			}
			if(ng) break;
		}
		if(ng) continue;
		return _P("%d\n",t);
	}
	_P("CRIME TIME\n");
}

まとめ

コードはややこしいけど、考え方は意外と単純。