はじめに
AtCoder Beginner Contest 288の復習記事です。
記事におけるScanner
クラスは、自作の入力クラスです。
コンテスト
https://atcoder.jp/contests/abc288
問題A
各クエリに対してA+B
の答えを出力します。
public static void Solve()
{
var N = Scanner.Scan<int>();
for (var i = 0; i < N; i++)
{
var (A, B) = Scanner.Scan<long, long>();
var answer = A + B;
Console.WriteLine(answer);
}
}
問題B
上位K
人のみ取得し、辞書順にソートしたものを出力します。
C#では、文字列の配列に対して、Array.Sort
メソッドを使うことでソートすることができます。
public static void Solve()
{
var (N, K) = Scanner.Scan<int, int>();
var S = new string[K];
for (var i = 0; i < K; i++)
{
S[i] = Scanner.Scan<string>();
}
Array.Sort(S);
Console.WriteLine(string.Join(Environment.NewLine, S));
}
問題C
頂点A
と頂点B
が同じ連結成分である場合、A
とB
に辺を追加してしまうと閉路ができてしまいます。
そのため、DisjointSetUnion
などのデータ構造を使い、辺をつなごうとする頂点同士が同じ連結成分であるかを判定し、同じ連結成分であればその辺を削除します。
public static void Solve()
{
var (N, M) = Scanner.Scan<int, int>();
var dsu = new DisjointSetUnion(N);
var answer = 0;
for (var i = 0; i < M; i++)
{
var (a, b) = Scanner.Scan<int, int>();
a--; b--;
if (dsu.IsSame(a, b)) answer++;
dsu.Merge(a, b);
}
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);
}
}
問題D
まだ解けてません;;