結果

問題 No.309 シャイな人たち (1)
コンテスト
ユーザー cympfh
提出日時 2015-12-02 16:30:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,834 bytes
コンパイル時間 1,788 ms
コンパイル使用メモリ 172,552 KB
実行使用メモリ 10,016 KB
最終ジャッジ日時 2024-09-14 07:57:18
合計ジャッジ時間 12,158 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#define rep(i,n) for(int i=0;i<(n);++i)
#define loop for(;;)
#define trace(var) cerr<<">>> "<<#var<<" = "<<var<<endl;
#define all(v) begin(v),end(v)
#define pb push_back
#define inf (1e9)
#define eps (1e-9)
using Integer = long long;
using Real = long double;
const Real PI = acosl(-1);
using P = pair<int, int>;

template<class S, class T> inline
ostream& operator<<(ostream&os, pair<S,T> p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template<class S, class T, class U> inline
ostream& operator<<(ostream&os, tuple<S,T,U> t) {
  return os << '('
    << get<0>(t) << ", "
    << get<1>(t) << ", "
    << get<2>(t) << ')';
}

template<class T> inline
ostream& operator<<(ostream&os, set<T> v) {
  os << "(set";
  for (T item: v) os << ' ' << item;
  os << ")";
  return os;
}

template<class T> inline
ostream& operator<<(ostream&os, vector<T> v) {
  if (v.size() == 0) { return os << "(empty)"; }
  os << v[0];
  for (int i=1, len=v.size(); i<len; ++i) os << ' ' << v[i];
  return os;
}

template<class T> inline
istream& operator>>(istream&is, vector<T>&v) {
  rep (i, v.size()) is >> v[i];
  return is;
}

using vi = vector<int>;
using vvi = vector<vi>;
using vd = vector<double>;
using vvd = vector<vd>;
using vb = vector<bool>;

inline vi bit_pattern(int I, int w) {
  vi r;
  rep (i, w) r.push_back((I & (1 << i)) ? 1 : 0);
  return r;
}

int main() {
  cerr << fixed << setprecision(5);

  int h, w;
  cin >> h >> w;

  vvi p(h+1, vi(w, 0));
  vvi s(h+1, vi(w, 0));
  rep (i, h) rep (j, w) cin >> p[i+1][j];
  rep (i, h) rep (j, w) cin >> s[i+1][j];
  rep (j, w) {
    p[0][j] = 0;
    s[0][j] = 4;
  }

  vvd Pr(h+1, vd(w, 0));

  for (int i = 1; i <= h; ++i) {
    rep (I, (1<<w)) {
      auto raising = bit_pattern(I, w); // 前列
      rep (J, (1<<w)) {
        auto is_known = bit_pattern(J, w);

        // simulate
        vi pt(w, 0);
        rep (j, w) {
          pt[j] = (is_known[j]) ? (4 - s[i][j]) : 0;
          if (raising[j]) pt[j]++;
        }

        stack<int> s;
        rep (j, w) if (pt[j] >= 4) {
          s.push(j-1);
          s.push(j+1);
        }
        while (not s.empty()) {
          int j = s.top(); s.pop();
          if (j < 0 or j>=w) continue;
          pt[j]++;
          if (pt[j] == 4) {
            s.push(j-1);
            s.push(j+1);
          }
        }

        double pr = 1.0; // of I and J
        rep (j, w) {
          pr *=
            (raising[j] ? Pr[i-1][j] : (1.0 - Pr[i-1][j]))
            * (is_known[j] ? p[i][j] : (100-p[i][j])) / 100.0;
        }
        rep (j, w) if (pt[j] >= 4) Pr[i][j] += pr;
      }
    }
  }

  //rep (i, h+1) { rep (j, w) cerr << Pr[i][j] << ' '; cerr << endl; }
    
  double ans = 0.0;
  rep (i, h+1) rep (j, w) ans += Pr[i][j];
  cout << ans << endl;
  return 0;
}
0