はじめに
AtCoder Beginner Contest 323の復習記事です。
記事における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/abc323
問題A
偶数番目は0-indexedで奇数番目となり、それらが0であるかを判定します。
public static void Solve()
{
var S = Scanner.Scan<string>();
var answer = true;
for (var i = 1; i < 16; i += 2)
{
answer &= S[i] == '0';
}
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
i番目の人の番号と勝利数をペアとしたとき、勝利数を降順、番号を昇順に並べ替えたものが答えとなります。
public static void Solve()
{
var N = Scanner.Scan<int>();
var G = new char[N][];
for (var i = 0; i < N; i++)
{
G[i] = Scanner.Scan<string>().ToCharArray();
}
var answer = new (int ID, int C)[N];
for (var i = 0; i < N; i++)
{
answer[i] = (i, G[i].Count(x => x == 'o'));
}
Console.WriteLine(string.Join(" ", answer.OrderByDescending(x => x.C).ThenBy(x => x.ID).Select(x => x.ID + 1)));
}
問題C
i番目の人がまだ解いていない問題のうち、スコアが高い問題から順に、現在の総合得点の最大より高くなるまで解くことで条件を達成できます。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var A = Scanner.ScanEnumerable<long>().ToArray();
var scores = new long[N];
var queues = new PriorityQueue<long, long>[N];
long max = 0;
for (var i = 0; i < N; i++)
{
var S = Scanner.Scan<string>();
queues[i] = new PriorityQueue<long, long>();
long score = i + 1;
for (var j = 0; j < M; j++)
{
if (S[j] == 'o') score += A[j];
else queues[i].Enqueue(A[j], -A[j]);
}
scores[i] = score;
max = Math.Max(max, score);
}
for (var i = 0; i < N; i++)
{
var answer = 0;
while (queues[i].Count > 0 && scores[i] < max)
{
answer++;
scores[i] += queues[i].Dequeue();
}
Console.WriteLine(answer);
}
}
問題D
スライムの大きさが小さくなることはないので、大きさが小さいものから順にスライムを合成させていくことで、スライムの引数を最小にすることができます。
この操作は、辞書と優先度付きキューなどを使うことで達成することができます。
public static void Solve()
{
var N = Scanner.Scan<int>();
var dict = new Dictionary<long, long>();
var queue = new PriorityQueue<long, long>();
for (var i = 0; i < N; i++)
{
var (s, c) = Scanner.Scan<long, long>();
if (!dict.ContainsKey(s)) dict[s] = 0;
dict[s] += c;
queue.Enqueue(s, s);
}
while (queue.Count > 0)
{
var s = queue.Dequeue();
var c = dict[s];
var ns = s * 2;
var nc = c / 2;
if (nc > 0)
{
if (!dict.ContainsKey(ns)) dict[ns] = 0;
dict[ns] += nc;
dict[s] -= nc * 2;
queue.Enqueue(ns, ns);
}
}
var answer = dict.Values.Sum();
Console.WriteLine(answer);
}
問題E
P[t]をt秒に曲が切り替わる確率とします。
(X+0.5)秒後に曲1が再生されている確率は、X秒以前に曲1に切り替わりX+1秒以降に曲1が再生されている確率であり、これはt<=X<t+T[1]となるP[t]に曲1が再生される確率1/Nを掛けたものの総和になります。
よって、Sum(P[t], X-T[1]+1<=t<=X) / Nが答えとなります。
各P[t]は次のように求めることができます。
P[0] = 1
P[t+T[i]] = P[t]/N (0<=t<=X, 1<=i<=N)
public static void Solve()
{
var (N, X) = Scanner.Scan<int, int>();
var T = Scanner.ScanEnumerable<int>().ToArray();
var P = new mint[X + 1];
P[0] = 1;
var pN = (mint)1 / N;
for (var i = 0; i <= X; i++)
{
for (var j = 0; j < N; j++)
{
if (i + T[j] <= X) P[i + T[j]] += P[i] * pN;
}
}
mint answer = 0;
for (var i = Math.Max(0, X - T[0] + 1); i <= X; i++)
{
answer += P[i] * pN;
}
Console.WriteLine(answer);
}