結果

問題 No.173 カードゲーム（Medium）
コンテスト
ユーザー Grenache
提出日時 2016-07-18 21:29:29
言語 Java
(openjdk 23)
結果
AC  
実行時間 2,265 ms / 3,000 ms
コード長 2,936 bytes
コンパイル時間 5,191 ms
コンパイル使用メモリ 78,764 KB
実行使用メモリ 48,388 KB
最終ジャッジ日時 2024-10-15 17:05:03
合計ジャッジ時間 20,024 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;


public class Main_yukicoder173 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Printer pr = new Printer(System.out);

        int n = sc.nextInt();
        int pa = (int)(sc.nextDouble() * 1000);
        int pb = (int)(sc.nextDouble() * 1000);

        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
        	a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
        	b[i] = sc.nextInt();
        }
        Arrays.sort(a);
        Arrays.sort(b);

        int win = 0;
        int loop = 1_000_000;
        for (int i = 0; i < loop; i++) {
    		int aa = 0;
    		int bb = 0;
    		int maska = 0;
    		int maskb = 0;
            int mask = (0x1 << n) - 1;
            int[] sa = new int[n];
            int[] sb = new int[n];
    		for (int j = 0; j < n; j++) {
            	int mina = Integer.numberOfTrailingZeros(~maska & mask);
            	int minb = Integer.numberOfTrailingZeros(~maskb & mask);

            	if (j == n - 1) {
            		sa[j] = mina;
            		sb[j] = minb;
            	} else {
            		int ra = (int)(Math.random() * 1000);
            		int rb = (int)(Math.random() * 1000);
            		if (ra < pa) {
            			sa[j] = mina;
            			maska |= 0x1 << mina;
            		} else {
//            			int tmp = (int)((double)(ra + 1 - pa) / (1000 - pa) * (n - j - 1));
            			int tmp = (int)(Math.random() * (n - j - 1));
            			for (int k = mina + 1; k < n; k++) {
            				if ((maska & 0x1 << k) != 0) {
            					continue;
            				}
            				if (tmp == 0) {
            					sa[j] = k;
            					maska |= 0x1 << k;
            					break;
            				}
            				tmp--;
            			}
            		}
            		if (rb < pb) {
            			sb[j] = minb;
            			maskb |= 0x1 << minb;
            		} else {
//            			int tmp = (int)((double)(rb + 1 - pb) / (1000 - pb) * (n - j - 1));
            			int tmp = (int)(Math.random() * (n - j - 1));
            			for (int k = minb + 1; k < n; k++) {
            				if ((maskb & 0x1 << k) != 0) {
            					continue;
            				}
            				if (tmp == 0) {
            					sb[j] = k;
            					maskb |= 0x1 << k;
            					break;
            				}
            				tmp--;
            			}
            		}
            	}
    		}

    		for (int j = 0; j < n; j++) {
            	if (a[sa[j]] > b[sb[j]]) {
    				aa += a[sa[j]] + b[sb[j]];
    			} else {
    				bb += a[sa[j]] + b[sb[j]];
    			}
    		}

    		if (aa > bb) {
    			win++;
    		}
        }

        pr.printf("%.4f\n", (double)win / loop);

        pr.close();
        sc.close();
    }

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}
0