#330123 (Java) No.133 カードゲーム

• 問題: No.133 カードゲーム
• ユーザー: k_6101
• 提出日時: 2019-03-29 23:53:00
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 57 ms / 5,000 ms
• コード長: 6,731 bytes
• コンパイル時間: 2,831 ms
• コンパイル使用メモリ: 81,380 KB
• 実行使用メモリ: 37,320 KB
• 最終ジャッジ日時: 2024-11-07 01:33:57
• 合計ジャッジ時間: 5,103 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 4
other	AC * 19

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.util.AbstractMap;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.TreeSet;
public class Main {
    
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyInput in = new MyInput(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        
        Solver solver = new Solver();
        solver.solve(1, in, out);
        
        out.close();
    }
    
    // ======================================================================
    // 1 <= N <= 4 : 　一人のカード枚数
    // a0 - aN-1 : A君のカード
    // b0 - bN-1 : B君のカード
    //
    // カードをお互いに出して、数字が大きい方が勝つ。　A君が勝つ確率は？
    // 
    // 深さ優先で検索して、全ての点を回る（深さが頂点の数まで行けた）かで判断する
    //
    static class Solver {
        int N;                              // 一人のカード枚数
        int[] A = null;                     // A君のカード
        int[] B = null;                     // B君のカード
        boolean[] used = null;              // 使用済みのマーク
        int[] data = null;                  // 作成中の順列の１つ
        
        // 順列の作成　　　now : 現在の値　　depth : 現在の深さ
        public int permutation(int now, int depth, PrintWriter out) {
//          out.println("start  now = " + now + "  depth = " + depth );
            if(depth == N) {                // できた順列の１つに対する処理
//                  for(int i = 0; i < N; i++)     out.print("[" + data[i] + "]");
//                  out.println("");
                int win = 0;                // この場合は勝ち負けの判定
                for(int i=0; i < N; i++) {
                    if(data[i] > B[i])      win++;
                }
//                  out.println("   -->  win = " + win + "  N/2 = " + (N/2));
                if(win > N/2)   return 1;
                else            return 0;
            }
            int ans = 0;
            for(int i=0; i < N; i++) {
                if(!used[i]) {
                    used[i] = true;     //　使用済みとする
                    data[depth] = A[i];
                    ans += permutation(i, depth + 1, out);
                    used[i] = false;    // 戻す
                }
            }
//          out.println("end  now = " + now + "  depth = " + depth + "  ans = " + ans);
            return ans;
        }
        
        // n! の計算
        public  int fact(int n) {
            return n == 0 ? 1 : n * fact(n - 1);
        }
        public void solve(int testNumber, MyInput in, PrintWriter out) {
            double ans = 0;
            N = in.nextInt();
            A = new int[N];
            B = new int[N];
            used = new boolean[N];
            data = new int[N];
            for(int i=0; i < N; i++) {
                A[i] = in.nextInt();
            }
            for(int i=0; i < N; i++) {
                B[i] = in.nextInt();
            }
            ans = (double)permutation(0, 0, out) / (double)(fact(N));  
            out.println(ans);
        }
    }
    // ======================================================================
    static class Pair<K, V> extends AbstractMap.SimpleEntry<K, V> {
        /** serialVersionUID. */
        private static final long serialVersionUID = 6411527075103472113L;
        public Pair(final K key, final V value) {
            super(key, value);
        }
     }    
    static class MyInput {
        private final BufferedReader in;
        private static int pos;
        private static int readLen;
        private static final char[] buffer = new char[1024 * 8];
        private static char[] str = new char[500 * 8 * 2];
        private static boolean[] isDigit = new boolean[256];
        private static boolean[] isSpace = new boolean[256];
        private static boolean[] isLineSep = new boolean[256];
 
        static {
            for (int i = 0; i < 10; i++) {
                isDigit['0' + i] = true;
            }
            isDigit['-'] = true;
            isSpace[' '] = isSpace['\r'] = isSpace['\n'] = isSpace['\t'] = true;
            isLineSep['\r'] = isLineSep['\n'] = true;
        }
 
        public MyInput(InputStream is) {
            in = new BufferedReader(new InputStreamReader(is));
        }
 
        public int read() {
            if (pos >= readLen) {
                pos = 0;
                try {
                    readLen = in.read(buffer);
                } catch (IOException e) {
                    throw new RuntimeException();
                }
                if (readLen <= 0) {
                    throw new MyInput.EndOfFileRuntimeException();
                }
            }
            return buffer[pos++];
        }
 
        public int nextInt() {
            int len = 0;
            str[len++] = nextChar();
            len = reads(len, isSpace);
            int i = 0;
            int ret = 0;
            if (str[0] == '-') {
                i = 1;
            }
            for (; i < len; i++) ret = ret * 10 + str[i] - '0';
            if (str[0] == '-') {
                ret = -ret;
            }
            return ret;
        }
 
        public String nextString() {
            String ret = new String(nextDChar()).trim();
            return ret;
        }
 
        public char[] nextDChar() {
            int len = 0;
            len = reads(len, isSpace);
            char[] ret = new char[len + 1];
            for (int i=0; i < len; i++)     ret[i] = str[i];
            ret[len] = 0x00;
            return ret;
        }
 
        public char nextChar() {
            while (true) {
                final int c = read();
                if (!isSpace[c]) {
                    return (char) c;
                }
            }
        }
 
        int reads(int len, boolean[] accept) {
            try {
                while (true) {
                    final int c = read();
                    if (accept[c]) {
                        break;
                    }
                    if (str.length == len) {
                        char[] rep = new char[str.length * 3 / 2];
                        System.arraycopy(str, 0, rep, 0, str.length);
                        str = rep;
                    }
                    str[len++] = (char) c;
                }
            } catch (MyInput.EndOfFileRuntimeException e) {
            }
            return len;
        }
 
        static class EndOfFileRuntimeException extends RuntimeException {
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX