乱択使ってみた
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程度でも十分な確率のようだ。
恐らく、問題の性質から外す確率のオーダーの逆数が大きいことがわかるんだろうが、証明力が足りない…
なんとなく偶然合う確率は低そうではあるけど。
想定解でなくても乱択でもいけることがある、ということがわかった。
それっぽいときは、試行回数を減らして何回か試してみて、確率のオーダーをなんとなく見てみよう