2011-03-19

SRM 500 Div1 250 -> 0(system test failed)

04:09 |

500回記念大会。

まず投票できる分を投票して、投票してない人が何人か数える。
投票してない人の分を投票数が少ない順に埋める。
埋め方が１通りでない場合（最低投票数の人数＜残り票数のとき）は、その人達の確率に「最低投票数の人数＜残り票数」を掛ける
最多票の人たちだけを新たに vulnerable にする
最多票の人数が変わらない時は無限ループになるので 0.0 を返す
最多票が１人のときは決まりなので積み上げてきた確率を返す

500, 1000 問題は開きもせず。

で 0 点なのにレートはなぜか 1294 -> 1304 に微増。Div1 のこったのこった !

反省点

System Test Results を見ると、１個だけ落ちてる。213, {42, 30, 101, 113, 41, 179, 113, 76, 69, 30, 18, 159, 36}
最大 500 票あるのに、「最小票が何票か」を表す int min_vot の初期値が 100 になっていた (!!
100 を 1000 に変えたらローカルで通った。
確か書いたときは決まっている票が最大 50 個だから 100 でいいだろうと思ってしまったのだった。
おしい＆ぬるい。。

あと結果的には問題なかったが、当初プログラムが想定外に無限ループになってログがでかくなっちゃうのでとりあえず 10 回で打ち切るようにしていたコードを消すの忘れて提出していた。
あとデバッグの cout が多いので提出前にコメントアウトすべし。
ほんとは、コードを書いてテストが通らなくて「？？」てなって cout してみる前に方針ミスなどに気がつけるようになりたいんですが。
なんかいろいろもったいなかった。。。。

ソース（追記：要ログイン）

http://www.topcoder.com/stat?c=problem_solution&rm=307554&rd=14429&pm=11342&cr=22919543

追記：上記リンクが要ログインなのでこちらにもソースを貼っておきます。

こちらは最小票カウンタの初期値を 100 から 1000 に変えた版です（ｗ

他の方のソースや解説を見ると、「投票が終わるならば浮動票だけの人が１度でも最多票を獲得することはない」ということに気づくと短いコードになるみたいですね。。

実際書いてて「浮動票onlyの人が最多になるとその時点では確率M/Nだけど、固定票はその時点では確率1なので違っちゃってなんかまずいな」と思っていたのが、浮動票だけの人は結局は選ばれないということで納得です。

class MafiaGame {
	public:
	double probabilityToLose(int N, vector <int> de) {
printf("%s %d\n", __FILE__, __LINE__);
		VI vul(N);
		VI vot(N);
		REP(i, N) vul[i]=1;
		vector<double> pro(N);
		REP(i, N) pro[i] = 1.0;
		int prev_n_vul = -1;
		
		int wdc = 0;
		do
		{
			cout<<"VUL "<<vul<<endl;
			int other = N-de.SZ;
			REP(i, N) vot[i]=0;
			REP(i, de.SZ) if(vul[de[i]]) { vot[de[i]]++; } else { other++; }
			cout<<"VOT "<<vot<<endl;
			cout<<"other "<<other<<endl;
			
			while(other>0)
			{
				cout<<"VO2 "<<vot<<endl;
				int min_vot = 1000;
				int min_cnt = 0;
				REP(i, N) if(vul[i] && vot[i]<min_vot) { min_vot=vot[i]; }
				REP(i, N) if(vul[i] && vot[i]==min_vot) min_cnt++;
				if(min_cnt<=other)
				{
					REP(i, N) if(vul[i] && vot[i]==min_vot) { vot[i]++; other--; }
				}
				else
				{
					// choose other/min_cnt
					double p = (double)other/min_cnt;
					REP(i, N)
					{
						if(other==0) break;
						if(vul[i] && vot[i]==min_vot) { pro[i] *= p; vot[i]++; other--; }
					}
					cout<<"PRO "<<pro<<endl;
				}
			}
			int n_vul = 0;
			int max_vot = 0;
			REP(i, N) if(vul[i] && max_vot < vot[i]) max_vot = vot[i];
			REP(i, N) if(vul[i] && vot[i]==max_vot) n_vul++;
			cout<<"n_vul "<<n_vul<<endl;
			if(n_vul==prev_n_vul) return 0.0;
			prev_n_vul = n_vul;
			REP(i, N) vul[i] = vot[i]==max_vot ? 1 : 0;
			if(n_vul==1) break;
			
			if(wdc++>10) return -1.0;
		}
		while(1);
		
		double ans = 0.0;
		REP(i, N) if(vul[i] && ans<pro[i]) ans = pro[i];
		return ans;
	}

kojingharangの日記

2011-03-19

SRM 500 Div1 250 -> 0(system test failed)