ABC272

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc272

問題A

コンテスト提出

C#ではLINQというIEnumerable<T>拡張メソッドを使うことで、整数型シーケンスの合計値を求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var answer = A.Sum();
    Console.WriteLine(answer);
}

問題B

コンテスト提出

i(1<=i<=M)回目の講演会にj(1<=j<=N)番目の人が参加しているかという2次元の表を構築し、全ての人aと人bの組み合わせ(1<=a<b<=N)においてともに参加している講演会が1つでもあることを判定します。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var join = new bool[M, N];
    for (var i = 0; i < M; i++)
    {
        var X = Scanner.ScanEnumerable<int>().ToArray();
        for (var j = 1; j <= X[0]; j++)
        {
            join[i, X[j] - 1] = true;
        }
    }

    var answer = true;
    for (var i = 0; i < N; i++)
    {
        for (var j = i + 1; j < N; j++)
        {
            var ok = false;
            for (var k = 0; k < M; k++)
            {
                ok |= join[k, i] && join[k, j];
            }

            answer &= ok;
        }
    }

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

問題C

コンテスト提出

異なる2要素を全探索してしまうと、時間計算量がO(N^2)となり実行時間制限に間に合いません。
2要素の和において偶数であることは、偶数+偶数であること、または奇数+奇数であることのみなので、Aを偶数と奇数にわけ、偶数が2個以上あればその最大値2つの和、奇数が2個以上あればその最大値2つの和のいずれかの最大値が答えとなります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    Array.Sort(A);
    Array.Reverse(A);
    var even = new List<long>();
    var odd = new List<long>();
    foreach (var a in A)
    {
        if (a % 2 == 0) even.Add(a);
        else odd.Add(a);
    }

    var answer = -1L;
    if (even.Count >= 2) answer = Math.Max(answer, even[0] + even[1]);
    if (odd.Count >= 2) answer = Math.Max(answer, odd[0] + odd[1]);

    Console.WriteLine(answer);
}

問題D

コンテスト提出

距離がちょうどSqrt(M)となる(i,j)の差分をあらかじめ求めておき、(1,1)から差分の幅優先探索をおこなうことで答えを求めることができます。 距離がちょうどSqrt(M)となるには、(i-k)^2 + (j-i)^2 == Mとなる必要があり、i=0,j=0としたときにkまたはlを固定することによって、lまたはkを求めることができます。 ``

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();

    var root = new Dictionary<int, int>();
    for (var i = 0; i * i <= M; i++)
    {
        root[i * i] = i;
    }

    var delta = new HashSet<(int, int)>();

    void Add(int dh, int dw)
    {
        if (dh * dh + dw * dw == M && !delta.Contains((dh, dw)))
        {
            delta.Add((dh, dw));
        }
    }

    // (i, j) = (0, 0)
    for (var k = 0; k < N; k++)
    {
        var dh = (0 - k);
        var dw2 = M - (dh * dh);
        if (dw2 < 0) break;
        if (root.ContainsKey(dw2))
        {
            var dw = root[dw2];
            // l = dw - j or j - dw
            Add(k, dw - 0);
            Add(k, 0 - dw);
            Add(dw - 0, k);
            Add(0 - dw, k);
        }
    }

    var dp = new long[N, N];
    const long inf = (long)1e18;
    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j < N; j++)
        {
            dp[i, j] = inf;
        }
    }

    dp[0, 0] = 0;
    var queue = new Queue<(int, int)>();
    queue.Enqueue((0, 0));
    while (queue.Count > 0)
    {
        var (i, j) = queue.Dequeue();
        foreach (var (dh, dw) in delta)
        {
            var (k, l) = (i + dh, j + dw);
            if (0 <= k && k < N && 0 <= l && l < N && dp[k, l] == inf)
            {
                dp[k, l] = dp[i, j] + 1;
                queue.Enqueue((k, l));
            }
        }
    }

    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j < N; j++)
        {
            if (dp[i, j] == inf) dp[i, j] = -1;
        }
    }

    Printer.Print2D(dp, " ");
}