結果

問題 No.133 カードゲーム
ユーザー mban
提出日時 2017-01-12 17:20:24
言語 C#
(mono 4.6.2)
結果
AC  
実行時間 33 ms
コード長 3508 Byte
コンパイル時間 300 ms
使用メモリ 12748 KB

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 32 ms
12732 KB
sample2.txt AC 30 ms
12740 KB
sample3.txt AC 29 ms
12692 KB
sample4.txt AC 31 ms
12740 KB
system_test1.txt AC 30 ms
12744 KB
system_test2.txt AC 31 ms
12744 KB
system_test3.txt AC 30 ms
12744 KB
system_test4.txt AC 31 ms
12748 KB
system_test5.txt AC 31 ms
12748 KB
system_test6.txt AC 29 ms
12740 KB
system_test7.txt AC 30 ms
12740 KB
system_test8.txt AC 30 ms
12740 KB
system_test9.txt AC 29 ms
12740 KB
system_test10.txt AC 30 ms
12748 KB
system_test11.txt AC 33 ms
12744 KB
system_test12.txt AC 29 ms
12740 KB
test1.txt AC 29 ms
12740 KB
test2.txt AC 29 ms
12748 KB
test3.txt AC 30 ms
12744 KB
test4.txt AC 30 ms
12744 KB
test5.txt AC 30 ms
12744 KB
test6.txt AC 29 ms
12744 KB
テストケース一括ダウンロード

ソースコード

diff #
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Text;
using System.Text.RegularExpressions;
using System.Linq;
using System.IO;

class Program
{
    static private Magatro M = new Magatro();
    static private void Main(string[]args)
    {
        M.Scan();
        M.Solve();
    }
}

public class Scanner
{
    private string[] S;
    private int Index;
    private char Separator;

    public Scanner(char separator = ' ')
    {
        Index = 0;
        Separator = separator;
    }

    private string[] Line()
    {
        return Console.ReadLine().Split(Separator);
    }

    public string Next()
    {
        string result;
        if (S == null || Index >= S.Length)
        {
            S = Line();
            Index = 0;
        }
        result = S[Index];
        Index++;
        return result;
    }
    public int NextInt()
    {
        return int.Parse(Next());
    }
    public double NextDouble()
    {
        return double.Parse(Next());
    }
    public long NextLong()
    {
        return long.Parse(Next());
    }
}

public class Magatro
{
    private int N;
    private int[] A, B;
    public void Scan()
    {
        Scanner sc = new Scanner();
        N = sc.NextInt();
        A = new int[N];
        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();
        }
    }

    public void Solve()
    {
        int[] temp = new int[N];
        for (int i = 0; i < N; i++)
        {
            temp[i] = i;
        }
        List<int[]> AList = new List<int[]>(), BList = new List<int[]>();

        int[] a = new int[N];
        int[] b = new int[N];
        for (int i = 0; i < N; i++)
        {
            a[i] = A[temp[i]];
            b[i] = B[temp[i]];
        }
        AList.Add(a);
        BList.Add(b);
        while (next_permutation(temp))
        {
           // Console.WriteLine(string.Join(" ", temp));
            a = new int[N];
            b = new int[N];
            for (int i = 0; i < N; i++)
            {
                a[i] = A[temp[i]];
                b[i] = B[temp[i]];
            }
            AList.Add(a);
            BList.Add(b);

        }
        int cnt = 0;
        int goukei = 0;
        foreach (var aa in AList)
        {
            foreach (var bb in BList)
            {
                goukei++;
                if (Q(aa, bb)) cnt++;
            }
        }
        Console.WriteLine((double)cnt / goukei);
    }
    private bool Q(int[] a, int[] b)
    {
        int acnt = 0;
        int bcnt = 0;
        for (int i = 0; i < N; i++)
        {
            if (a[i] > b[i]) acnt++;
            if (a[i] < b[i]) bcnt++;
        }
        if (acnt > bcnt) return true;
        else return false;
    }
    private bool next_permutation(int[] perm)
    {
        int n = perm.Length;
        int k = -1;
        for (int i = 1; i < n; i++)
            if (perm[i - 1] < perm[i])
                k = i - 1;
        if (k == -1)
        {
            for (int i = 0; i < n; i++)
                perm[i] = i;
            return false;
        }
        int l = k + 1;
        for (int i = l; i < n; i++)
            if (perm[k] < perm[i])
                l = i;
        int t = perm[k];
        perm[k] = perm[l];
        perm[l] = t;
        Array.Reverse(perm, k + 1, perm.Length - (k + 1));
        return true;
    }
}
0