Coder-Strike 2014 Final - B. Online Meeting

Coder-StrikeのOnline Finalに参加。
ABCを何とか解きレートがHighest更新した。Dもあと15秒だったのでもったいない…。
http://codeforces.com/contest/420/problem/B

問題

N人がチャットルームで会話しており、M件分のチャットルームの人の出入りのログが与えられる。

「チャットルームに誰か人がいる場合、その人は常にいる」という場合、その人はリーダーである可能性がある。
N人中リーダーの可能性がある人を列挙せよ。

解法

ログ中に登場しない人は、ずっとチャットルームにいたかもしれないしいないかもしれない。
ずっとチャットルームにいるなら、その人はリーダーの可能性があるので、ログに登場しない人は全員リーダーの可能性がある。

あとは各人ログ中初回のメッセージを見ることで、開始時にチャットルームにいたかいないか判断できる。
以後、ログを最初から再度以下のようにたどることで各人がリーダーかどうか判定できる。
最初全員がリーダーの可能性があると考えて、可能性がなくなった人を外していこう。
まず以下のように考えられる。

• 自分以外の人がいる状態でログイン → 入る前は他の人がいた＝リーダーではない
• 自分以外の人がいる状態でログアウト → 出た後は他の人がいる＝リーダーではない

また、以下の条件も考える。

• 一人だけの時間帯が複数回あり、そのような時間帯だった人が２人以上いる→どちらもリーダーではない

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");
	
}

まとめ

複数回ログをたどるのがコツ。