CODE THANKS FESTICAL 2014 G問題

g.c

#include <stdio.h>
#include <stdlib.h>

double probs[100];
double table[101][200][200]; // N,K,K

int main(void) {
  int i, j, k;
  int N, K;
  scanf("%d%d",&N,&K);
  for (i=0;i<N;i++) {
    int p;
    scanf("%d",&p);
    probs[i] = (double)p / 100.0;
  }
  for (i=1;i<=N;i++) {
    for (j=0;j<K;j++) {
      for (k=0;k<K;k++) {
        table[i][j][k] = 0.0;
      }
    }
  }

  // i = 処理した人数
  // j = 右端の人がいる席
  // k = 空席の数
  table[1][0][K-1] = 1.0;

  for (i=1;i<=N;i++) {
    for (j=0;j<K;j++) {
      for (k=K-1;k>=0;k--) {
        double prob = table[i][j][k];
        if (i == N) { // 全員処理した
          continue;
        }
        if (prob == 0.0) { // 到達しない状態
          continue;
        }
        // とにかく座る
        if (k - (K - j - 1) > 0) {
          table[i+1][j][k-1] += prob * probs[i]; // 隙間を埋める
        } else if (j <= K - 2) {
          table[i+1][j+1][k-1] += prob * probs[i]; // 右に座る
        } else {
          table[i+1][j][k] += prob * probs[i]; // 席が埋まった
        }
        // 空けて座る
        if (j <= K - 3) {
          table[i+1][j+2][k-1] += prob * (1.0 - probs[i]);
        } else {
          table[i+1][j][k] += prob * (1.0 - probs[i]); // 席が埋まった
        }
      }
    }
  }

  double sum = 0;
  for (i=0;i<K;i++) {
    for (j=0;j<K;j++) {
      double prob = table[N][i][j];
      sum += prob * j;
    }
  }
  printf("%.9f\n", sum);

  return 0;
}