SRM diary(Sigmar)

SRM537 Div1 275 KingXNewCurrency

SRM537, Div1 | 03:57 |

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

SRM537, Div1 | 03:57 |

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;
	}
};