結果

問題 No.66 輝け☆全国たこやき杯
ユーザー srup٩(๑`н´๑)۶srup٩(๑`н´๑)۶
提出日時 2016-09-23 20:07:59
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 105 ms / 5,000 ms
コード長 1,126 bytes
コンパイル時間 710 ms
コンパイル使用メモリ 59,204 KB
実行使用メモリ 14,204 KB
最終ジャッジ日時 2023-08-11 06:09:07
合計ジャッジ時間 1,554 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,384 KB
testcase_04 AC 2 ms
4,384 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 4 ms
4,628 KB
testcase_07 AC 9 ms
7,364 KB
testcase_08 AC 29 ms
9,780 KB
testcase_09 AC 105 ms
14,204 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <cmath>
typedef long long ll;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

//dp[i][j] := i回回目の試合にj番目のひとが勝つ確率

double dp[12][1200];
int m;
double s[1200];
//memo[i][j] := iとjが戦い、i番目の人が勝つ確率
double memo[1200][1200];
int main(void){
	cin >> m;
	rep(i, pow(2, m)) cin >> s[i];
	rep(i, pow(2, m))rep(j, pow(2, m)){
		memo[i][j] = pow(s[i], 2.0) / (pow(s[i], 2.0) + pow(s[j], 2.0));
	}

	//確率dp　(可能性のある対戦相手を探すのが難しい)
	rep(i, 12)rep(j, 1200) dp[i][j] = 0.0;
	rep(i, 1200)dp[0][i] = 1.0;

	int mask = 0xFFFFFF;
	for (int i = 0; i < m; ++i){//何試合目
		mask -= 1 << i;
		for (int x = 0; x < (1 << m); ++x){//戦う人の番号(勝率を求める側)
			for (int y = 0; y < (1 << m); ++y){//i試合目に戦う可能性のある相手を探す
				if(x == y)continue;
				if(((x ^ y) & (1 << i)) != 0 && (x & mask) == (y & mask)){//ここが難しい
					dp[i + 1][x] += dp[i][x] * dp[i][y] * memo[x][y];
				}
			}
		}
	}
	printf("%.9f\n", dp[m][0]);
	return 0;
}
0