結果

問題 No.309 シャイな人たち (1)
ユーザー te-shte-sh
提出日時 2017-07-03 13:55:23
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 1,715 ms / 4,000 ms
コード長 2,989 bytes
コンパイル時間 2,507 ms
コンパイル使用メモリ 162,860 KB
実行使用メモリ 23,268 KB
最終ジャッジ日時 2023-09-03 14:57:02
合計ジャッジ時間 24,816 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,688 ms
21,772 KB
testcase_01 AC 1,706 ms
21,416 KB
testcase_02 AC 1,705 ms
21,944 KB
testcase_03 AC 1,702 ms
22,300 KB
testcase_04 AC 26 ms
4,380 KB
testcase_05 AC 400 ms
8,640 KB
testcase_06 AC 1,711 ms
21,820 KB
testcase_07 AC 1,699 ms
22,040 KB
testcase_08 AC 1,715 ms
23,268 KB
testcase_09 AC 1,704 ms
21,768 KB
testcase_10 AC 1,693 ms
22,600 KB
testcase_11 AC 1,703 ms
21,712 KB
testcase_12 AC 1,702 ms
22,076 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 405 ms
8,692 KB
権限があれば一括ダウンロードができます

ソースコード

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)); }
}
0