ABC239

Published on Saturday, 19 February 2022

Updated on Sunday, 20 February 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc239

問題A

コンテスト提出

与えられた計算式に入力のHを与えたときの答えを求めます。 intだとx * (12800000 + x)の計算でオーバーフローしてしまうので、longで取ることに注意します。

public static void Solve()
{
    var H = Scanner.Scan<long>();
    double F(long x) => Math.Sqrt(x * (12800000 + x));
    Console.WriteLine(F(H));
}

問題B

コンテスト提出

X>=0のときはそのままX/10で切り捨てを求め、X<0のときは-X/10の切り上げた数の-を考えればいいです。

public static void Solve()
{
    var X = Scanner.Scan<long>();
    var answer = X >= 0 ? X / 10 : -(-X + 9) / 10;
    Console.WriteLine(answer);
}

問題C

コンテスト提出

一つの点に対して、abs(dx)+abs(dy)==3となる格子点は8つのみであり、それぞれの点の組み合わせのうち、一致する点があるかを全探索します。

public static void Solve()
{
    var (x1, y1, x2, y2) = Scanner.Scan<long, long, long, long>();

    var D = new[] { (-2, 1), (-2, -1), (-1, 2), (-1, -2), (1, 2), (1, -2), (2, 1), (2, -1) };
    var answer = false;
    foreach (var (dx1, dy1) in D)
    {
        var (xx1, yy1) = (x1 + dx1, y1 + dy1);
        foreach (var (dx2, dy2) in D)
        {
            var (xx2, yy2) = (x2 + dx2, y2 + dy2);
            answer |= xx1 == xx2 && yy1 == yy2;
        }
    }

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

問題D

コンテスト提出

200までの素数を作ることができるかを考えると、{200以下の任意の素数}-{高橋君の選んだ素数}となる整数を青木君は選ぶことで素数を作ることができます。そのため、高橋君の整数を固定し、200以下の素数をすべて見たときに青木君が選ぶことのできる整数が存在するかを判定します。もし青木君が素数を作るための整数を1つでも選ぶことができなければ、高橋君の勝利となります。

public static void Solve()
{
    var (A, B, C, D) = Scanner.Scan<int, int, int, int>();
    var P = Prime.Sieve(200);
    var answer = false;
    for (var i = A; i <= B; i++)
    {
        var exist = false;
        foreach (var p in P)
        {
            var j = p - i;
            exist |= C <= j && j <= D;
        }

        answer |= !exist;
    }
    Console.WriteLine(answer ? "Takahashi" : "Aoki");
}

Prime.Sieve(200)は、与えられた数以下の素数群を返す関数です。

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;
        }
    }
}

クエリごとに部分木を計算すると、計算量がO(N^2)でになってしまうので、あらかじめ部分木のうちで対象となりうる要素を保持しておくことを考えます。しかし、部分木のすべての数を保持してしまうと、全体で最悪N*(N-1)/2個の要素が存在し、ソートも考えると計算量がO(N^2log(N^2))でTLEになってしまうので、保持する要素を制限することを考えます。制約の、1 <= Ki <= 20から、各頂点で対象となる数は、最大でも20個ということがわかります。また、木Bが木Aの部分木のとき、木Bの大きいほうから21番目以降の要素は、木Aにおいても21番目以降であるため、21番目以降の要素は無視することができます。このことから、深さ優先探索を行って部分木を見たときに、部分木の要素のうち、降順で最大20個ずつ保持して行くことで、計算量をO(Nlog(N))に抑えることができ、各クエリ当たりO(1)で答えを求めることができます。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var X = Scanner.ScanEnumerable<int>().ToArray();
    var G = new List<int>[N].Select(x => new List<int>()).ToArray();
    for (var i = 0; i < N - 1; i++)
    {
        var (a, b) = Scanner.Scan<int, int>();
        a--; b--;
        G[a].Add(b);
        G[b].Add(a);
    }

    var list = new List<int>[N].Select(_ => new List<int>()).ToArray();

    void Dfs(int u, int p)
    {
        foreach (var v in G[u])
        {
            if (v == p) continue;
            Dfs(v, u);
            foreach (var x in list[v])
            {
                list[u].Add(x);
            }
        }

        list[u].Add(X[u]);
        list[u].Sort();
        list[u].Reverse();
        list[u] = list[u].Take(20).ToList();
    }

    Dfs(0, -1);

    for (var i = 0; i < Q; i++)
    {
        var (v, k) = Scanner.Scan<int, int>();
        v--; k--;
        Console.WriteLine(list[v][k]);
    }
}

問題F

復習提出

コンテスト中の考察です。

N-1本の高速道路なら、Dの合計が(N-1)*2以外は-1になりそう。
連結じゃないところを優先して繋げる?
連結成分ごとのDの合計が多いところを優先して繋げる?

解説でも同様の考え方でした。

連結させた場合にDが変化するからPriorityQueueでDの合計が多い物を優先する。
連結したものは一つのqueueにまとめる。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var D = Scanner.ScanEnumerable<long>().ToArray();
    if (D.Sum() != (N - 1) * 2)
    {
        Console.WriteLine(-1);
        return;
    }

    var dsu = new DisjointSetUnion(N);
    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);
        dsu.Merge(a, b);
        D[a]--;
        D[b]--;
    }

    var answers = new List<(int, int)>();
    var queue = new PriorityQueue<(Queue<int> U, long M)>((x, y) => y.M.CompareTo(x.M));
    foreach (var group in dsu.GetGroups())
    {
        var q = new Queue<int>(group.Where(x => D[x] > 0));
        var s = group.Sum(x => D[x]);
        if (q.Count == 0)
        {
            Console.WriteLine(-1);
            return;
        }

        queue.Enqueue((q, s));
    }

    while (queue.Count >= 2)
    {
        var (uq, us) = queue.Dequeue();
        var (vq, vs) = queue.Dequeue();
        var u = uq.Dequeue();
        var v = vq.Dequeue();
        D[u]--;
        D[v]--;
        us--;
        vs--;
        dsu.Merge(u, v);
        answers.Add((u + 1, v + 1));
        if (D[u] > 0) uq.Enqueue(u);
        if (D[v] > 0) vq.Enqueue(v);

        if (us >= vs)
        {
            while (vq.Count > 0) uq.Enqueue(vq.Dequeue());
            us += vs;
            queue.Enqueue((uq, us));
        }
        else
        {
            while (uq.Count > 0) vq.Enqueue(uq.Dequeue());
            vs += us;
            queue.Enqueue((vq, vs));
        }
    }

    for (var i = 0; i < N; i++)
    {
        for (var j = i + 1; j < N; j++)
        {
            if (D[i] == 0) break;
            if (D[j] == 0) continue;
            D[i]--;
            D[j]--;
            answers.Add((i + 1, j + 1));
        }
    }

    if (D.Any(x => x != 0))
    {
        Console.WriteLine(-1);
        return;
    }

    foreach (var (u, v) in answers)
    {
        Console.WriteLine($"{u} {v}");
    }
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E

問題F