ABC292

はじめに

AtCoder Beginner Contest 292の復習記事です。

記事におけるScannerクラスは、自作の入力クラスです。

コンテスト

https://atcoder.jp/contests/abc292

問題A

コンテスト提出

string.ToUpperで文字列をすべて大文字にすることができます。

public static void Solve()
{
    var S = Scanner.Scan<string>();
    var answer = S.ToUpper();
    Console.WriteLine(answer);
}

問題B

コンテスト提出

Y[x]をその時点のxのイエローカードの数とし、レッドカードはイエローカード2枚分であるとします。 そして、各イベントについて次のような処理を行います。

• イベントが1の場合、Y[x]+=1
• イベントが2の場合、Y[x]+=2
• イベントが3の場合、Y[x]>=2ならば退場処分を受けている。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var C = new int[N];
    while (Q-- > 0)
    {
        var (e, x) = Scanner.Scan<int, int>();
        x--;
        if (e == 3)
        {
            var answer = C[x] >= 2 ? "Yes" : "No";
            Console.WriteLine(answer);
        }
        else
        {
            C[x] += e;
        }
    }
}

問題C

コンテスト提出

また、ABの値がXの場合、A*B==XとなるAとBの組み合わせの個数は、Xの約数の個数と一致します。 これは、時間計算量O(Sqrt(X))で求めることができます。 また、C(n)をnの約数の個数としたとき、X+Y=Nとなる組み合わせはC(X)*C(Y)個になります。 そして、ABの値をXとしたとき、CDの値はY=N-Xで求められるので、ABを固定することで全体計算量O(NSqrt(N))で求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var dict = new Dictionary<long, long>();

    long F(long n)
    {
        if (dict.ContainsKey(n)) return dict[n];
        long result = 0;
        for (var a = 1L; a * a <= n; a++)
        {
            if (n % a != 0) continue;
            var b = n / a;
            if (a == b) result++;
            else result += 2;
        }

        return dict[n] = result;
    }

    long answer = 0;
    for (var ab = 1; ab < N; ab++)
    {
        var cd = N - ab;
        answer += F(ab) * F(cd);
    }

    Console.WriteLine(answer);
}

問題D

コンテスト提出

DisjointSetUnionを使って、各連結成分の代表する頂点を求められるようにしておきます。 そして、連結成分の頂点の個数と辺の個数をそれぞれ各連結成分の代表にまとめ、それらを比較することで、各連結成分の頂点の個数を辺の個数が一致するかを求めることができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var G = new List<int>[N].Select(x => new List<int>()).ToArray();
    var E = new (int U, int V)[M];
    var dsu = new DisjointSetUnion(N);
    for (var i = 0; i < M; i++)
    {
        var (u, v) = Scanner.Scan<int, int>();
        u--; v--;
        E[i] = (u, v);
        dsu.Merge(u, v);
    }

    var vc = new int[N];
    for (var u = 0; u < N; u++)
    {
        vc[dsu.LeaderOf(u)]++;
    }

    var ec = new int[N];
    foreach (var (u, _) in E)
    {
        ec[dsu.LeaderOf(u)]++;
    }

    var answer = true;
    for (var u = 0; u < N; u++)
    {
        answer &= vc[u] == ec[u];
    }

    Console.WriteLine(answer ? "Yes" : "No");
}

問題E

復習提出

ある頂点を始点sとしたとき、その頂点からたどり着くことができる頂点tに対して、s->tの辺を張ることができます。 このことから、各頂点を始点としたときに、たどり着くことができる頂点を幅優先探索などで探索することで、張ることができる辺の数を求めることができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var G = new List<int>[N].Select(x => new List<int>()).ToArray();
    for (var i = 0; i < M; i++)
    {
        var (u, v) = Scanner.Scan<int, int>();
        u--; v--;
        G[u].Add(v);
    }

    var used = new bool[N];
    var queue = new Queue<int>();
    var answer = -M;
    for (var i = 0; i < N; i++)
    {
        Array.Fill(used, false);
        used[i] = true;
        queue.Enqueue(i);
        while (queue.Count > 0)
        {
            var u = queue.Dequeue();
            foreach (var v in G[u])
            {
                if (used[v]) continue;
                used[v] = true;
                answer++;
                queue.Enqueue(v);
            }
        }
    }

    Console.WriteLine(answer);
}