結果

問題 No.309 シャイな人たち (1)
ユーザー uafr_cs
提出日時 2015-12-06 17:37:24
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,100 ms / 4,000 ms
コード長 4,600 bytes
コンパイル時間 2,297 ms
コンパイル使用メモリ 78,516 KB
実行使用メモリ 358,800 KB
最終ジャッジ日時 2024-09-14 15:59:49
合計ジャッジ時間 16,462 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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.
boolean[][][] using = new boolean[R][DP_SIZE][DP_SIZE];
int[][][] using_bit = new int[R][DP_SIZE][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(using[r][prev_raise_bit & curr_known_bit][curr_known_bit]){
DP[r + 1][using_bit[r][prev_raise_bit & curr_known_bit][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;
using_bit[r][prev_raise_bit & curr_known_bit][curr_known_bit] = curr_raise_bit;
using[r][prev_raise_bit & curr_known_bit][curr_known_bit] = true;
}
}
}
/*
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*/ }
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0