結果

問題 No.309 シャイな人たち (1)
ユーザー cympfhcympfh
提出日時 2015-12-02 17:30:14
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,257 bytes
コンパイル時間 1,483 ms
コンパイル使用メモリ 158,040 KB
実行使用メモリ 4,352 KB
最終ジャッジ日時 2023-10-12 09:01:10
合計ジャッジ時間 2,212 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 2 ms
4,352 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,352 KB
testcase_15 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

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) {
    vvd pt(w, vd(5, 0)); // pt[j][s] = Pr[score(i,j) == s] ただし pt[j][4] = Pr[score>=4]
    
    rep (j, w) {
      pt[j][4 - s[i][j]] = p[i][j]/100.0;
      pt[j][0] = 1.0 - p[i][j]/100.0;
      if (s[i][j] == 4) pt[j][0] = 1.0;
    }

    // 前の行からの伝播
    rep (j, w) {
      vd memo(6, 0);
      rep (k, 5) {
        memo[k+1] += pt[j][k] * Pr[i-1][j];
        memo[k] += pt[j][k] * (1.0 - Pr[i-1][j]);
      }
      rep (k, 5) pt[j][k] = memo[k];
      pt[j][4] += memo[5];
    }

    vector<bool> used(w, false);
    rep (_, w) {
      int idx = -1;
      double mp = -1;
      rep (j, w) {
        if (not used[j] and pt[j][4] > mp) {
          mp = pt[j][4];
          idx = j;
        }
      }
      used[idx] = true;
      if (idx > 0) { // to left
        int j = idx;
        vd memo(6, 0);
        rep (k, 5) {
          memo[k+1] += pt[j-1][k] * mp;
          memo[k] += pt[j-1][k] * (1.0 - mp);
        }
        rep (k, 5) pt[j-1][k] = memo[k];
        pt[j-1][4] += memo[5];
      }
      if (idx < w-1) { // to right
        int j = idx;
        vd memo(6, 0);
        rep (k, 5) {
          memo[k+1] += pt[j+1][k] * mp;
          memo[k] += pt[j+1][k] * (1.0 - mp);
        }
        rep (k, 5) pt[j+1][k] = memo[k];
        pt[j+1][4] += memo[5];
      }
    }

    rep (j, w) Pr[i][j] = pt[j][4];

  }

  //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