結果

問題 No.133 カードゲーム
ユーザー jun0sckjun0sck
提出日時 2018-04-18 09:19:20
言語 Java21
(openjdk 21)
結果
AC  
実行時間 47 ms / 5,000 ms
コード長 4,406 bytes
コンパイル時間 2,226 ms
コンパイル使用メモリ 77,384 KB
実行使用メモリ 50,496 KB
最終ジャッジ日時 2023-09-09 11:20:34
合計ジャッジ時間 4,635 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
49,676 KB
testcase_01 AC 45 ms
49,528 KB
testcase_02 AC 45 ms
49,556 KB
testcase_03 AC 44 ms
49,932 KB
testcase_04 AC 45 ms
49,708 KB
testcase_05 AC 46 ms
49,608 KB
testcase_06 AC 46 ms
49,540 KB
testcase_07 AC 47 ms
49,504 KB
testcase_08 AC 44 ms
49,824 KB
testcase_09 AC 44 ms
49,740 KB
testcase_10 AC 46 ms
49,500 KB
testcase_11 AC 46 ms
49,564 KB
testcase_12 AC 46 ms
50,408 KB
testcase_13 AC 45 ms
49,572 KB
testcase_14 AC 45 ms
49,472 KB
testcase_15 AC 45 ms
49,544 KB
testcase_16 AC 47 ms
49,580 KB
testcase_17 AC 46 ms
49,584 KB
testcase_18 AC 46 ms
50,496 KB
testcase_19 AC 47 ms
50,268 KB
testcase_20 AC 46 ms
49,500 KB
testcase_21 AC 46 ms
49,536 KB
testcase_22 AC 47 ms
49,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {

    private static Scanner sc;
    private static int[][] neg8 = new int[][]{{-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1}};
    private static int[][] neg4 = new int[][]{{1, 0}, {0, -1}, {-1, 0}, {0, 1}};

    public static void main(String[] args) {
        Main instance = new Main();
        sc = instance.new Scanner();
        instance.solve();
    }

    private void solve() {
        try {
            int N = sc.nextInt();
            int[]a = new int[N];
            for (int i = 0; i < N; i++) {
                a[i] = sc.nextInt();
            }
            int[]b = new int[N];
            for (int i = 0; i < N; i++) {
                b[i] = sc.nextInt();
            }

            List<List<Integer>> al = new ArrayList<>();
            {
                Arrays.sort(a);
                al.add(genList(a));
                while (nextPermutation(a)) {
                    al.add(genList(a));
                }
            }
            List<List<Integer>> bl = new ArrayList<>();
            {
                Arrays.sort(b);
                bl.add(genList(b));
                while (nextPermutation(b)) {
                    bl.add(genList(b));
                }
            }

            int gameCount = 0;
            int totalWinA = 0;
            for (List<Integer> inta : al) {
                for (List<Integer> intb : bl) {
                    gameCount++;
                    int win = 0;
                    for (int i = 0; i < N; i++) {
                        if (intb.get(i) < inta.get(i)) win++;
                    }
                    if ((N/2) < win) totalWinA++;
                }
            }

            System.out.println(totalWinA / (float)gameCount);

        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    private List<Integer> genList(int[]arr) {
        List<Integer> res = new ArrayList<>();
        for (int i : arr) {
            res.add(i);
        }
        return res;
    }

    private class Scanner {
        String[] s;
        int i;
        BufferedReader br;
        String regex = " ";

        public Scanner() {
            s = new String[0];
            i = 0;
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        @Override
        protected void finalize() throws Throwable {
            try {
                super.finalize();
            } finally {
                destruction();
            }
        }

        private void destruction() throws IOException {
            if (br != null) br.close();
        }

        public String next() throws IOException {
            if (i < s.length) return s[i++];
            String st = br.readLine();
            while (st == "") st = br.readLine();
            s = st.split(regex, 0);
            i = 0;
            return s[i++];
        }

        public int nextInt() throws NumberFormatException, IOException {
            return Integer.parseInt(next());
        }

        public Long nextLong() throws NumberFormatException, IOException {
            return Long.parseLong(next());
        }

        public Double nextDouble() throws NumberFormatException, IOException {
            return Double.parseDouble(next());
        }
    }

    private static double distance(int x1, int x2, int y1, int y2) {
        return Math.sqrt((Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)));
    }

    private static boolean nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        boolean swap = false;
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
            swap = true;
        }
        reverse(nums, i + 1);
        return swap;
    }

    private static void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
0