Submission #5068348
Source Code Expand
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using BitArray = System.Collections.BitArray; using BigInteger = System.Numerics.BigInteger; namespace AtCoderProject { class Program { static void Main() { Console.WriteLine(new Program().Calc()); } public object Calc() { var K = ReadLineInt32(); var N = (int)Math.Pow(2, K); var Rs = Enumerable.Repeat(0, N).Select(_ => ReadLineInt32()).ToArray(); var dp = new double[N, K + 1]; // dp[i,k]は選手iがkラウンドで勝ち上がる確率 for (int i = 0; i < N; i++) { dp[i, 0] = 1; } int groupFighterNum = 1; for (int k = 1; k <= K; k++) { groupFighterNum *= 2; for (int i = 0; i < N; i++) { var groupFirstFighter = i / groupFighterNum * groupFighterNum; int startFighter, endFighter; if (i < groupFirstFighter + groupFighterNum / 2) { startFighter = groupFirstFighter + groupFighterNum / 2; endFighter = groupFirstFighter + groupFighterNum - 1; } else { startFighter = groupFirstFighter; endFighter = groupFirstFighter + groupFighterNum / 2 - 1; } for (int j = startFighter; j <= endFighter; j++) { if (i == j) continue; dp[i, k] += (1 / (1 + Math.Pow(10, (Rs[j] - Rs[i]) / 400.0))) * dp[j, k - 1]; } dp[i, k] *= dp[i, k - 1]; } } var sb = new StringBuilder(); for (int i = 0; i < N; i++) sb.AppendLine(dp[i, K].ToString()); return sb.ToString(); } #if DEBUG #pragma warning disable IDE0051 // 使用されていないプライベート メンバーを削除する #pragma warning disable IDE1006 // 命名スタイル static string _ReadLineImpl() => queue.Dequeue(); #pragma warning restore IDE1006 // 命名スタイル static readonly Queue<string> queue; static Program() { string input = @" 3 2000 2500 2300 2700 2100 2400 2600 2200 "; queue = new Queue<string>(); foreach (var line in input.Split(new char[] { '\r', '\n' }, StringSplitOptions.RemoveEmptyEntries)) queue.Enqueue(line); } #else private static string _ReadLineImpl() => Console.ReadLine(); #endif static string ReadLine() => _ReadLineImpl(); static int ReadLineInt32() => int.Parse(ReadLine()); static long ReadLineInt64() => long.Parse(ReadLine()); static ulong ReadLineUInt64() => ulong.Parse(ReadLine()); static double ReadLineDouble() => double.Parse(ReadLine()); static string[] ReadLineSplit() => ReadLine().Split().ToArray(); static int[] ReadLineSplitInt32() => ReadLine().Split().Select(s => int.Parse(s)).ToArray(); static long[] ReadLineSplitInt64() => ReadLine().Split().Select(s => long.Parse(s)).ToArray(); static ulong[] ReadLineSplitUInt64() => ReadLine().Split().Select(s => ulong.Parse(s)).ToArray(); static double[] ReadLineSplitDouble() => ReadLine().Split().Select(s => double.Parse(s)).ToArray(); static IEnumerable<string> RepeatReadLines(int count) { for (int i = 0; i < count; i++) yield return ReadLine(); } static IEnumerable<int> RepeatReadLinesInt32(int count) { for (int i = 0; i < count; i++) yield return ReadLineInt32(); } static IEnumerable<string[]> RepeatReadLinesSplit(int count) { for (int i = 0; i < count; i++) yield return ReadLineSplit(); } } static class BitArrayUtils { static BitArray ToBitArray(this long l) { return new BitArray(BitConverter.GetBytes(l)); } static long ToInt64(this BitArray bitArray) { var array = new byte[8]; bitArray.CopyTo(array, 0); return BitConverter.ToInt64(array, 0); } static BitArray ToBitArray(this ulong l) { return new BitArray(BitConverter.GetBytes(l)); } static ulong ToUInt64(this BitArray bitArray) { var array = new byte[8]; bitArray.CopyTo(array, 0); return BitConverter.ToUInt64(array, 0); } } }
Submission Info
Submission Time | |
---|---|
Task | C - トーナメント |
User | kzrnm |
Language | C# (Mono 4.6.2.0) |
Score | 4 |
Code Size | 4992 Byte |
Status | AC |
Exec Time | 120 ms |
Memory | 13420 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 4 / 4 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 120 ms | 13420 KB |
01 | AC | 119 ms | 13420 KB |
02 | AC | 56 ms | 11292 KB |
03 | AC | 118 ms | 13420 KB |
90 | AC | 24 ms | 13396 KB |
91 | AC | 24 ms | 11348 KB |