ABC288

はじめに

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

まだ解けてません;;