乱択使ってみた

SRM 360 DIV1 Easy のこのhttp://community.topcoder.com/stat?c=problem_statement&pm=7875&rd=10772問題で。
想定解ではないらしいが、何回かSystem Testをやっても通る。
コードのメイン部分

#define N 1000000
int t[55][55];
struct SumOfSelectedCells {
	int h, w;
	string hypothesis(vector <string> table) {
		h = table.size(); w = 0;
		{stringstream ss(table[0]);int j=0;int x;while(ss>>x)j++;w=j;}
		bool b = 0;
		if(h > w) b = 1;
		rep(i, h) {
			stringstream ss(table[i]);
			int j = 0;
			int x;
			while(ss>>x) {
				if(b) t[j++][i] = x;
				else t[i][j++] = x;
			}
		}
		if(b) swap(h, w);
		vi v;
		rep(i, h) {
			rep(j, w)cout<<t[i][j]<<" ";cout<<endl;
		}
		rep(i, w) v.pb(i);
		int y = -1;
		rep(ii, N) {
			random_shuffle(all(v));
			int x = 0;
			rep(i, h) x += t[i][v[i]];
			if(y != -1 && x != y) {
				cout <<y<<"," <<x << endl;
				return "INCORRECT";
			}
			y = x;
		}
		return "CORRECT";
	}
};

初めに通した時は念のためN(試行回数)=10^6でやったが、試したらN=100程度でも十分な確率のようだ。
恐らく、問題の性質から外す確率のオーダーの逆数が大きいことがわかるんだろうが、証明力が足りない…
なんとなく偶然合う確率は低そうではあるけど。
想定解でなくても乱択でもいけることがある、ということがわかった。
それっぽいときは、試行回数を減らして何回か試してみて、確率のオーダーをなんとなく見てみよう