結果
問題 | No.133 カードゲーム |
ユーザー | utaka |
提出日時 | 2019-11-10 18:18:13 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 31 ms / 5,000 ms |
コード長 | 17,507 bytes |
コンパイル時間 | 1,036 ms |
コンパイル使用メモリ | 109,952 KB |
実行使用メモリ | 19,840 KB |
最終ジャッジ日時 | 2024-09-15 05:02:07 |
合計ジャッジ時間 | 2,411 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 29 ms
19,456 KB |
testcase_01 | AC | 28 ms
19,712 KB |
testcase_02 | AC | 31 ms
19,712 KB |
testcase_03 | AC | 28 ms
18,944 KB |
testcase_04 | AC | 29 ms
19,712 KB |
testcase_05 | AC | 29 ms
19,712 KB |
testcase_06 | AC | 30 ms
19,840 KB |
testcase_07 | AC | 29 ms
19,712 KB |
testcase_08 | AC | 29 ms
19,840 KB |
testcase_09 | AC | 29 ms
19,840 KB |
testcase_10 | AC | 30 ms
19,712 KB |
testcase_11 | AC | 29 ms
19,840 KB |
testcase_12 | AC | 29 ms
19,584 KB |
testcase_13 | AC | 30 ms
19,840 KB |
testcase_14 | AC | 30 ms
19,840 KB |
testcase_15 | AC | 30 ms
19,584 KB |
testcase_16 | AC | 29 ms
19,840 KB |
testcase_17 | AC | 28 ms
19,072 KB |
testcase_18 | AC | 29 ms
19,712 KB |
testcase_19 | AC | 29 ms
19,712 KB |
testcase_20 | AC | 30 ms
19,712 KB |
testcase_21 | AC | 30 ms
19,712 KB |
testcase_22 | AC | 29 ms
19,712 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
// 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); } /// <summary> /// シーケンスの次の順列を求めます /// </summary> /// <typeparam name="T">順列を構成する要素の型</typeparam> /// <param name="array">次の順列を求めたいシーケンス</param> /// <param name="start">次の順列を求めたい範囲の最初のインデックス</param> /// <param name="length">次の順列を求めたい範囲の長さ</param> /// <returns>引数arrayが最後の順列ならばfalse、そうでないならtrueを返します</returns> public static bool NextPermutation<T>(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 //========================================================================================= /// <summary> /// 要素数 (a, b) の、defaultValue で満たされた配列を作成します。 /// </summary> /// <typeparam name="T">配列の型</typeparam> /// <param name="a">1次元の要素数</param> /// <param name="b">2次元の要素数</param> /// <param name="defaultValue">デフォルト値</param> /// <returns>指定した条件で初期化された配列</returns> public static T[,] Array2D<T>(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; } /// <summary> /// 要素数 (a, b) のdefault値で満たされた配列を作成します。 /// </summary> /// <typeparam name="T">配列の型</typeparam> /// <param name="a">1次元の要素数</param> /// <param name="b">2次元の要素数</param> /// <returns>初期化された配列</returns> public static T[,] Array2D<T>(int a, int b) where T : struct { var ret = new T[a, b]; return ret; } /// <summary> /// 要素数 (a, b) の、defaultValue で満たされたJag配列を作成します。 /// </summary> /// <typeparam name="T">配列の型</typeparam> /// <param name="a">1次元の要素数</param> /// <param name="b">2次元の要素数</param> /// <param name="defaultValue">デフォルト値</param> /// <returns>指定した条件で初期化された配列</returns> public static T[][] JagArray2D<T>(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; } /// <summary> /// 要素数 (a, b) のdefault値で満たされたJag配列を作成します。 /// </summary> /// <typeparam name="T">配列の型</typeparam> /// <param name="a">1次元の要素数</param> /// <param name="b">2次元の要素数</param> /// <returns>初期化された配列</returns> public static T[][] JagArray2D<T>(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; } /// <summary> /// ジャグ配列をコピーして返す。 /// </summary> public static T[][] CopyJagArray<T>(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<string> inputStream; public ConsoleInput(TextReader stream, char separator = ' ') { _separator = separator; _stream = stream; inputStream = new Queue<string>(); } 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 }