結果

問題 No.66 輝け☆全国たこやき杯
コンテスト
ユーザー masa
提出日時 2015-10-09 17:47:07
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 15 ms / 5,000 ms
コード長 1,097 bytes
コンパイル時間 760 ms
コンパイル使用メモリ 71,768 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-07-20 02:23:36
合計ジャッジ時間 1,352 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>

using namespace std;


int main() {
	int m, n;

	cin >> m;
	n = pow(2, m);

	vector<int> s(n), s2(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		s2[i] = s[i] * s[i];
	}

	// dp[i][j] = i回戦をjが突破する確率
	vector< vector<double> > prob(m + 1, vector<double>(n, 0));
	prob[0] = vector<double>(n, 1);

	vector< vector <double> > win(n, vector<double>(n, 0.0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) {
				continue;
			}

			win[i][j] = (1.0 * s2[i]) / (s2[i] + s2[j]);
		}
	}

	for (int i = 1; i <= m; i++) {
		int n_person = pow(2, i);
		for (int j  = 0; j < n; j += n_person) {

			int y_begin = j + n_person / 2;
			int y_end   = j + n_person - 1;

			for (int x = j; x < y_begin; x++) {
				for (int y = y_begin; y <= y_end; y++) {
					prob[i][x] += win[x][y] * prob[i - 1][x] * prob[i - 1][y];
					prob[i][y] += win[y][x] * prob[i - 1][x] * prob[i - 1][y];
				}
			}
		}
	}

	printf("%.9f\n", prob[m][0]);
	return 0;
}
0