本番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"); }
まとめ
コードはややこしいけど、考え方は意外と単純。