Coder-StrikeのOnline Finalに参加。
ABCを何とか解きレートがHighest更新した。Dもあと15秒だったのでもったいない…。
http://codeforces.com/contest/420/problem/B
問題
N人がチャットルームで会話しており、M件分のチャットルームの人の出入りのログが与えられる。
「チャットルームに誰か人がいる場合、その人は常にいる」という場合、その人はリーダーである可能性がある。
N人中リーダーの可能性がある人を列挙せよ。
解法
ログ中に登場しない人は、ずっとチャットルームにいたかもしれないしいないかもしれない。
ずっとチャットルームにいるなら、その人はリーダーの可能性があるので、ログに登場しない人は全員リーダーの可能性がある。
あとは各人ログ中初回のメッセージを見ることで、開始時にチャットルームにいたかいないか判断できる。
以後、ログを最初から再度以下のようにたどることで各人がリーダーかどうか判定できる。
最初全員がリーダーの可能性があると考えて、可能性がなくなった人を外していこう。
まず以下のように考えられる。
- 自分以外の人がいる状態でログイン → 入る前は他の人がいた=リーダーではない
- 自分以外の人がいる状態でログアウト → 出た後は他の人がいる=リーダーではない
また、以下の条件も考える。
- 一人だけの時間帯が複数回あり、そのような時間帯だった人が2人以上いる→どちらもリーダーではない
int N,M; char hoge[100001]; int msg[100001]; int ok[100005]; int inin[100005]; void solve() { int f,i,j,k,l,x,y; cin>>N>>M; FOR(i,N) ok[i]=0; FOR(i,M) { string SS; cin>>SS>>x; if(SS[0]=='+' && ok[x-1]==0) ok[x-1]=1; if(SS[0]=='-' && ok[x-1]==0) ok[x-1]=2; hoge[i]=SS[0]; msg[i]=x-1; } FOR(i,N) inin[i]=1; set<int> S; FOR(i,N) if(ok[i]==2) S.insert(i); if(S.size()>0) FOR(i,N) if(ok[i]==1) inin[i]=0; set<int> sg; FOR(i,M) { if(hoge[i]=='+') { S.insert(msg[i]); if(S.size()==1) sg.insert(msg[i]); if(S.size()>1) inin[msg[i]]=0; } else { if(S.size()==1) sg.insert(msg[i]); if(S.size()>1) inin[msg[i]]=0; S.erase(msg[i]); } } if(sg.size()>1) FOR(i,N) if(ok[i]) inin[i]=0; if(S.size()>0) FOR(i,N) if(ok[i] && S.find(i)==S.end()) inin[i]=0; _P("%d\n",count(inin,inin+N,1)); FOR(i,N) if(inin[i]) _P("%d ",i+1); _P("\n"); }
まとめ
複数回ログをたどるのがコツ。