結果

問題 No.66 輝け☆全国たこやき杯
ユーザー data9824data9824
提出日時 2015-06-19 02:46:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 1,026 bytes
コンパイル時間 587 ms
コンパイル使用メモリ 72,380 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-07 03:48:18
合計ジャッジ時間 1,137 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 5 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

int main() {
	int m;
	cin >> m;
	int playerCount = (1 << m);
	vector<double> s(1 + playerCount);
	for (int i = 1; i <= playerCount; ++i) {
		cin >> s[i];
	}
	// [?-th round][?-th player]
	vector<vector<double> > p(1 + m, vector<double>(1 + playerCount));
	fill(p[0].begin(), p[0].end(), 1.0);
	for (int round = 1; round <= m; ++round) {
		for (int k = 1; k <= playerCount; ++k) {
			double sum = 0;
			int game = (k - 1) / (1 << round);
			int previousGame = (k - 1) / (1 << (round - 1));
			for (int m = game * (1 << round) + 1;
				m <= (game + 1) * (1 << round);
				++m) {
				if (m < previousGame * (1 << (round - 1)) + 1
					|| (previousGame + 1) * (1 << (round - 1)) + 1 <= m) {
					double conditional = s[k] * s[k] / (s[k] * s[k] + s[m] * s[m]);
					sum += conditional * p[round - 1][m];
				}
			}
			p[round][k] = p[round - 1][k] * sum;
		}
	}
	cout << fixed << setprecision(12) << p[m][1] << endl;
	return 0;
}
0