結果
| 問題 |
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 |
ソースコード
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 {
}
}
}