結果

問題 No.66 輝け☆全国たこやき杯
コンテスト
ユーザー 古寺いろは
提出日時 2015-04-13 08:23:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 750 bytes
コンパイル時間 1,197 ms
コンパイル使用メモリ 159,608 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 14:12:50
合計ジャッジ時間 1,765 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

int S[1 << 10];

vector<double> dfs(int start, int num){
	vector<double> ret(num);
	if (num == 1){
		ret[0] = 1;
		return ret;
	}
	vector <double> a = dfs(start, num / 2);
	vector <double> b = dfs(start + num / 2, num / 2);
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < b.size(); j++)
		{
			double p = a[i] * b[j];
			int ap = start + i;
			int bp = start + num / 2 + j;
			ret[i] += p * S[ap] * S[ap] / (S[ap] * S[ap] + S[bp] * S[bp]);
			ret[num/2 + j] += p * S[bp] * S[bp] / (S[ap] * S[ap] + S[bp] * S[bp]);
		}
	}
	return ret;
}

int main(){
	int M;
	cin >> M;
	for (int i = 0; i < (1<<M); i++)
	{
		cin >> S[i];
	}
	vector<double> ans = dfs(0, 1 << M);
	printf("%.14f\n", ans[0]);
}
0