Submission #7682535

---

Source Code Expand

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();

    double[][] p = computeP(N);
    double[] exp = new double[N + 1];
    exp[1] = 0;
    for (int i = 2; i <= N; i++) {
      exp[i] = 1.d;
      for (int j = 1; j < i; j++) exp[i] += p[i][j] * exp[j];
      exp[i] /= 1 - p[i][i];
    }
    System.out.println(exp[N]);
  }

  private static double[][] computeP(int N) {
    double[][][] f = new double[N + 1][N + 1][N + 1];
    f[0][0][0] = 1.d;
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= N; j++) {
        for (int k = 0; k <= N; k++) {
          if (i == 0 && k == 0 && j == 0) continue;
          f[i][j][k] = 0.d;
          if (i > 0) f[i][j][k] += f[i - 1][j][k];
          if (j > 0) f[i][j][k] += f[i][j - 1][k];
          if (k > 0) f[i][j][k] += f[i][j][k - 1];
          f[i][j][k] /= 3.d;
        }
      }
    }
    // n人がじゃんけんをして少数派がm人になる確率
    double[][] p = new double[N + 1][N + 1];
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= N; j++) {
        for (int k = 0; k <= N; k++) {
          int n = i + j + k;
          if (n > N) continue;
          int m = (i == j && j == k) ? n : minNonZero(i, j, k);
          p[n][m] += f[i][j][k];
        }
      }
    }
    return p;
  }

  private static int minNonZero(int i, int j, int k) {
    if (i > j) return minNonZero(j, i, k);
    if (j > k) return minNonZero(i, k, j);
    if (i > 0) return i;
    if (j > 0) return j;
    return k;
  }
}

Submission Info

Judge Result