Google Code Jam 2021 Qualification Round : E. Cheating Detection

これは他のコンテストでは余り見ないタイプの問題。
https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1155

問題

N(=100)人の生徒がM(=10000)問の問題からなるテストを受ける。
生徒のスキルS[i]と、問題の難易度Q[j]に対し、生徒が問題を正答する確率はsigmod(S[i]-Q[j])で与えられる。

今ここでN人中1人がずるをしている。
ずるをしている生徒は、各問題について1/2の確率でスキルと難易度を問わず正答し、1/2の確率で真っ当にsigmoid関数に則って正答する。

N人の生徒がM問の問題を解いた時の結果が与えられる。
ずるをしている生徒を特定せよ。

解法

まず生徒を問題の正答数順にソートする。
ずるをしている生徒は、近い正答数の生徒に比べスキルが少ないはずである。
よって難しい問題において妙に正答率が周囲より高いことになる。

そこで、問題を正答数順にソートし、問題を難易度順に並べる。
各人易しい1000問と難しい1000問の正答率を求め、周辺との差が大きい人をずるをしていると特定した。

手元でテストケースをランダム生成したところ、98%位はこれでうまくいった。

int P,N;
string S[101];
int O[101];
void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	N=100;
	pair<int,int> A[101];
	pair<int,int> cnt[10101];
	FOR(i,N) {
		cin>>S[i];
		A[i].first=count(ALL(S[i]),'1');
		A[i].second=i;
	}
	FOR(j,10000) {
		cnt[j]={0,j};
		FOR(i,100) if(S[i][j]=='1') cnt[j].first++;
	}
	sort(A,A+N);
	sort(cnt,cnt+10000);
	FOR(i,N) {
		O[i]=A[i].second;
		string U;
		FOR(j,10000) U.push_back(S[i][cnt[j].second]);
		S[i]=U;
	}
	
	x=0;
	int ma=-1,ret=-1;
	int X[N],Y[N];
	FOR(j,N) {
		x=y=0;
		FOR(i,1000) {
			x+=S[O[j]][i]=='1';
			y+=S[O[j]][9999-i]=='0';
		}
		X[j]=x;
		Y[j]=y;
	}
	
	FOR(j,N) {
		int dif=0;
		x=j-1;
		y=j+1;
		if(x<0) x=y+1;
		if(y==N) y=x-1;
		dif=abs(X[j]-X[x])+abs(X[j]-X[y])+abs(Y[j]-Y[x])+abs(Y[j]-Y[y]);
		if(dif>ma) ma=dif, ret=O[j];
		
	}
	
	
	
	_P("Case #%d: %d\n",_loop, ret+1);
	
}

void init() {
	cin>>P;
}

まとめ

本番、P=10ですら通らず頭を抱えていたが、単に改行忘れだった。