kmjp's blog

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

AtCoder ARC #132 : F - Takahashi The Strongest

本番何とか解けてよかった。
https://atcoder.jp/contests/arc132/tasks/arc132_f

問題

3人でK回のじゃんけんを行う。
1人目と2人目について、K回で出す手のパターンがそれぞれN通り・M通り与えられる。
3人目の手の出し方(3^K)通りそれぞれについて、K回中1回でも3人目だけが勝つことがあるのは、1人目・2人目のパターンの組み合わせN*M通りのうち何通りか求めよ。

解法

3人目が単独勝利するには、1人目と2人目が同じ手を出し、かつ3人目がそれに勝つ手を出さなければならない。
そこで、まず高速ゼータ変換の要領で次を求めよう。

まずある手の出し方maskを以下のように定義する。
mask := 4^K通りの値を取る。それぞれ、(グー・チョキ・パー・不定)とする。
A(mask) := N通り中、1人目がmaskに相当するパターンを出せる組み合わせの数
B(mask) := M通り中、2人目がmaskに相当するパターンを出せる組み合わせの数
とする。これは高速ゼータ変換の変形で求めることができる。

そうすると、
F(mask) := NM通り中、1・2年目がmaskに相当するパターンを出せる組み合わせの数
として
F(mask) = A(mask)*B(mask)
で求めることができる。

次に、以下を考える。
mask' := 4^K通りの値を取る。それぞれ、3人目の出し方として、(チョキだと勝てない・パーなら勝てない・グーなら勝てない・絶対勝てない(1人目と2人目の手が不一致))とする。
G(mask') := NM通り中、3人目がmask'に相当するパターンで1勝もできない組み合わせ数
とするとG(mask')はF(mask)を高速メビウス変換の変形ですることで求めることができる。

あとは3人目の手の出し方mask'に対しNM-G(mask')を答えればよい。

int K,N,M;
int A[1<<24];
int B[1<<24];
ll C[1<<24];
int p3[13];

int decode(string S) {
	int mask=0;
	FORR(c,S) {
		mask*=4;
		if(c=='P') mask+=2;
		if(c=='S') mask++;
	}
	return mask;
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p3[0]=1;
	FOR(i,12) p3[i+1]=p3[i]*3;
	
	
	cin>>K>>N>>M;
	FOR(i,N) {
		cin>>s;
		A[decode(s)]=1;
	}
	FOR(i,M) {
		cin>>s;
		B[decode(s)]=1;
	}
	
	int mask;
	FOR(i,K) {
		int cur=1<<(2*i);
		FOR(mask,1<<(2*K)) if((mask>>(2*i))%4==3) {
			A[mask]+=A[mask-(cur*3)];
			A[mask]+=A[mask-(cur*2)];
			A[mask]+=A[mask-(cur*1)];
			B[mask]+=B[mask-(cur*3)];
			B[mask]+=B[mask-(cur*2)];
			B[mask]+=B[mask-(cur*1)];
		}
	}
	FOR(mask,1<<(2*K)) C[mask]=1LL*A[mask]*B[mask];
	FOR(i,K) {
		int cur=1<<(2*i);
		FOR(mask,1<<(2*K)) if((mask>>(2*i))%4==3) {
			C[mask-(cur*3)]-=C[mask];
			C[mask-(cur*2)]-=C[mask];
			C[mask-(cur*1)]-=C[mask];
		}
	}

	FOR(mask,p3[K]) {
		int nm=0;
		FOR(i,K) {
			nm |= (mask/p3[i])%3*(1<<(2*i));
		}
		cout<<1LL*N*M-abs(C[nm])<<endl;
	}
	
}

まとめ

本番、高速ゼータ/メビウス変換の変形で解けそうというのはすぐ思いついたけど、バグを仕込んでしまい解決に手間取った。
まぁそれでもパフォーマンス3200で変わらないんだけど。どうせ時間内にEは解けてないし。