kmjp's blog

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

Google Code Jam 2021 Round 1A : C. Hacked Exam

いい感じに悩んだ問題。
https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/0000000000754750

問題

N人の生徒がQ問の2択問題に取り組んだ。
各人の解答と、正解数が与えられる。

この情報をもとにこのQ問に取り組む時、正解数の期待値の最大値とその回答例を答えよ。

解法

N=1,2のケースを見たのち、N=3に進もう。

  • N=1の場合
    • その1人が過半数正答しているならマネして、そうでないなら反対を答えよう。
  • N=2の場合
    • 2人の解答が不一致の問題は、正答数が多い方をマネしよう。
    • 2人の解答が一致の場所は、正解数の情報から計算して2人とも何問正解したか計算できる。過半数正答しているならマネして、そうでないなら反対を答えよう。
  • N=3の場合
    • 3名をA,B,Cと名付け、Q問を以下の4通りに分類する。
      • A,B,Cの解答が一致
      • A,Bの解答が一致、Cだけ異なる
      • A,Cの解答が一致、Bだけ異なる
      • B,Cの解答が一致、Aだけ異なる
    • ここまでの考察を踏まえると、戦略としては各分類において、多数派を真似するか反対を取るかの2択を考えることができる。そこで2^4通り総当たりしてしまおう。
    • 4つの分類において、各分類で多数派が何問正答しているか総当たりし、2^4通りの戦略における期待値を求めよう。期待値が最大となる戦略にそって回答する。
    • 期待値は有理数で答える点に注意。Qが120もあるので分子分母が2^64を超え64bit整数に収まらない可能性がある。
int N,Q;
string A[3];
int S[3];

__int128 C_[125][125];
__int128 comb(int P_,int Q_) {
	if(P_<0 || P_>120 || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}


ostream& operator<<(ostream& os, __int128 v) {
	if(v==0) {
		return (os<<'0');
	}
	if(v<0) {
		os<<'-';
		v=-v;
	}
	
	string T;
	while(v) {
		T+=(char)('0'+(v%10));
		v/=10;
	}
	reverse(ALL(T));
	return (os<<T);
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i]>>S[i];
	}
	
	string T;
	__int128 X=1,Y=1;
	
	if(N==1) {
		T=A[0];
		X=S[0];
		if(S[0]*2<Q) {
			X=Q-S[0];
			FORR(c,T) {
				if(c=='F') c='T';
				else c='F';
			}
		}
	}
	else if(N==2) {
		if(S[0]>S[1]) {
			T=A[0];
		}
		else {
			T=A[1];
		}
		int same=0;
		
		FOR(i,Q) if(A[0][i]==A[1][i]) same++;
		int dif=Q-same;
		int sameac=(S[0]+S[1]-dif)/2;
		X=(max(S[0],S[1])-sameac);
		if(sameac*2<same) {
			sameac=same-sameac;
			FOR(i,Q) if(A[0][i]==A[1][i]) {
				if(T[i]=='F') T[i]='T';
				else T[i]='F';
			}
		}
		
		Y=1;
		X+=sameac;
	}
	else {
		int AB=0,AC=0,BC=0,ABC=0;
		FOR(i,Q) {
			if(A[0][i]==A[1][i]&&A[0][i]==A[2][i]) ABC++;
			else if(A[0][i]==A[1][i]) AB++;
			else if(A[0][i]==A[2][i]) AC++;
			else BC++;
		}
		__int128 pat[16]={};
		int w,x,y,z;
		Y=0;
		for(x=0;x<=AB;x++) for(y=0;y<=AC;y++) for(z=0;z<=BC;z++) {
			int AA=x+y+(BC-z);
			int BB=x+(AC-y)+z;
			int CC=(AB-x)+y+z;
			int w=S[0]-AA;
			if(S[1]-BB!=w) continue;
			if(S[2]-CC!=w) continue;
			if(w<0||w>ABC) continue;
			__int128 p=comb(ABC,w)*comb(AB,x)*comb(AC,y)*comb(BC,z);
			Y+=p;
			int mask;
			FOR(mask,16) {
				int sc=0;
				sc+=(mask&1)?(ABC-w):w;
				sc+=(mask&2)?(AB-x):x;
				sc+=(mask&4)?(AC-y):y;
				sc+=(mask&8)?(BC-z):z;
				pat[mask]+=sc*p;
			}
		}
		int ma=max_element(pat,pat+16)-pat;
		X=pat[ma];
		FOR(i,Q) {
			if(A[0][i]==A[1][i]&&A[0][i]==A[2][i]) {
				if(ma&1) T+=(char)('T'+'F'-A[0][i]);
				else T+=A[0][i];
			}
			else if(A[0][i]==A[1][i]) {
				if(ma&2) T+=A[2][i];
				else T+=A[0][i];
			}
			else if(A[0][i]==A[2][i]) {
				if(ma&4) T+=A[1][i];
				else T+=A[0][i];
			}
			else {
				if(ma&8) T+=A[0][i];
				else T+=A[1][i];
			}
		}
		
	}
	
	__int128 G=__gcd(X,Y);
	X/=G;
	Y/=G;
	cout<<"Case #"<<_loop<<": "<<T<<" "<<X<<"/"<<Y<<endl;
}

void init() {
	int i,j;
	FOR(i,121) C_[i][0]=C_[i][i]=1;
	for(i=1;i<121;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
}

まとめ

自分はいったんSmallまでSubmitして、その後Largeに取り組んだのだけど、一気にN=3までやる人とどっちが多いんだろうな。
Large周りのルール、昔の方が好みだったな。
あと__int128の文字列化、今まで持ってないので今更作った。Pythonで解いてもよかったけどN=2までC++でやってしまったので…。