kojingharangの日記

Typical DP contest D サイコロ

01:54 |

• サイコロを N 回振ったとき、出た目の積が D の倍数となる確率を求めよ
• 1≦N≦100, 1≦D≦10^18

• 倍数ということで素因数分解した形で考える
• サイコロの目 1〜6 は全て 2^i * 3^j * 5^k の形で表せる。
• だからなんなのさ

• シャワー浴びてたらひらめく !
• D に 7 以上の素因数があったらサイコロを何回振っても D の倍数にはならない ... ので 0 を印字して終わる
• D = 2^p2 * 3^p3 * 5^p5 と表せたので、なんか途中の状態を 2^? * 3^? * 5^? と表しておくんじゃないか
• dp[2の指数][3の指数][5の指数] = n回目にそういう状態になる確率
• 初期値は dp[0][0][0] = 1. 他の要素は 0
• サイを降るごとに状態全てについて目で場合分けして確率を更新. 3が出たら 2^0 * 3^1 * 5^0 掛けるので [i][j+1][k]のとこを更新　みたいな。
• 最終的に i ≧ p2 && j ≧ p3 && k ≧ p5 の確率を全部たしたものが答え。

• TLE
• コンテスト終了

(あとで)

• DP表の無駄なコピーを消す && dp[i][j][k]==0 ならスキップ
• accepted in practice

double dp[2][210][110][110];

int main() {
	//ios::sync_with_stdio(false);
	ll N, D;
	int tb[]={
		0, 0, 0,
		1, 0, 0,
		0, 1, 0,
		2, 0, 0,
		0, 0, 1,
		1, 1, 0,
	};
	while(cin>>N>>D) {
		int p2=0, p3=0, p5=0;
		while(D%2==0) p2++,D/=2;
		while(D%3==0) p3++,D/=3;
		while(D%5==0) p5++,D/=5;
		if(D>1) {
			cout<<0<<endl;
			continue;
		}
//		cout<<p2<<" "<<p3<<" "<<p5<<endl;
		int men=0;
		REP(m, 2) REP(i, 210) REP(j, 110) REP(k, 110) dp[m][i][j][k]=0;
		dp[men][0][0][0] = 1;
		REP(I, N) {
			REP(i, 210) REP(j, 110) REP(k, 110) {
				if(dp[men][i][j][k]==0.0) continue;
				REP(me, 6) {
					int ni = i+tb[me*3+0];
					int nj = j+tb[me*3+1];
					int nk = k+tb[me*3+2];
					if(ni<210 && nj<110 && nk<110) dp[1-men][ni][nj][nk] += dp[men][i][j][k] / 6.0;
				}
			}
			REP(i, 210) REP(j, 110) REP(k, 110) dp[men][i][j][k]=0;
			men ^= 1;
//			PRINT3(dp, 5, 5, 1);
		}
		double ans = 0;
		REP(i, 210) REP(j, 110) REP(k, 110) if(i>=p2 && j>=p3 && k>=p5) ans += dp[men][i][j][k];
		
		cout<<ans<<endl;
	}
	
	return 0;
}

ツイートする

Typical DP contest C トーナメント

02:19 |

• 2^K 人がトーナメント対戦する。人 i, j が対戦して i が勝つ確率が式で与えられる。各人が優勝する確率を求める。
• 1≦K≦10

• わからないので工夫とかなしで何を計算すべきか考えてみる
• dp[k][i] ... k回戦が終わった段階で人iが勝ち残ってる確率 と置いてみる. (実際は2面だけ用意した
• 各対戦で戦う可能性のある人すべてのパターンで確率を計算してdp[k+1]に足してく
• 決勝は 512x512 →おー間に合うじゃん
• accepted

double f(double EP, double EQ) {
	return 1.0 / (1 + pow(10, (EQ-EP)/400));
}

int main() {
	//ios::sync_with_stdio(false);
	ll K;
	while(cin>>K) {
		VI E(1<<K);
		REP(i, 1<<K) cin>>E[i];
		
		vector<double> p(1<<K, 1), np(1<<K);
		REP(round, K) {
			int size = 1<<round;
			int games = (1<<K)/size/2;
//			cout<<"round: "<<size<<" "<<games<<endl;
			REP(game, games) {
				int asidx = game*size*2;
				int bsidx = game*size*2+size;
				REP(ai, size) {
					REP(bi, size) {
						double pawin = f(E[asidx+ai], E[bsidx+bi]);
						np[asidx+ai] += p[asidx+ai]*p[bsidx+bi]*pawin;
						np[bsidx+bi] += p[asidx+ai]*p[bsidx+bi]*(1-pawin);
					}
				}
			}
//			cout<<"np: "<<np<<endl;
			p = np;
			np = vector<double>(1<<K);
		}
		REP(i, 1<<K) cout<<p[i]<<endl;
	}
	
	return 0;
}

ツイートする