Codeforces #460 Div2 F. A Game With Numbers

思いついたのが遅くて時間内に実装間に合わず。
http://codeforces.com/contest/919/problem/F

問題

2人が8枚ずつカードを持っている。
各カードは0～4のいずれかの整数が書かれている。
自身が所有するカードをすべて0にしたら勝ちである。

両者は後退のターン制で自身のカードの数値を変えられる。
両者のカードから、0でないものを1枚ずつ選ぶ。
すると自身のカードの数値に相手の数値が加算され、mod 5がとられる。

両者のカードの初期状態と、先手が示されたとき、互いに最適手を取った場合勝者がどちらか、もしくは引き分けがありうるか答えよ。

解法

引き分けの条件が面倒。
引き分けは、下手に手を出すと負けになるので、互いに負けない手を取ろうとすると両者ループになって生じる。
普通にメモ化再帰すると、このループが処理できず失敗する。

よって、トポロジカルソートの要領で、勝ち負けが確定した状態から巻き戻していこう。

• 「先手負け確定」の状態がある場合、その直前としてあり得る状態は「先手勝ち確定」である。
• 遷移先がすべて「先手勝ち確定」の場合、その直前としてあり得る状態は「先手負け確定」である。

いずれの状態にも到達できない状態は、引き分けとみなせる。

int T;
map<vector<int>,int> MP;
vector<vector<int>> C;
vector<int> pre[2020][2020];
int ret[2020][2020];
int lef[2020][2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	vector<int> V(5),W(5);
	
	
	int cnt=0;
	FOR(V[0],9) FOR(V[1],9) FOR(V[2],9) FOR(V[3],9) FOR(V[4],9) {
		if(V[0]+V[1]+V[2]+V[3]+V[4]==8) {
			MP[V]=cnt++;
			C.push_back(V);
		}
	}
	FOR(x,cnt) FOR(y,cnt) {
		V=C[x];
		W=C[y];
		for(i=1;i<=4;i++) if(V[i]) {
			V[i]--;
			for(j=1;j<=4;j++) if(W[j]) {
				V[(i+j)%5]++;
				pre[y][MP[V]].push_back(x);
				lef[x][y]++;
				V[(i+j)%5]--;
			}
			V[i]++;
		}
	}
	MINUS(ret);
	
	queue<int> Q;
	FOR(x,cnt-1) {
		ret[x][cnt-1]=0;
		Q.push(x*10000+cnt-1);
	}
	
	while(Q.size()) {
		x=Q.front()/10000;
		y=Q.front()%10000;
		Q.pop();
		
		if(ret[x][y]==1) {
			FORR(e,pre[x][y]) if(ret[e][x]==-1) {
				if(--lef[e][x]==0) {
					ret[e][x]=0;
					Q.push(e*10000+x);
				}
			}
		}
		else {
			FORR(e,pre[x][y]) if(ret[e][x]==-1) {
				ret[e][x]=1;
				Q.push(e*10000+x);
			}
		}
	}
	
	scanf("%d",&T);
	while(T--) {
		int first;
		
		int A[8],B[8];
		int AV=0,BV=0;
		scanf("%d",&first);
		scanf("%d%d%d%d%d%d%d%d",&A[0],&A[1],&A[2],&A[3],&A[4],&A[5],&A[6],&A[7]);
		scanf("%d%d%d%d%d%d%d%d",&B[0],&B[1],&B[2],&B[3],&B[4],&B[5],&B[6],&B[7]);
		V.resize(0);
		W.resize(0);
		V.resize(5);
		W.resize(5);
		FOR(i,8) V[A[i]]++, W[B[i]]++;
		if(first==0) {
			x=ret[MP[V]][MP[W]];
			if(x==1) _P("Alice\n");
			else if(x==0) _P("Bob\n");
			else _P("Deal\n");
		}
		else {
			x=ret[MP[W]][MP[V]];
			if(x==1) _P("Bob\n");
			else if(x==0) _P("Alice\n");
			else _P("Deal\n");
		}
	}
	
}

まとめ

せっかくEまで順調だったのにな。