はじめに
AtCoder Beginner Contest 350の復習記事です。
記事における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/abc350
問題A
1以上350未満かつ316以外のコンテストが対象となるコンテストになります。
例
public static void Solve()
{
var S = Scanner.Scan<string>();
var n = int.Parse(S[3..]);
var answer = 1 <= n && n < 350 && n != 316;
Console.WriteLine(answer ? "Yes" : "No");
}
問題B
例
E[i]をi番目の歯が生えているかをboolとして持ちます。
E[T[i]]を順番に反転させ、最終的にEのtrueの数が答えになります。
public static void Solve()
{
var (N, Q) = Scanner.Scan<int, int>();
var T = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
var E = new bool[N];
Array.Fill(E, true);
foreach (var t in T)
{
E[t] = !E[t];
}
var answer = E.Count(x => x);
Console.WriteLine(answer);
}
問題C
index[x]をAにおけるxの位置とします。
あらかじめ各index[A[i]]を求めておき、左から順番にA[i]==iであるかを判定していきます。
A[i]!=iのとき、iの値はAのj=index[i]番目にあるので、A[i]とA[j]を入れ替えます。
例
public static void Solve()
{
var N = Scanner.Scan<int>();
var A = Scanner.ScanEnumerable<int>().Select(x => x - 1).ToArray();
var index = new int[N];
for (var i = 0; i < N; i++)
{
index[A[i]] = i;
}
var answers = new List<(int A, int B)>();
for (var i = 0; i < N; i++)
{
if (A[i] == i) continue;
var j = index[i];
(index[A[i]], index[A[j]]) = (index[A[j]], index[A[i]]);
(A[i], A[j]) = (A[j], A[i]);
answers.Add((i + 1, j + 1));
}
Console.WriteLine(answers.Count);
Console.WriteLine(string.Join(Environment.NewLine, answers.Select(x => $"{x.A} {x.B}")));
}
問題D
各連結成分ごとに2組のユーザの組み合わせを数え上げ、既に友達になっているM組を引いたものが答えになります。
例
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var dsu = new DisjointSetUnion(N);
for (var i = 0; i < M; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
dsu.Merge(a, b);
}
long answer = 0;
foreach (var group in dsu.GetGroups())
{
var c = (long)group.Count;
answer += c * (c - 1) / 2;
}
answer -= M;
Console.WriteLine(answer);
}
public class DisjointSetUnion
{
public int Length { get; }
private readonly int[] _parentOrSize;
public DisjointSetUnion(int length)
{
if (length < 0) throw new ArgumentOutOfRangeException(nameof(length));
Length = length;
_parentOrSize = new int[Length];
Array.Fill(_parentOrSize, -1);
}
public int Merge(int u, int v)
{
if (u < 0 || Length <= u) throw new ArgumentOutOfRangeException(nameof(u));
if (v < 0 || Length <= v) throw new ArgumentOutOfRangeException(nameof(v));
var (x, y) = (LeaderOf(u), LeaderOf(v));
if (x == y) return x;
if (-_parentOrSize[x] < -_parentOrSize[y]) (x, y) = (y, x);
_parentOrSize[x] += _parentOrSize[y];
_parentOrSize[y] = x;
return x;
}
public bool IsSame(int u, int v)
{
if (u < 0 || Length <= u) throw new ArgumentOutOfRangeException(nameof(u));
if (v < 0 || Length <= v) throw new ArgumentOutOfRangeException(nameof(v));
return LeaderOf(u) == LeaderOf(v);
}
public int LeaderOf(int v)
{
if (v < 0 || Length <= v) throw new ArgumentOutOfRangeException(nameof(v));
if (_parentOrSize[v] < 0) return v;
return _parentOrSize[v] = LeaderOf(_parentOrSize[v]);
}
public int SizeOf(int v)
{
if (v < 0 || Length <= v) throw new ArgumentOutOfRangeException(nameof(v));
return -_parentOrSize[LeaderOf(v)];
}
public IEnumerable<IReadOnlyCollection<int>> GetGroups()
{
var result = new List<int>[Length].Select(x => new List<int>()).ToArray();
for (var i = 0; i < Length; i++) result[LeaderOf(i)].Add(i);
return result.Where(x => x.Count > 0);
}
}