いい感じに悩んだ問題。
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整数に収まらない可能性がある。
- 3名をA,B,Cと名付け、Q問を以下の4通りに分類する。
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++でやってしまったので…。