// ReSharper disable ArrangeTypeMemberModifiers // ReSharper disable ConvertIfStatementToSwitchStatement // ReSharper disable FunctionRecursiveOnAllPaths // ReSharper disable InconsistentNaming // ReSharper disable InlineOutVariableDeclaration // ReSharper disable InvertIf // ReSharper disable JoinDeclarationAndInitializer // ReSharper disable MemberCanBeMadeStatic.Global // ReSharper disable MemberCanBeMadeStatic.Local // ReSharper disable NonReadonlyMemberInGetHashCode // ReSharper disable PossibleNullReferenceException // ReSharper disable RedundantUsingDirective // ReSharper disable SuggestVarOrType_BuiltInTypes // ReSharper disable SuggestVarOrType_Elsewhere // ReSharper disable TailRecursiveCall // ReSharper disable UnusedMember.Global // ReSharper disable UnusedMember.Local // ReSharper disable UseObjectOrCollectionInitializert #if true && UTAKA_LOCAL //#if false #define UTAKA_DEBUG #endif using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Diagnostics; using System.IO; using System.Linq; using System.Runtime.CompilerServices; using System.Text; using System.Numerics; using System.Runtime.InteropServices; namespace UtakaApp { public partial class Program { //========================================================================================= // Answer //========================================================================================= public const string SiteName = "Yukicoder"; public const string ContestName = "199"; public const string ProblemName = ""; public int N; public int[] A; public int[] B; public int[] opponentIndexes; public bool[] used; public int count; public void Solve() { N = cin.ReadInt; A = cin.ReadIntArray(N); B = cin.ReadIntArray(N); opponentIndexes = Enumerable.Repeat(-1, N).ToArray(); used = new bool[N]; Dfs(0); int all = 1; for (int i = 1; i <= N; i++) { all *= i; } double ans = ((double)count) / all; cou.WriteLine(ans); } public void Dfs(int cur) { if (cur == N) { int win = 0; int lose = 0; for (int i = 0; i < N; i++) { if (A[i] > B[opponentIndexes[i]]) win++; else if (A[i] < B[opponentIndexes[i]]) lose++; } if (win > lose) count++; return; } for (int i = 0; i < N; i++) { if (used[i]) continue; used[i] = true; opponentIndexes[cur] = i; Dfs(cur + 1); used[i] = false; opponentIndexes[cur] = -1; } } // NextPermutationによる解放 #if false public void Solve() { N = cin.ReadInt; A = cin.ReadIntArray(N); B = cin.ReadIntArray(N); long t = 1; for (int i = 1; i <= N; i++) { t *= i; } long total = t * t; Array.Sort(A); long count = 0; // NOTE: 二重にする必要なかったAは固定してもいい do { Array.Sort(B); do { int innerCount = 0; for (int i = 0; i < N; i++) { if (A[i] > B[i]) { innerCount++; } } if (innerCount > N / 2) { count++; } } while (NextPermutation(B, 0, N)); } while (NextPermutation(A, 0, N)); cou.WriteLine((double)count / total); } /// /// シーケンスの次の順列を求めます /// /// 順列を構成する要素の型 /// 次の順列を求めたいシーケンス /// 次の順列を求めたい範囲の最初のインデックス /// 次の順列を求めたい範囲の長さ /// 引数arrayが最後の順列ならばfalse、そうでないならtrueを返します public static bool NextPermutation(T[] array, int start, int length) where T : IComparable { int end = start + length - 1; // 範囲が狭すぎる if (end <= start) return false; int last = end; while (true) { int pos = last--; if (array[last].CompareTo(array[pos]) < 0) { int i; for (i = end + 1; array[last].CompareTo(array[--i]) >= 0;) { } T tmp = array[last]; array[last] = array[i]; array[i] = tmp; Array.Reverse(array, pos, end - pos + 1); return true; } if (last == start) // 最後の順列 { Array.Reverse(array, start, end - start); return false; } } // ここに来ることはない throw new Exception("NextPermutation: Fatal error"); } #endif } //========================================================================================= // Debug IO //========================================================================================= public partial class Program { //========================================================================================= // Main //========================================================================================= private readonly ConsoleInput cin; private readonly IConsole cou; public Program(ConsoleInput cin, IConsole cou) { this.cin = cin; this.cou = cou; } public static void Main(string[] args) { #if UTAKA_LOCAL //#if false new TestCaseCheckerForAtCoder().TestProblems(4); #else var cin = new ConsoleInput(System.Console.In); var console = new MyConsole(); new Program(cin, console).Solve(); console.Flush(); #endif } //========================================================================================= // Library //========================================================================================= /// /// 要素数 (a, b) の、defaultValue で満たされた配列を作成します。 /// /// 配列の型 /// 1次元の要素数 /// 2次元の要素数 /// デフォルト値 /// 指定した条件で初期化された配列 public static T[,] Array2D(int a, int b, T defaultValue) where T : struct { var ret = new T[a, b]; for (int i = 0; i < a; i++) { for (int j = 0; j < b; j++) { ret[i, j] = defaultValue; } } return ret; } /// /// 要素数 (a, b) のdefault値で満たされた配列を作成します。 /// /// 配列の型 /// 1次元の要素数 /// 2次元の要素数 /// 初期化された配列 public static T[,] Array2D(int a, int b) where T : struct { var ret = new T[a, b]; return ret; } /// /// 要素数 (a, b) の、defaultValue で満たされたJag配列を作成します。 /// /// 配列の型 /// 1次元の要素数 /// 2次元の要素数 /// デフォルト値 /// 指定した条件で初期化された配列 public static T[][] JagArray2D(int a, int b, T defaultValue) where T : struct { var ret = new T[a][]; for (int i = 0; i < a; i++) { ret[i] = Enumerable.Repeat(defaultValue, b).ToArray(); } return ret; } /// /// 要素数 (a, b) のdefault値で満たされたJag配列を作成します。 /// /// 配列の型 /// 1次元の要素数 /// 2次元の要素数 /// 初期化された配列 public static T[][] JagArray2D(int a, int b) where T : struct { var ret = new T[a][]; for (int i = 0; i < a; i++) { ret[i] = new T[b]; } return ret; } /// /// ジャグ配列をコピーして返す。 /// public static T[][] CopyJagArray(T[][] source) where T : struct { int len = source.Length; T[][] dest = new T[len][]; for (int i = 0; i < len; i++) { T[] inner = source[i]; int innerLength = inner.Length; T[] newer = new T[innerLength]; Array.Copy(inner, newer, innerLength); dest[i] = newer; } return dest; } } public class ConsoleInput { private readonly char _separator = ' '; private readonly TextReader _stream; private readonly Queue inputStream; public ConsoleInput(TextReader stream, char separator = ' ') { _separator = separator; _stream = stream; inputStream = new Queue(); } public string Read { get { if (inputStream.Count != 0) { return inputStream.Dequeue(); } var tmp = _stream.ReadLine().Split(_separator); for (var i = 0; i < tmp.Length; ++i) { inputStream.Enqueue(tmp[i]); } return inputStream.Dequeue(); } } public string ReadLine => _stream.ReadLine(); public int ReadInt => int.Parse(Read); public long ReadLong => long.Parse(Read); public double ReadDouble => double.Parse(Read); public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) { ret[i] = Read; } return ret; } public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadInt; } return ret; } public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) { ret[i] = ReadLong; } return ret; } } public interface IConsole { void Flush(); void Write(object obj); void Write(string str); void WriteLine(object obj); void WriteLine(string str); void WriteLine(); } public class MyConsole : IConsole { public MyConsole() { var sw = new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false}; Console.SetOut(sw); } public void Flush() { Console.Out.Flush(); } public void Write(object obj) { Write(obj.ToString()); } public void Write(string str) { Console.Write(str); } public void WriteLine(object obj) { WriteLine(obj.ToString()); } public void WriteLine(string str) { Console.WriteLine(str); } public void WriteLine() { Console.WriteLine(); } } #if UTAKA_LOCAL public class DebugConsole : IConsole { private readonly StringBuilder mSb; public DebugConsole() { mSb = new StringBuilder(); } public void Flush() { // 何もしない } public void Write(object obj) { Write(obj.ToString()); } public void Write(string str) { mSb.Append(str); } public void WriteLine(object obj) { WriteLine(obj.ToString()); } public void WriteLine(string str) { mSb.AppendLine(str); } public void WriteLine() { mSb.AppendLine(); } public string GetAllOutput() { return mSb.ToString(); } } #endif #if UTAKA_LOCAL public class TestCaseCheckerForAtCoder { private string GetDirectoryPath() { var problemPart = string.IsNullOrEmpty(Program.ProblemName) ? "" : $"/{Program.ProblemName}"; return $"{Environment.GetFolderPath(Environment.SpecialFolder.UserProfile)}/AlgorithmPrac/{Program.SiteName}/{Program.ContestName}{problemPart}"; } private string GetInputFilePath(int testCaseNumber) { return $"{GetDirectoryPath()}/sample-{testCaseNumber}.in"; } private string GetOutputFilePath(int testCaseNumber) { return $"{GetDirectoryPath()}/sample-{testCaseNumber}.out"; } public bool TestProblem(int testCaseNumber) { var inputFilePath = GetInputFilePath(testCaseNumber); var outputFilePath = GetOutputFilePath(testCaseNumber); TextReader inputStream = new StreamReader(inputFilePath); var cin = new ConsoleInput(inputStream); var debugConsoleWriter = new DebugConsole(); new Program(cin, debugConsoleWriter).Solve(); var output = debugConsoleWriter.GetAllOutput(); TextReader outputStream = new StreamReader(outputFilePath); var outputAnswer = outputStream.ReadToEnd(); Dbg.WriteLine(output); Dbg.WriteLine(outputAnswer); var isCorrect = output == outputAnswer; return isCorrect; } public void TestProblems(int targetTestCaseNumber = -1) { if (targetTestCaseNumber >= 0) { Console.WriteLine($"!!!!!!!!!!!! Check TestCase {targetTestCaseNumber} !!!!!!!!!!"); } bool isSuccessAll = true; int testCaseNumber = 0; while (true) { testCaseNumber++; if (targetTestCaseNumber >= 0 && targetTestCaseNumber != testCaseNumber) { continue; } var inputFileName = GetInputFilePath(testCaseNumber); if (!File.Exists(inputFileName)) { break; } Console.WriteLine($"TestCase {testCaseNumber} ====================================================="); var result = TestProblem(testCaseNumber); if (result) { Console.WriteLine("Success"); } else { isSuccessAll = false; Console.WriteLine("Failure *****"); } } if (isSuccessAll) { Console.WriteLine("!!!!!!!!! All Success !!!!!!!!!"); } } } #endif #if UTAKA_LOCAL public static class Dbg { public static void WriteLine(string str) { Console.WriteLine(str); } public static void Write(string str) { Console.Write(str); } } #else public static class Dbg { public static void WriteLine(string str) { } public static void Write(string str) { } } #endif }