Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-03-17SRM537 Div1

SRM537 Div1 500 KingXMagicSpells

| 03:57 | SRM537 Div1 500 KingXMagicSpells - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM537 Div1 500 KingXMagicSpells - SRM diary(Sigmar) SRM537 Div1 500 KingXMagicSpells - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

期待値ってことは、また線形性か

XORだとビット毎に変化するので、ビット毎にそのビットが立つ確率を計算して、後で足しあわせればいいだろう

と思ったけど最大10億だったら無理か(←無理でない。30ビットしかない。)


うーん分からん。DPか。

DPも無理ぽい。お手上げ・・・


後で

チャレンジフェーズでようやく30ビットしかないことに気づいた

頭悪すぎる・・


ソースコード

class KingXMagicSpells {
public:
	double expectedNumber(vector <int> ducks, vector <int> s1, vector <int> s2, int K) {
		double res;
		int n=ducks.size();

		vector <vector <double> > p(n, vector <double>(30));
		for(int i=0; i<n; i++) {
			for(int j=0; j<30; j++) {
				if(ducks[i]&(1<<j)) p[i][j]=1;
			}
		}

		for(int i=0; i<K; i++) {
			vector <vector <double> > np(n, vector <double>(30));
			for(int j=0; j<n; j++) {
				for(int k=0; k<30; k++) {
					if(s1[j]&(1<<k)) np[j][k]=(1-p[j][k])/2;
					else np[j][k]=p[j][k]/2;
				}
			}
			for(int j=0; j<n; j++) {
				for(int k=0; k<30; k++) {
					np[s2[j]][k]+=p[j][k]/2;
				}
			}
			p=np;
		}
		
		res=0;
		for(int i=0; i<30; i++) {
			res+=p[0][i]*(1<<i);
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120317