はじめに
AtCoder Beginner Contest 320の復習記事です。
記事における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/abc320
問題A
Math.Pow関数や、for文でAをB回掛けたもの、BをA回掛けたものを求め、それぞれを足したものを出力します。
public static void Solve()
{
var (A, B) = Scanner.Scan<long, long>();
var answer = Math.Pow(A, B) + Math.Pow(B, A);
Console.WriteLine(answer);
}
問題B
連続する部分文字列の両端の組み合わせi,j (i<=j)を全探索し、その部分文字列が回文であるかを判定します。
public static void Solve()
{
var S = Scanner.Scan<string>();
var N = S.Length;
var answer = 0;
for (var i = 0; i < N; i++)
{
for (var j = i; j < N; j++)
{
var ok = true;
for (var k = 0; k <= j - i && ok; k++)
{
var a = i + k;
var b = j - k;
ok &= S[a] == S[b];
}
if (ok)
{
answer = Math.Max(answer, j - i + 1);
}
}
}
Console.WriteLine(answer);
}
問題C
スロットのリールのうち、どの数字を止めるかを固定して考えます。
止める数字を固定したとき、各リールでその数字が出現する順番を全探索します。
出現する順番が一致しているリールが2つのとき、それぞれ1周目と2周目で止めることで、その数字をそろえることができます。
出現する順番が一致しているリールが3つのとき、それぞれ1周目、2週目、3週目で止めることで、その数字をそろえることができます。
public static void Solve()
{
var M = Scanner.Scan<int>();
var list = new List<int>[3][];
for (var i = 0; i < 3; i++)
{
var S = Scanner.Scan<string>().Select(x => x - '0').ToArray();
list[i] = new List<int>[10].Select(_ => new List<int>()).ToArray();
for (var j = 0; j < M; j++)
{
list[i][S[j]].Add(j);
}
}
const int Inf = (int)1e9;
var answer = Inf;
for (var k = 0; k < 10; k++)
{
foreach (var a in list[0][k])
{
foreach (var b in list[1][k])
{
foreach (var c in list[2][k])
{
var x = a;
var y = b;
var z = c;
if (x == y && y == z)
{
x += M;
y += M * 2;
}
else if (x == y)
{
y += M;
}
else if (x == z)
{
z += M;
}
else if (y == z)
{
z += M;
}
answer = Math.Min(answer, Math.Max(Math.Max(x, y), z));
}
}
}
}
if (answer == Inf) answer = -1;
Console.WriteLine(answer);
}
問題D
N個の頂点に対して、M個の情報をA[i]からB[i]へのD(X[i],Y[i])となる有向辺とB[i]からA[i]へのD(-X[i],-Y[i])となる有向辺とした、2M個の辺からなる有向グラフを構築し、人1を始点とした幅優先探索を行い、それぞれの人の座標の集合を求めます。
各人のあり得る座標の集合において、一意に定まる場合はその座標を、それ以外の場合はundecidableを出力します。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
const string Undecidable = "undecidable";
var G = new HashSet<(int, Point)>[N].Select(x => new HashSet<(int, Point)>()).ToArray();
for (var i = 0; i < M; i++)
{
var (a, b, x, y) = Scanner.Scan<int, int, long, long>();
a--; b--;
G[a].Add((b, new(x, y)));
G[b].Add((a, new(-x, -y)));
}
var P = new HashSet<Point>[N].Select(_ => new HashSet<Point>()).ToArray();
P[0].Add(new(0, 0));
var queue = new Queue<int>();
queue.Enqueue(0);
while (queue.TryDequeue(out var u))
{
var cp = P[u].First();
foreach (var (v, diff) in G[u])
{
var (dx, dy) = diff;
var np = new Point(cp.X + dx, cp.Y + dy);
if (P[v].Contains(np)) continue;
P[v].Add(np);
queue.Enqueue(v);
}
}
for (var i = 0; i < N; i++)
{
if (P[i].Count == 1)
{
var p = P[i].First();
Console.WriteLine($"{p.X} {p.Y}");
}
else
{
Console.WriteLine(Undecidable);
}
}
}
public readonly record struct Point(long X, long Y);
問題E
待機列の人を番号順に管理できる優先度付きキューと、列から離れた人の番号と帰ってくる時間を時間順に管理できる優先度付きキューを用意し、そうめんが流れてくるごとに、その時間以前の列から離れた人を待機列に追加し、待機列の先頭の人にそうめんを獲得させ、その人を列から離れさせるというシミュレーションを行います。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var leavingID = new PriorityQueue<R>((x, y) =>
{
var result = x.Time.CompareTo(y.Time);
if (result == 0) result = x.ID.CompareTo(y.ID);
return result;
});
for (var i = 0; i < N; i++)
{
leavingID.Enqueue(new R(i, 0));
}
var waitingID = new PriorityQueue<int>((x, y) => x.CompareTo(y));
var answers = new long[N];
for (var i = 0; i < M; i++)
{
var (t, w, s) = Scanner.Scan<long, long, long>();
while (leavingID.Count > 0 && leavingID.Peek().Time <= t)
{
var (id, _) = leavingID.Dequeue();
waitingID.Enqueue(id);
}
if (waitingID.Count == 0) continue;
var waited = waitingID.Dequeue();
answers[waited] += w;
var nt = t + s;
leavingID.Enqueue(new R(waited, nt));
}
Console.WriteLine(string.Join(Environment.NewLine, answers));
}
public readonly record struct R(int ID, long Time);
public class PriorityQueue<T> : IReadOnlyCollection<T>
{
private readonly Comparison<T> _comparison;
private readonly List<T> _heap;
public PriorityQueue(IEnumerable<T> items, IComparer<T> comparer = null) : this(comparer)
{
foreach (var item in items) Enqueue(item);
}
public PriorityQueue(IEnumerable<T> items, Comparison<T> comparison) : this(comparison)
{
foreach (var item in items) Enqueue(item);
}
public PriorityQueue(IComparer<T> comparer = null) : this((comparer ?? Comparer<T>.Default).Compare) { }
public PriorityQueue(Comparison<T> comparison)
{
_heap = new List<T>();
_comparison = comparison;
}
public int Count => _heap.Count;
public IEnumerator<T> GetEnumerator() => _heap.GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
public void Enqueue(T item)
{
var child = Count;
_heap.Add(item);
while (child > 0)
{
var parent = (child - 1) / 2;
if (_comparison(_heap[parent], _heap[child]) <= 0) break;
(_heap[parent], _heap[child]) = (_heap[child], _heap[parent]);
child = parent;
}
}
public T Dequeue()
{
if (Count == 0) throw new InvalidOperationException();
var result = _heap[0];
_heap[0] = _heap[Count - 1];
_heap.RemoveAt(Count - 1);
var parent = 0;
while (parent * 2 + 1 < Count)
{
var left = parent * 2 + 1;
var right = parent * 2 + 2;
if (right < Count && _comparison(_heap[left], _heap[right]) > 0)
left = right;
if (_comparison(_heap[parent], _heap[left]) <= 0) break;
(_heap[parent], _heap[left]) = (_heap[left], _heap[parent]);
parent = left;
}
return result;
}
public T Peek()
{
if (Count == 0) throw new InvalidOperationException();
return _heap[0];
}
public bool TryDequeue(out T result)
{
if (Count > 0)
{
result = Dequeue();
return true;
}
result = default;
return false;
}
public bool TryPeek(out T result)
{
if (Count > 0)
{
result = Peek();
return true;
}
result = default;
return false;
}
public void Clear() => _heap.Clear();
public bool Contains(T item) => _heap.Contains(item);
}