VK Cup 2015 Round 1 : D. Social Network

これは自力で解けた。Eで大損だな…。
http://codeforces.com/contest/529/problem/D

問題

SNS上でN個のログと、パラメータM,Tがある。
各ログは、時刻S[i]からなり、ある人がS[i]～(S[i]+T-1)の時間の間オンラインだったことを示す。
(同一時間に１人が２つ以上のログに登場しても良い。)
ただし、誰がログインしていたかはわからない。

ここで、このSNSはこの日以下の状態であったことがわかっている。

• SNSにM人を超えて同時ログインしていた時間帯は全くない。
• SNSにM人ちょうど同時ログインしていた瞬間がある。

上記条件を満たすログとユーザーIDの対応のうち、総ユーザー数が最大となるものを求めよ。

解法

ログの時間の古い順からIDを割り当てる。
その際、dequeを用いて(ログイン中のID,退席時刻)の対を管理する。

• まず時刻S[i]を処理する前に、退席時刻がS[i]未満のログインIDをdequeの戦闘から抜く。
• 時刻S[i]にログイン中の人がM人未満の場合：
  • 新規IDを割り当て、退席時刻をS[i]+T-1としてdequeの末尾に追加。
• 時刻S[i]にログイン中の人がM人の場合：
  • これ以上新規IDの人がログインできないので、dequeの末尾の人の退席時刻をS[i]+T-1に更新する。

途中同時ログインID数がMに到達しない場合、解無し。
そうでない場合、割り当てたIDを出力する。

int N,M,T;
int V[30000],R[30000];
int ma,mau,num;
deque<pair<int,int> > Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d %d %d",&N,&M,&T);
	
	FOR(i,N) {
		scanf("%d:%d:%d",&x,&y,&r);
		V[i]=x*3600+y*60+r;
	}
	x=0;
	for(i=0;i<=86400;i++) {
		while(Q.size() && Q.front().first==i) Q.pop_front();
		
		while(x<N && V[x]==i) {
			if(Q.size()==M) {
				R[x]=Q.back().second;
				Q.pop_back();
			}
			else {
				R[x]=++mau;
			}
			Q.push_back(make_pair(i+T,R[x]));
			x++;
		}
		ma=max(ma,(int)Q.size());
	}
	if(ma<M) {
		cout<<"No solution"<<endl;
	}
	else {
		cout<<mau<<endl;
		FOR(i,N) cout<<R[i]<<endl;
	}
}

まとめ

本番ちゃんと見ればよかったなぁ。