kmjp's blog

競技プログラミング参加記です

Codeforces #390 Div2 C. Vladik and chat

せっかく正答者少ないEを解いたのに、A,C落として順位が低下。
http://codeforces.com/contest/754/problem/C

問題

チャットの参加者一覧と一連のメッセージが与えられる。
一部のメッセージは発言者が不明である。

発言には以下のルールがあるとする。条件を満たす発言者を求めよ。

  • 同じ人は2回続けて発言しない
  • 発言中に自身の名前を含まない

解法

DPで各メッセージに対し、各参加者が最終発言者となるかどうかを更新していけばよい。
DPの過程では直前どの状態から遷移してきたか覚えておき、最後復元する。

int T,N,M;
string UN[1010];
string Msg[1010];
int who[1010];
bitset<128> mask[1010];
int dp[101][110];

vector<string> split(string s) {
	vector<string> R;
	R.push_back("");
	FORR(c,s) {
		if(c=='.' || c==',' || c=='!' || c=='?' || c==' '|| c==':') {
			if(R.back()!="") R.push_back("");
		}
		else {
			R.back() += c;
		}
	}
	return R;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>UN[i];
		cin>>M;
		getline(cin,Msg[0]);
		FOR(i,M) {
			getline(cin,Msg[i]);
			vector<string> S = split(Msg[i]);
			
			if(Msg[i][0]=='?') {
				FOR(j,N) mask[i][j]=1;
			}
			else {
				FOR(j,N) mask[i][j]=0;
				FOR(j,N) if(S[0]==UN[j]) mask[i][j]=1;
				S[0]+='+';
			}
			
			FORR(r,S) FOR(j,N) if(r==UN[j]) mask[i][j]=0;
		}
		MINUS(dp);
		FOR(i,N) dp[0][i]=0;
		FOR(i,M) {
			FOR(j,N) if(mask[i][j]) {
				FOR(x,N) if(dp[i][x]>=0 && (i==0 || x!=j)) dp[i+1][j]=x;
			}
		}
		FOR(i,N) if(dp[M][i]>=0) {
			int cur=i;
			for(j=M-1;j>=0;j--) {
				who[j]=cur;
				cur=dp[j+1][cur];
			}
			FOR(j,M) {
				if(Msg[j][0]=='?') {
					cout<<UN[who[j]]<<Msg[j].substr(1)<<endl;
				}
				else {
					cout<<Msg[j]<<endl;
				}
			}
			break;
		}
		if(i==N) cout<<"Impossible"<<endl;
		
	}
}

まとめ

入力Parseフェーズが面倒で面白くない…。