ABC254

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc254

問題A

コンテスト提出

文字列として入力を取り、文字列の後ろ2文字を表示します。

public static void Solve()
{
    var N = Scanner.Scan<string>();
    var answer = N[^2..];
    Console.WriteLine(answer);
}

問題B

コンテスト提出

問題文に沿って実装をします。 これはパスカルの三角形、二項係数を表します。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var nCk = new long[N, N];
    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j <= i; j++)
        {
            if (j == 0 || j == i) nCk[i, j] = 1;
            else nCk[i, j] = nCk[i - 1, j - 1] + nCk[i - 1, j];
        }
    }

    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j <= i; j++)
        {
            Console.Write(nCk[i, j]);
            Console.Write(j == i ? '\n' : ' ');
        }
    }
}

問題C

コンテスト提出

A[i]が入れ替え可能な位置として、A[i+K]やA[i+k*2]のようにi+Kの倍数の何れかの値と入れ替えることができることがわかります。 そのため、i%K番目のグループごとに値をソートし、数列Bのi番目にi%K番目のグループのi/K番目の値を復元してできたものが、Aをソートしたものと一致かを判定します。

A = [3, 4, 1, 3, 4]
G[0] = [3, 1, 4] -> [1, 3, 4]
G[1] = [4, 3] -> [3, 4]
B = [1, 3, 3, 4, 4]

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

    for (var i = 0; i < K; i++)
    {
        G[i].Sort();
    }

    var B = new List<int>();
    for (var i = 0; i < N; i++)
    {
        B.Add(G[i % K][i / K]);
    }

    var C = A.OrderBy(x => x).ToArray();
    var answer = true;
    for (var i = 0; i < N; i++)
    {
        answer &= B[i] == C[i];
    }

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

問題D

復習提出

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var sq = new bool[N + 1];
    for (var i = 1; i * i <= N; i++)
    {
        sq[i * i] = true;
    }

    var count = new long[N + 1];
    for (var i = 1; i <= N; i++)
    {
        long j = 0;
        foreach (var d in GetDivisors(i))
        {
            if (sq[d]) j = Math.Max(j, d);
        }

        count[i / j]++;
    }

    var answer = 0L;
    for (var i = 1; i <= N; i++)
    {
        answer += count[i] * count[i];
    }

    Console.WriteLine(answer);
}

問題E

コンテスト提出

各クエリに対して、全ての頂点をメモしてDFSやBFSをしてしまうと、時間計算量がO(QM)となってしまい、実行時間制限に間に合いません。 しかし、制約にグラフの各頂点の時数は3以下であり、0<=k<=3とあることから、クエリあたり最大でも距離が0から3の頂点の和1+3^1+3^2+3^3=1+3+9+27=40しかないことがわかります。 そのため、訪れた頂点のみをHashSetなどで管理することで、実行時間制限に間に合わせることができます。

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 (a, b) = Scanner.Scan<int, int>();
        a--; b--;
        G[a].Add(b);
        G[b].Add(a);
    }

    var Q = Scanner.Scan<int>();
    while (Q-- > 0)
    {
        var (x, k) = Scanner.Scan<int, int>();
        x--;
        var set = new HashSet<long>();
        var queue = new Queue<(int, int)>();
        set.Add(x);
        queue.Enqueue((x, 0));
        while (queue.Count > 0)
        {
            var (u, d) = queue.Dequeue();
            if (d == k) continue;
            foreach (var v in G[u])
            {
                if (set.Contains(v)) continue;
                set.Add(v);
                queue.Enqueue((v, d + 1));
            }
        }

        var answer = set.Sum() + set.Count;
        Console.WriteLine(answer);
    }
}