DigitalArts プログラミングコンテスト2012 : C - Chokutter

さて３問目。
http://digitalarts2012.contest.atcoder.jp/tasks/digitalarts_3

最大10万回分のフォロー・アンフォロー・ツイートのログがあるので、各人のタイムラインに現れる発言数を求める問題。
最大ではフォロー数×ツイート程度の計算量があるので、そのままシミュレーションすると最大で5万×5万＝25億程度ループを回すことになるが、実直に処理してもなんとか間に合うらしい。

ただ、これはかなり危ないので、もっと計算量を落とす必要がある。
順にログを解析する場合、行動に応じて以下の手順を組めばよい

• ツイートした場合、その人のツイート数をインクリメントする。
• フォローした場合、フォロー開始時のフォロー相手の発言数を覚えておく。
• アンフォローした場合、その時点のフォロー相手の発言数から開始時の発言数を引いたものを、TL登場数として加算する。

ログを処理し終わったときにフォロー関係が続いている組み合わせは、アンフォロー同様発言数の差をTL登場数として加算する。
この手順だとログ数の計算量で終わる。

int N,M,K;
int T[100001];
int S[100001];
map<pair<int,int>, int> FT;

void solve() {
	int x,y,i,j,c,w,t;
	char st[10];
	
	GET3(&N,&M,&K);
	ZERO(T);
	ZERO(S);
	FT.clear();
	FOR(i,M) {
		GETs(st);
		w=GETi()-1;
		if(st[0]=='t') {
			T[w]++;
		}
		else if(st[0]=='f') {
			t=GETi()-1;
			FT.insert(make_pair(make_pair(w,t),T[t]));
			FT.insert(make_pair(make_pair(t,w),T[w]));
		}
		else {
			t=GETi()-1;
			S[w]+=T[t]-FT[make_pair(w,t)];
			S[t]+=T[w]-FT[make_pair(t,w)];
			FT.erase(make_pair(w,t));
			FT.erase(make_pair(t,w));
		}
	}
	
	map<pair<int,int>, int>::iterator it;
	for(it=FT.begin();it!=FT.end();it++) {
		pair<int,int> p=(*it).first;
		S[p.first] += T[p.second] - (*it).second;
	}
	FOR(i,N) T[i]+=S[i];
	
	sort(T,T+N);
	_P("%d\n",T[(N-1)-(K-1)]);
	return;
}

まとめ

なかなか回答が思いつかなかったけど、解いてみると面白い問題。