ECR扱うの久しぶり。
http://codeforces.com/contest/803/problem/E
問題
2人でポーカーを行う。
1回プレイを行うと、勝者は敗者から1ポイントを奪う。
ポイントがK差がついた時点で終了する。
2人のプレイの勝敗履歴が残っているが、一部欠けている。
条件を満たすように、最後のプレイでちょうどK差がつくような履歴が存在するか。
するなら一例を構成せよ。
解法
O(NK)解法で間に合うので、勝・負・引き分けを欠けた部分に当てはめながらDPして戻すだけ。
int N,K; string S; char from[1010][2020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K>>S; from[0][1010]='+'; FOR(i,N) { FOR(j,2020) if(from[i][j]!=0) { if(S[i]=='?'||S[i]=='W') { if(i==N-1 && j+1<=1010+K) from[i+1][j+1]='W'; if(j+1<1010+K) from[i+1][j+1]='W'; } if(S[i]=='?'||S[i]=='D') { from[i+1][j]='D'; } if(S[i]=='?'||S[i]=='L') { if(i==N-1 && j-1>=1010-K) from[i+1][j-1]='L'; if(j-1>1010-K) from[i+1][j-1]='L'; } } } string S; int cur=-1; if(from[N][1010+K]) cur=1010+K; else if(from[N][1010-K]) cur=1010-K; if(cur==-1) { S="NO"; } else { for(i=N;i>0;i--) { S+=from[i][cur]; if(from[i][cur]=='W') cur--; else if(from[i][cur]=='L') cur++; } reverse(ALL(S)); } cout<<S<<endl; }
まとめ
なんでこれこんな正答者少ないんだろう。