C – Standings
1 から N の番号が付いた N 人がコイントスを何回かしました。人 i は A_i 回表を出し、B_i 回裏を出したこと分かっています。
人 i のコイントスの 成功率 は A_i / (A_i + B_i) で定義されます。人 1, …, N の番号を、成功率の高い順に並び替えてください。成功率が同じ人が複数いる場合、その中では人の番号が小さい順になるように並び替えてください。
入力されるデータ
N
A_1 B_1
A_2 B_2
：
A_N B_N（ただし 2 ≦ N ≦ 2×10^5
0 ≦ A_i, B_i ≦ 10^9
A_i + B_i ≦ 1 ）
簡単そうで難しい問題です。
成功率を A_i / (A_i + B_i) で算出してソートすればよいのではないか？
それだと罠にかかります。
以下は成功率を A_i / (A_i + B_i) で算出してソート（成功率が同じ人が複数いる場合、その中では人の番号が小さい順にソート）しただけのコードです。
結果は不正解。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
using System; using System.Collections.Generic; using System.Linq; class P // P は Person の略 { public P(int num, double d) { Number = num; D = d; } public int Number = 0; public double D = 0; } class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<P> list = new List<P>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); double bunbo = (double)vs[0] + vs[1]; double d = (double)vs[0] / bunbo; list.Add(new P(i + 1, d)); } list = list.OrderByDescending(p => p.D).ThenBy(p => p.Number).ToList(); int[] arr = list.Select(_ => _.Number).ToArray(); Console.WriteLine(string.Join(" ", arr)); } } |
浮動小数点型による誤差
なぜか？
大小を浮動小数点型を用いて比較するのは、誤差の関係上危険です。実際、double を用いた大小比較による解法は落ちるケースが複数入っています。
2つの実数 A = 165580141 / 267914296 , B = 433494437 / 701408733 を考えてみます。実際に計算してみると、A ≒ 0.61803398874989485443509143685、B ≒ 0.61803398874989484911360520514 であり A のほうが大きいです。ところが double 型で計算すると両方とも 0.618033988749895 です。これがこの問題に仕掛けられた罠だったのです。
では、どうすればよいのか？ 整数同士で比較できるようにすればよいのです。
A_1 / (A_1 + B_1) と A_2 / (A_2 + B_2) であれば双方を(A_1 + B_1) * (A_2 + B_2)倍して、A_1 * (A_2 + B_2) と A_2 * (A_1 + B_1) を比較すればよいのです。これなら誤差は入りません。
大小関係を自分で定義するには？
問題はOrderByDescendingを使ってソートする部分をどうするかです。これは以下のようにすればよいです。
まず SpecialComparer クラス（名前は何でもよいが…）を定義します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
public class SpecialComparer : IComparer<Person> { public int Compare(Person p1, Person p2) { long c1 = p1.A * (p2.A + p2.B); long c2 = p2.A * (p1.A + p1.B); if (c1 == c2) return 0; else if (c1 > c2) return 1; else return -1; } } list = list.OrderByDescending(p => p, new SpecialComparer()).ThenBy(p => p.Number).ToList(); |
以下のコードを提出すると AC（= 正解）となりました。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
using System; using System.Collections.Generic; using System.Linq; public class Person { public Person(int num, int a, int b) { Number = num; A = a; B = b; } public int Number = 0; public long A = 0; public long B = 0; } class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<Person> list = new List<Person>(); for (int i = 0; i < N; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); list.Add(new Person(i + 1, vs[0], vs[1])); } list = list.OrderByDescending(p => p, new SpecialComparer()).ThenBy(p => p.Number).ToList(); int[] arr = list.Select(_ => _.Number).ToArray(); Console.WriteLine(string.Join(" ", arr)); } } public class SpecialComparer : IComparer<Person> { public int Compare(Person p1, Person p2) { long c1 = p1.A * (p2.A + p2.B); long c2 = p2.A * (p1.A + p1.B); if (c1 == c2) return 0; else if (c1 > c2) return 1; else return -1; } } |
