[yukicoder] No.133 カードゲーム

問題

No.133 カードゲーム - yukicoder

誤差の許容が緩いので、モンテカルロ法で解くことにしました。でも、モンテカルロ法の実装とそれ以外で難易度に差がないような気もします。

考え方

カードの出し方は 通りあります。カードの出し方を配列に格納し、ランダムに出し方を決めることで、モンテカルロ法で解くことができます。

カードの出し方は、順列の列挙を使うことで求められます。

コード

import java.util.Arrays;
import java.util.Scanner;

public class Exec0133 {
    static int[][] list;
    static int index = 0;
    static int N;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        int []A = new int[N];
        int []B = new int[N];

        for(int i = 0; i < N; i++) {
            A[i] = scan.nextInt();
        }
        for(int i = 0; i < N; i++) {
            B[i] = scan.nextInt();
        }
        scan.close();
        int l = fact(N);
        list = new int[l][N];
        int []a = new int[N];
        perm(0, a, new boolean[N + 1]);

        Arrays.fill(a, 0);
        int n = 100000;
        int win = 0;
        for(int i = 0; i < n; i++) {
            int t1 = (int)(Math.random() * l);
            int t2 = (int)(Math.random() * l);
            int cnt1 = 0;
            int cnt2 = 0;
            for(int j = 0; j < N; j++) {
                int c1 = A[list[t1][j] - 1];
                int c2 = B[list[t2][j] - 1];
                if(c1 > c2) {
                    cnt1 ++;
                }else if(c1 < c2) {
                    cnt2 ++;
                }
            }
            if(cnt1 > cnt2) {
                win ++;
            }
        }

        double ans = (double) win / n;
        System.out.println(ans);

    }
    static void perm(int n, int[] a, boolean[] flag) {
        if(n == a.length) {
            for(int i = 0; i < N; i++) {
                list[index][i] = a[i];
            }
            index ++;
            return;
        }
        for(int i = 1; i <= a.length; i++) {
            if(flag[i]) continue;
            a[n] = i;
            flag[i] = true;
            perm(n + 1, a, flag);
            flag[i] = false;
        }
    }
    static int fact(int n) {
        if(n == 1) {
            return 1;
        }else {
            return n * fact(n - 1);
        }
    }
}