ABC284

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc284

問題A

コンテスト提出

文字列を配列に受け取り、その配列を逆順にしたものを出力します。 インデックスを逆順に参照したり、IEnumerable<T>のReverse()で逆順にしたものを得ることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = new string[N];
    for (var i = 0; i < N; i++)
    {
        S[i] = Scanner.Scan<string>();
    }

    Console.WriteLine(string.Join(Environment.NewLine, S.Reverse()));
}

問題B

コンテスト提出

Aのうち奇数(2で割ったとき1余るもの)の個数を数え上げます。

public static void Solve()
{
    var T = Scanner.Scan<int>();
    while (T-- > 0)
    {
        var N = Scanner.Scan<int>();
        var A = Scanner.ScanEnumerable<int>().ToArray();
        var answer = A.Count(x => x % 2 == 1);
        Console.WriteLine(answer);
    }
}

問題C

コンテスト提出

始点を順に決めて幅優先探索を行ったり、DisjointSetUnion等のデータ構造を用いることで連結集合の個数を求めることができます。

始点を順に決めて幅優先探索する方法

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

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

    Console.WriteLine(answer);
}

DisjointSetUnionを使う方法

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var dsu = new DisjointSetUnion(N);
    for (var i = 0; i < M; i++)
    {
        var (u, v) = Scanner.Scan<int, int>();
        u--; v--;
        dsu.Merge(u, v);
    }

    var answer = dsu.GetGroups().Count();
    Console.WriteLine(answer);
}

問題D

コンテスト提出

ある素数aでNを割り切れる場合、aがpのときとaがqの二通りの可能性があります。 p==aの場合、つまりN/p%p==0の場合はq=N/p/pとなります。 q==aの場合、つまりN/q==p*pの場合はp=Sqrt(N/q)となります。

public static void Solve()
{
    var T = Scanner.Scan<int>();
    var primes = Prime.Sieve((int)3e7).Select(x => (long)x).ToArray();
    while (T-- > 0)
    {
        var N = Scanner.Scan<long>();
        foreach (var p in primes)
        {
            if (N % p != 0) continue;
            var n = N / p;
            if (n % p == 0)
            {
                var q = n / p;
                Console.WriteLine($"{p} {q}");
            }
            else
            {
                bool F(long x) => x * x <= n;
                var q = BinarySearch((long)3e9, 1, F);
                Console.WriteLine($"{q} {p}");
            }

            break;
        }
    }
}

public static long BinarySearch(long ng, long ok, Func<long, bool> func)
{
    while (Math.Abs(ok - ng) > 1)
    {
        var m = (ok + ng) / 2;
        if (func(m)) ok = m;
        else ng = m;
    }

    return ok;
}

public static class Prime
{
    public static IEnumerable<int> Sieve(int value)
    {
        if (value < 2) yield break;
        yield return 2;
        var sieve = new bool[(value + 1) / 2];
        for (var i = 1; i < sieve.Length; i++)
        {
            if (sieve[i]) continue;
            yield return i * 2 + 1;
            for (var j = i; j < sieve.Length; j += i * 2 + 1) sieve[j] = true;
        }
    }
}

問題E

コンテスト提出

行きがけ順で深さ優先探索を行い、パスを数え上げることで答えを求めることができます。 答えの上限は1e6なので、答えがそれ以上になる場合はその時点で深さ優先探索を打ち切ることで実行時間制限に間に合わせることができます。

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);
        G[v].Add(u);
    }

    const int inf = (int)1e6;

    var used = new bool[N];
    used[0] = true;
    var answer = 0;

    void Dfs(int u)
    {
        answer++;
        if (answer >= inf) return;
        foreach (var v in G[u])
        {
            if (used[v]) continue;
            used[v] = true;
            Dfs(v);
            used[v] = false;
        }
    }

    Dfs(0);
    answer = Math.Min(answer, inf);
    Console.WriteLine(answer);
}