結果
問題 | No.309 シャイな人たち (1) |
ユーザー |
![]() |
提出日時 | 2021-05-16 18:30:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,558 ms / 4,000 ms |
コード長 | 2,867 bytes |
コンパイル時間 | 2,304 ms |
コンパイル使用メモリ | 206,432 KB |
最終ジャッジ日時 | 2025-01-21 13:19:54 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
//https://ncode.syosetu.com/n4830bu/309/#include <bits/stdc++.h>using namespace std;int main() {int R, C;cin >> R >> C;vector P(R, vector(C, 0.0));vector S(R, vector(C, 0));for (auto&& V : P) {for (auto&& p : V) {cin >> p;p /= 100;}}for (auto&& V : S) {for (auto&& s : V) {cin >> s;}}vector maine(1 << C, 0.0);vector memo(1 << (C * 2), 0);vector seen(1 << (C * 2), false);maine[0] = 1;double ans = 0;for (int r = 0; r < R; r++) {auto& p = P[r];vector book(1 << C, 0.0);for (int bit = 0; bit < (1 << C); bit++) {double prob = 1.0;for (int c = 0; c < C; c++) {if (bit & (1 << c))prob *= p[c];elseprob *= (1 - p[c]);}for (int honzuki = 0; honzuki < (1 << C); honzuki++) {int mask = 0;int narou = 0;for (int i = 0; i < C; i++) {mask <<= 2;mask |= min(3, (bit & (1 << i)) ? max(S[r][i] - !!(honzuki & (1 << i)), 0) : 3);}if (seen[mask])narou = memo[mask];else {seen[mask] = true;auto s = S[r];int que = 0;for (int i = 0; i < C; i++) {if (s[i])if (honzuki & (1 << i))s[i]--;if (s[i] == 0 && (bit & (1 << i))) {que |= (1 << i);narou |= (1 << i);}}while (que) {int x = __builtin_ctz(que);que ^= (1 << x);for (int i = 0; i < 2; i++) {int y = x + 1 - i * 2;if (y >= 0 && y < C) {if (((1 << y) & narou) || !(bit & (1 << y)))continue;s[y]--;if (s[y] == 0) {narou |= (1 << y);que |= (1 << y);}}}}memo[mask] = narou;}book[narou] += prob * maine[honzuki];}}for (int bit = 0; bit < (1 << C); bit++) {ans += __builtin_popcount(bit) * book[bit];}swap(book, maine);}cout << fixed << setprecision(10) << ans << endl;}