Hatena::Grouptopcoder

tsubosakaの日記

2009-01-15

SRM 286 Div1 Easy

| 09:36

当たる確率のあるパターンは現在リーチになっているものだけなので期待値の独立性から(リーチになっているものの賞金総額) / (残りのボールの数)を計算すればよい.

import java.util.*;
public class ExtraBall {
  public double expectedPayout(int[] card, int[] balls, String[] patterns,
      int[] prizes) {
    Arrays.sort(balls);
    int cs[] = new int[card.length];
    for(int i = 0 ; i < card.length ; i++)
      if(Arrays.binarySearch(balls, card[i]) >= 0)
        cs[i] = 1;
    double tot = 0.0;
    for(int p = 0 ; p < patterns.length ; p++){
      int diff = 0;
      String pattern = patterns[p];
      for(int j = 0 ; j < cs.length ; j++)
        if(cs[j] == 0 && pattern.charAt(j) == 'X')
          diff++;
      if(diff == 1)
        tot += prizes[p];      
    }
    double res = tot / (75.0 - balls.length);
    return res;
  }
}