kmjp's blog

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

Codeforces ECR #020 : E. Roma and Poker

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;
	
}

まとめ

なんでこれこんな正答者少ないんだろう。