kmjp's blog

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

yukicoder : No.936 Are

時間通り参加していないのだけど、この回なんかあったの?
https://yukicoder.me/problems/no/936

問題

2人で以下のゲームを行う。
両者両指のうち0~4本のいずれかを立てた状態である。

両者交互に手番が回ってくるので、以下のいずれかの行動を行う。

  • 自身の手のうち1本以上指が立っている手と、相手の手のうち1本以上指が立っている手を選び、相手の手の立てる指数を自身の立てた指の分加算しmod 5を取る。
  • 自身の両手の指を再配分する。その際mod5を取ってもよい。ただし実質変わらない状態への変化は許可されない。

自身の行動により、相手の両手の立っている指の数が0になると勝ちとなる。

後手は、自身の手番で1手で勝ち確定できるなら、必ずその手を取る。
また、相手の次の手番で負け確定する手は(不可避でない限り)取らない。

先手がKターン以内に勝利する操作の組み合わせは何通りか。

解法

正直動作パターンを全部総当たりするたけ。
相手は「負け確定手しかない場合は、どれかを取る」という動きがあるので見落とさないよう注意。

ll mo=1000000007;
int N,K;
ll from[5][5][5][5];
ll to[5][5][5][5];
int win[5][5][5][5];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,5) FOR(j,5) FOR(x,5) FOR(y,5) if(i+j>0 && x+y>0) {
		if((i+x)%5+y==0) win[i][j][x][y]=1;
		if((i+y)%5+x==0) win[i][j][x][y]=1;
		if((j+x)%5+y==0) win[i][j][x][y]=1;
		if((j+y)%5+x==0) win[i][j][x][y]=1;
	}
	
	
	cin>>N>>K;
	cin>>i>>j>>x>>y;
	
	from[i][j][x][y]=1;
	ll ret=0;
	while(K--) {
		ZERO(to);
		//攻撃
		FOR(i,5) FOR(j,5) FOR(x,5) FOR(y,5) if(from[i][j][x][y]) {
			ll v=from[i][j][x][y];
			if(N==0) {
				if(i&&x) {
					if((i+x)%5+y==0) (ret+=v)%=mo;
					else (to[i][j][(i+x)%5][y]+=v)%=mo;
				}
				if(i&&y) {
					if((i+y)%5+x==0) (ret+=v)%=mo;
					else (to[i][j][x][(i+y)%5]+=v)%=mo;
				}
				if(j&&x) {
					if((j+x)%5+y==0) (ret+=v)%=mo;
					else (to[i][j][(j+x)%5][y]+=v)%=mo;
				}
				if(j&&y) {
					if((j+y)%5+x==0) (ret+=v)%=mo;
					else (to[i][j][x][(j+y)%5]+=v)%=mo;
				}
				int a,b;
				FOR(a,5) FOR(b,5) {
					if(a+b==0) continue;
					if(a+b>i+j) continue;
					if((a+b)%5!=(i+j)%5) continue;
					if(a==i&&b==j) continue;
					if(a==j&&b==i) continue;
					(to[a][b][x][y]+=v)%=mo;
				}
			}
			else {
				//必勝ならそれで終了
				if(win[x][y][i][j]) continue;
				
				int pat=0;
				if(i&&x&&win[(x+i)%5][j][x][y]==0) (to[(i+x)%5][j][x][y]+=v)%=mo, pat++;
				if(i&&y&&win[(y+i)%5][j][x][y]==0) (to[(i+y)%5][j][x][y]+=v)%=mo, pat++;
				if(j&&x&&win[i][(x+j)%5][x][y]==0) (to[i][(j+x)%5][x][y]+=v)%=mo, pat++;
				if(j&&y&&win[i][(y+j)%5][x][y]==0) (to[i][(j+y)%5][x][y]+=v)%=mo, pat++;
				
				int a,b;
				FOR(a,5) FOR(b,5) {
					if(a+b==0) continue;
					if(a+b>x+y) continue;
					if((a+b)%5!=(x+y)%5) continue;
					if(a==x&&b==y) continue;
					if(a==y&&b==x) continue;
					if(win[i][j][a][b]) continue;
					(to[i][j][a][b]+=v)%=mo;
					pat++;
				}
				if(pat==0) {
					//どうやっても負ける
					if(i&&x) (to[(i+x)%5][j][x][y]+=v)%=mo;
					if(i&&y) (to[(i+y)%5][j][x][y]+=v)%=mo;
					if(j&&x) (to[i][(j+x)%5][x][y]+=v)%=mo;
					if(j&&y) (to[i][(j+y)%5][x][y]+=v)%=mo;
					
					int a,b;
					FOR(a,5) FOR(b,5) {
						if(a+b==0) continue;
						if(a+b>x+y) continue;
						if((a+b)%5!=(x+y)%5) continue;
						if(a==x&&b==y) continue;
						if(a==y&&b==x) continue;
						(to[i][j][a][b]+=v)%=mo;
					}
					
				}
			}
		}
		swap(from,to);
		N^=1;
	}
	cout<<ret<<endl;
}

まとめ

ややこしいけど、やることは愚直な問題。