Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-17SRM537 Div1

SRM537 Div1 275 KingXNewCurrency

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

Problem Statement

コーディングフェーズ

よく分からんがmax(A, B)までの数iを候補として、適当にlcm(X, i)までの数で問題ないかチェックすればいいだろう

というのが正しそうかどうかを検討するのに20分くらい要した


後で

そもそもAとBをXとiで表せなければダメだし、逆にそれができれば他の数も全部表せるので、そのチェックだけで良かった

相変わらず不要な検討ばかりして時間がもったいない。。。


ソースコード

提出した版

ll gcd(ll a, ll b) {
	while(b) {
		a=a%b;
		swap(a, b);
	}
	return a;
}

ll lcm(ll a, ll b) {
	return a/gcd(a,b)*b;
}

class KingXNewCurrency {
public:
	int howMany(int A, int B, int X) {
		int res;
		
		if(A>B) swap(A, B);
		int g=gcd(A, B);
		if(g%X==0) return -1;

		res=0;
		for(int i=1; i<=B ;i++) {
			int g2=gcd(X, i);
			if(g%g2!=0) continue;
			int l2=lcm(X, i);
			int can[40010];
			memset(can, 0, sizeof(can));
			for(int j=0; X*j<=l2; j++) {
				for(int k=0; X*j+i*k<=l2; k++) {
					can[X*j+i*k]=1;
				}
			}
			bool ok=true;
			for(int j=0; A*j<=l2; j++) {
				for(int k=0; A*j+B*k<=l2; k++) {
					if(!can[A*j+B*k]) {
						ok=false;
						break;
					}
				}
				if(!ok) break;
			}
			if(ok) res++;
		}

		return res;
	}
};

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