結果
問題 | No.309 シャイな人たち (1) |
ユーザー |
![]() |
提出日時 | 2015-12-06 17:25:17 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 3,597 ms / 4,000 ms |
コード長 | 4,422 bytes |
コンパイル時間 | 2,591 ms |
コンパイル使用メモリ | 78,952 KB |
実行使用メモリ | 48,764 KB |
最終ジャッジ日時 | 2024-09-14 15:59:24 |
合計ジャッジ時間 | 29,549 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 |
ソースコード
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashSet;import java.util.LinkedList;import java.util.Scanner;import java.util.Set;import java.util.StringTokenizer;public class Main {public static final double EPS = 1e-8;public static void main(String[] args) {Scanner sc = new Scanner(System.in);final int R = sc.nextInt();final int C = sc.nextInt();double[][] probs = new double[R][C];for(int i = 0; i < R; i++){for(int j = 0; j < C; j++){probs[i][j] = sc.nextDouble();}}int[][] shys = new int[R][C];for(int i = 0; i < R; i++){for(int j = 0; j < C; j++){shys[i][j] = sc.nextInt();}}final int DP_SIZE = 1 << C;double[][] knowns_probs = new double[R][DP_SIZE];for(int r = 0; r < R; r++){ Arrays.fill(knowns_probs[r], 1); }int[] shy_zero_bits = new int[R];int[] shy_one_bits = new int[R];for(int r = 0; r < R; r++){for(int c = 0; c < C; c++){shy_zero_bits[r] |= (((shys[r][c] == 0) ? 1 : 0) << c);shy_one_bits[r] |= (((shys[r][c] == 1) ? 1 : 0) << c);}}for(int bit = 0; bit < DP_SIZE; bit++){for(int r = 0; r < R; r++){for(int i = 0; i < C; i++){knowns_probs[r][bit] *= ((bit & (1 << i)) != 0) ? (probs[r][i] / 100.0) : (1 - probs[r][i] / 100.0);}}}double[][] DP = new double[R + 1][DP_SIZE]; //配るDPする.int[][] using_bit = new int[R][DP_SIZE];boolean[][] reached = new boolean[R + 1][DP_SIZE];Arrays.fill(DP[0], 0);DP[0][0] = 1.0; reached[0][0] = true;int[] curr_line = new int[C];for(int r = 0; r < R; r++){ // O(R) -> 11//System.out.println(r);for(int curr_known_bit = 0; curr_known_bit < DP_SIZE; curr_known_bit++) {for(int prev_raise_bit = 0; prev_raise_bit < DP_SIZE; prev_raise_bit++){if(prev_raise_bit != 0 && (curr_known_bit & prev_raise_bit) == 0){DP[r + 1][using_bit[r][curr_known_bit]] += DP[r][prev_raise_bit] * knowns_probs[r][curr_known_bit];continue;}if(!reached[r][prev_raise_bit]){ continue; }final int somebody_raise_bit = shy_zero_bits[r] | (shy_one_bits[r] & prev_raise_bit);if((curr_known_bit & somebody_raise_bit) == 0){DP[r + 1][0] += DP[r][prev_raise_bit] * knowns_probs[r][curr_known_bit];reached[r + 1][0] |= true;continue;}int curr_raise_bit = 0;for(int i = 0; i < C; i++){curr_line[i] = ((curr_known_bit & (1 << i)) == 0 ? 0 : 4 - shys[r][i]) + ((prev_raise_bit & (1 << i)) != 0 ? 1 : 0);if(curr_line[i] >= 4){ curr_raise_bit |= (1 << i); }}//if(can_sat){for(int i = 0; i < C - 1; i++){if((curr_raise_bit & (1 << i)) != 0 && (curr_raise_bit & (1 << (i + 1))) == 0){if(++curr_line[i + 1] >= 4){ curr_raise_bit |= (1 << (i + 1)); }}}for(int i = C - 1; i >= 1; i--){if((curr_raise_bit & (1 << i)) != 0 && (curr_raise_bit & (1 << (i - 1))) == 0){if(++curr_line[i - 1] >= 4){ curr_raise_bit |= (1 << (i - 1)); }}}//}DP[r + 1][curr_raise_bit] += DP[r][prev_raise_bit] * knowns_probs[r][curr_known_bit];reached[r + 1][curr_raise_bit] |= true;if(prev_raise_bit == 0){using_bit[r][curr_known_bit] = curr_raise_bit;}}}}/*for(double[] bits : DP){System.out.println(Arrays.toString(bits));}*/double answer = 0;for(int r = 1; r <= R; r++){for(int bit = 0; bit < DP_SIZE; bit++){answer += Integer.bitCount(bit) * DP[r][bit];}}System.out.printf("%.11f\n", answer);}public static class Scanner {private BufferedReader br;private StringTokenizer tok;public Scanner(InputStream is) {br = new BufferedReader(new InputStreamReader(is));}private void getLine() {try {while (!hasNext()) {tok = new StringTokenizer(br.readLine());}} catch(IOException e){ /* ignore */ }}private boolean hasNext() {return tok != null && tok.hasMoreTokens();}public String next() {getLine(); return tok.nextToken();}public int nextInt(){return Integer.parseInt(next());}public double nextDouble(){return Double.parseDouble(next());}public void close() {try{ br.close(); } catch (IOException e){ /*ignore*/ }}}}