せっかく正答者少ない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フェーズが面倒で面白くない…。