はじめに
AtCoder Beginner Contest 313の復習記事です。
記事におけるScannerクラスは、自作の入力クラスです。
Scannerクラス
public static class Scanner
{
public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]));
}
public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
}
public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
}
public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
}
public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
{
var input = ScanStringArray();
return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
}
public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
private static string[] ScanStringArray()
{
var line = Console.ReadLine()?.Trim() ?? string.Empty;
return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
}
private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
}
コンテスト
https://atcoder.jp/contests/abc313
問題A
Nが1のときは、人1が最強なので、答えは0になります。
それ以外のときは、人1以外の最大のプログラミング力に+1したものから人1のプログラミング力を引いたものが答えとなります。
ただし、人1以外の最大のプログラミング力が人1のプログラミング力よりも小さい場合、答えは0になります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var P = Scanner.ScanEnumerable<int>().ToArray();
var max = N > 1 ? P.Skip(1).Max() : 0;
var answer = Math.Max(max + 1 - P[0], 0);
Console.WriteLine(answer);
}
問題B
それぞれの人xについて、人xよりも強い人の数をdeg[x]としたとき、deg[x]が0となる人xが最強のプログラマー候補となります。
最強のプログラマー候補が複数人いる場合、最強となる人を特定することはできないので、答えは-1となります。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var deg = new int[N];
for (var i = 0; i < M; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
deg[b]++;
}
var answer = -1;
for (var i = 0; i < N; i++)
{
if (deg[i] != 0) continue;
if (answer == -1)
{
answer = i + 1;
}
else
{
Console.WriteLine(-1);
return;
}
}
Console.WriteLine(answer);
}
問題C
操作を行ったところで、Aの合計値Sumは変わらないことから、Aの平均値をAveとしたとき、各要素はFloor(Ave)もしくはCeil(Ave)にすることで、Aの最小値と最大値の差を1以下にすることができます。
そして、Ceil(Ave)になりうる値は、SumをNで割った余りM個であればいいことがわかります。
このことから、Aの大きい方からM個をCeil(Ave)、残りのN-M個をFloor(Ceil)にしたときの回数を合わせ、2で割ったものが答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
Array.Sort(A);
var sum = A.Sum();
var ave = sum / N;
var mod = sum % N;
long answer = 0;
for (var i = 0; i < N - mod; i++)
{
answer += Math.Abs(ave - A[i]);
}
for (var i = 0; i < mod; i++)
{
answer += Math.Abs(A[N - 1 - i] - (ave + 1));
}
answer = answer / 2;
Console.WriteLine(answer);
}