TopCoderOpen 2021 Round3 : Medium TellBagsApart

怖かったけど通ってよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=16912&rd=18749

問題

2つの袋がある。
片方は白黒の石が4個ずつ、片方は20個ずつ入っているが、どっちの袋が4個ずつ入っているのかは不明である。

ここで以下を2500回行う。

• 袋を片方選ぶ。この選び方は任意なので、両袋を選ぶ頻度は大きく偏ることがある。
• 選んだ袋から2つ石を選ぶ。この石の選び方はランダムである。

選んだ袋と、1個目の石の色と2個目の石の色で、作業の結果は8通りに分類できる。
そこで、2500回行った際8通りがそれぞれ何回発生したかという情報が与えられる。
どちらの袋が白黒4個ずつの石が入っている方か当てよ。

解法

頻度が少ない方は誤差が怖いので、まず袋単位で試行回数を見て、多い方(合計が1250回以上の方)をチェックしよう。
4個ずつ入っている袋は、同色の石を2個選ぶ確率は3/7であり、20個ずつ入っている袋では19/39である。
そこで、同色の石を2個選んだ割合が3/7と19/39のどちらに近いかで判断しよう。

上位陣ではlogを取ったうえで近さを比べているようだが、幸いlogを取らなくても通る。

ll P[2][2];
double Q[2][2];


class TellBagsApart {
	public:
	string whichBagIsSmaller(vector <int> records) {
		int x[2]={4,20};
		int i;
		FOR(i,2) {
			P[i][0]=x[i]*(x[i]-1);
			P[i][1]=x[i]*x[i];
			Q[i][0]=2*P[i][0]*1.0/(P[i][0]+P[i][0]+P[i][1]+P[i][1]);
			Q[i][1]=2*P[i][1]*1.0/(P[i][0]+P[i][0]+P[i][1]+P[i][1]);
		}
		
		string R;
		FOR(i,records.size()/8) {
			int A[2][2]={
				{records[i*8]+records[i*8+3],records[i*8+1]+records[i*8+2]},
				{records[i*8+4]+records[i*8+7],records[i*8+5]+records[i*8+6]},
			};
			int tar=A[0][0]+A[0][1]<A[1][0]+A[1][1];
			
			double same=1.0*A[tar][0]/(A[tar][0]+A[tar][1]);
			if(abs(Q[0][0]-same)>abs(Q[1][0]-same)) tar^=1;
			R+='1'+tar;
		}
		
		
		return R;
		
	}
}

まとめ

logで補正するのは思い浮かばなかった。危なかったな…。