結果

問題 No.162 8020運動
コンテスト
ユーザー ゴリポン先生
提出日時 2025-12-12 15:08:51
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,284 ms / 5,000 ms
コード長 1,468 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 6,233 ms
コンパイル使用メモリ 212,828 KB
実行使用メモリ 156,604 KB
最終ジャッジ日時 2025-12-12 15:09:37
合計ジャッジ時間 40,431 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

module main;
// https://tottoripaper.hatenablog.jp/entry/2015/03/28/182049 より
// 動的計画法
import std;
import core.bitop;

alias T = Tuple!(int, double);
double[] P;	// 虫歯に「なる」確率
T[][] ns;
double[][] dp;

double probability(int prev, int next)
{
	double res = 1.0;
	foreach (i; 0 .. 14) {
		if (!((prev >> i) & 1)) continue;

		double p;
		if (i == 0) {
			p = P[(prev >> 1) & 1];
		} else if (i == 13) {
			p = P[(prev >> 12) & 1];
		} else {
			p = P[((prev >> (i - 1)) & 1) + ((prev >> (i + 1)) & 1)];
		}
		res *= (next >> i) & 1 ? 1.0 - p : p;
	}

	return res;
}
// 多次元配列をある値で埋める
void fill(A, T)(ref A a, T value) if (isArray!A)
{
	alias E = ElementType!A;
	static if (isArray!E) {
		foreach (ref e; a)
			fill(e, value);
	} else {
		a[] = value;
	}
}

void main()
{
	// 入力
	int N = readln.chomp.to!int;
	P = readln.split.to!(double[]);
	P[] /= 100;
	// 答えの計算
	N = 80 - N;
	ns = new T[][](1 << 14);
	dp = uninitializedArray!(double[][])(21, 1 << 14);

	foreach (i; 0 .. 1 << 14) {
		foreach (j; 0 .. 1 << 14) {
			if ((i & j) != j) continue;
			ns[i] ~= T(j, probability(i, j));
		}
	}

	fill(dp, 0.0);
	dp[0][(1 << 14) - 1] = 1.0;
	foreach (i; 0 .. N) {
		foreach (j; 0 .. 1 << 14) {
			foreach (t; ns[j]) {
				dp[i + 1][t[0]] += dp[i][j] * t[1];
			}
		}
	}

	double res = 0.0;
	foreach (i; 0 .. 1 << 14) {
		res += dp[N][i] * popcnt(i);
	}
	// 答えの出力
	writefln("%.12f", res * 2);
}
0