yukicoder : No.2727 Tetrahedron Game

初手を思いつくかどうか…。
https://yukicoder.me/problems/no/2727

問題

3次元座標上で3つの点が与えられる。
N要素の整数列Aと、N文字の文字列Sが与えられる。

iターン目では、S[i]の文字によって先手後手どちらが操作するか決まる。
自分のターンでは、3つの点のうち2つ(重複可)を選び、前者の座標に、後者の座標のA[i]倍を加算する。

最終的に原点とこの3点が成す四面体の体積を考える。

• 非整数なら引き分け
• 整数の場合、101で割った余りがK以上なら先手の勝ち、そうでない場合後手の勝ち

両者最適手を取った場合勝者はどちらか。

解法

正四面体の体積は、3点の座標を並べた3*3の行列式を6で割った余りである。

各自のターンでできるのは、

• 3点から異なる2点を選んだ場合、行列式の値は変わらない
• 3点から1点を2回選んだ場合、行列式の値は(A[i]+1)倍になる

なので、結局行列式を1倍するか(A[i]+1)倍するかの二択である。

ここで現在の体積に対し行列式を状態に、勝者を後退解析で求めよう。
体積の計算で行列式を6で割るため、体積は

• 2で割ったことがあるか
• 3で割ったことがあるか
• (2及び3で最大1回割ったうえで)101で割った余り

の3値の組み合わせで表現するとよい。

int T,N,K;
ll P[3][3];
int dp[10101][102][2][2];
int A[10101];
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(y,3) FOR(x,3) cin>>P[y][x];
		FOR(i,N) cin>>A[i];
		cin>>S;
		
		FOR(i,101) {
			dp[N][i][0][0]=-1;
			dp[N][i][0][1]=-1;
			dp[N][i][1][0]=-1;
			dp[N][i][1][1]=(i>=K);
		}
		for(i=N-1;i>=0;i--) {
			FOR(j,101) FOR(x,2) FOR(y,2) {
				// 1倍
				set<int> R;
				R.insert(dp[i+1][j][x][y]);
				int nj=(A[i]+1);
				int nx=x;
				int ny=y;
				if(nx==0&&nj%2==0) nx=1,nj/=2;
				if(ny==0&&nj%3==0) ny=1,nj/=3;
				nj=nj*j%101;
				R.insert(dp[i+1][nj][nx][ny]);
				
				if(S[i]=='K') {
					if(R.count(1)) dp[i][j][x][y]=1;
					else if(R.count(-1)) dp[i][j][x][y]=-1;
					else dp[i][j][x][y]=0;
				}
				else {
					if(R.count(0)) dp[i][j][x][y]=0;
					else if(R.count(-1)) dp[i][j][x][y]=-1;
					else dp[i][j][x][y]=1;
				}
			}
		}
		ll d=P[0][0]*P[1][1]*P[2][2]+P[0][1]*P[1][2]*P[2][0]+P[0][2]*P[1][0]*P[2][1];
		d-=P[0][0]*P[1][2]*P[2][1]+P[0][1]*P[1][0]*P[2][2]+P[0][2]*P[1][1]*P[2][0];
		d=abs(d);
		x=y=0;
		
		if(d==0) {
			cout<<"D"<<endl;
			continue;
		}
		
		if(d%2==0) d/=2,x=1;
		if(d%3==0) d/=3,y=1;
		d%=101;
		if(dp[0][d][x][y]==1) cout<<"K"<<endl;
		if(dp[0][d][x][y]==0) cout<<"P"<<endl;
		if(dp[0][d][x][y]==-1) cout<<"D"<<endl;
		
		
	}
	
}

まとめ

行列式を使って正四面体の体積を計算できることを忘れていた…。