結果

問題 No.309 シャイな人たち (1)
ユーザー te-sh
提出日時 2017-07-03 13:55:23
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,321 ms / 4,000 ms
コード長 2,989 bytes
コンパイル時間 2,645 ms
コンパイル使用メモリ 165,344 KB
実行使用メモリ 22,848 KB
最終ジャッジ日時 2024-06-12 20:40:27
合計ジャッジ時間 19,717 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.algorithm, std.conv, std.range, std.stdio, std.string;
// allowable-error: 10 ** -8
void main()
{
auto rd = readln.split.to!(size_t[]), r = rd[0], c = rd[1];
readln;
auto p = r.iota.map!(_ => readln.split.to!(real[]).map!"a / 100".array).array;
readln;
auto s = r.iota.map!(_ => readln.split.to!(int[])).array;
auto cb = (1 << c), cb2 = (1 << (c * 2));
auto pb = new real[][](r, cb);
foreach (i; 0..r)
foreach (j; 0..cb) {
pb[i][j] = 1;
foreach (k; 0..c)
pb[i][j] *= j.bitTest(k) ? 1 - p[i][k] : p[i][k];
}
auto unma = new int[][](r, cb);
foreach (i; 0..r)
foreach (j; 0..cb)
foreach (k; 0..c)
if (j.bitTest(k)) unma[i][j] |= (3 << (k * 2));
auto pt2hu = new int[](cb2);
foreach (i; 0..cb2) pt2hu[i] = calcHu(c, i);
auto dp = new real[][](r, cb);
foreach (i; 0..r) dp[i][] = 0;
foreach (i; 0..cb) {
auto pt = calcPt(c, s[0], 0);
auto hu = pt2hu[pt | unma[0][i]];
dp[0][hu] += pb[0][i];
}
foreach (i; 1..r)
foreach (j; 0..cb) {
auto pt = calcPt(c, s[i], j);
foreach (k; 0..cb) {
auto hu = pt2hu[pt | unma[i][k]];
dp[i][hu] += pb[i][k] * dp[i-1][j];
}
}
auto ans = real(0);
foreach (i; 0..r)
foreach (j; 1..cb)
ans += dp[i][j] * j.popcnt;
writefln("%.9f", ans);
}
auto calcP(size_t c, real[] p, int bkn)
{
auto r = real(0);
foreach (i; 0..c)
r *= bkn.bitTest(i) ? p[i] : 1 - p[i];
return r;
}
auto calcPt(size_t c, int[] s, int bhu)
{
auto pt = 0;
foreach (i; 0..c) {
auto pti = (s[i] - bhu.bitTest(i)).clamp(0, 3);
pt |= (pti << (i * 2));
}
return pt;
}
auto calcHu(size_t c, int bpt)
{
auto pt = new int[](c);
foreach (i; 0..c) pt[i] = ((bpt >> (i * 2)) & 3);
auto op = new bool[](c);
ptrdiff_t findPt0(int[] pt)
{
foreach (i; 0..c)
if (pt[i] <= 0 && !op[i]) return i;
return -1;
}
auto toHu(int[] pt)
{
auto hu = 0;
foreach (i; 0..c)
if (pt[i] <= 0) hu = hu.bitSet(i);
return hu;
}
for (;;) {
auto i = findPt0(pt);
if (i < 0) return toHu(pt);
if (i > 0) --pt[i-1];
if (i < c-1) --pt[i+1];
op[i] = true;
}
}
pragma(inline) {
pure bool bitTest(T)(T n, size_t i) { return (n & (T(1) << i)) != 0; }
pure T bitSet(T)(T n, size_t i) { return n | (T(1) << i); }
pure T bitReset(T)(T n, size_t i) { return n & ~(T(1) << i); }
pure T bitComp(T)(T n, size_t i) { return n ^ (T(1) << i); }
pure T bitSet(T)(T n, size_t s, size_t e) { return n | ((T(1) << e) - 1) & ~((T(1) << s) - 1); }
pure T bitReset(T)(T n, size_t s, size_t e) { return n & (~((T(1) << e) - 1) | ((T(1) << s) - 1)); }
pure T bitComp(T)(T n, size_t s, size_t e) { return n ^ ((T(1) << e) - 1) & ~((T(1) << s) - 1); }
import core.bitop;
pure int bsf(T)(T n) { return core.bitop.bsf(ulong(n)); }
pure int bsr(T)(T n) { return core.bitop.bsr(ulong(n)); }
pure int popcnt(T)(T n) { return core.bitop.popcnt(ulong(n)); }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0