ABC304

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc304

問題A

コンテスト提出

A[i]が最も小さい番号の人の順番をk (0-indexed)としたとき、i番目に出力すべき人は(k+i-1)%N番の人となります。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var S = new string[N];
    var A = new int[N];
    var first = -1;
    const int Inf = (int)1e9;
    var min = Inf;
    for (var i = 0; i < N; i++)
    {
        var (s, a) = Scanner.Scan<string, int>();
        S[i] = s;
        A[i] = a;
        if (a < min)
        {
            min = a;
            first = i;
        }
    }

    for (var i = 0; i < N; i++)
    {
        Console.WriteLine(S[(first + i) % N]);
    }
}

問題B

コンテスト提出

NがM桁の数値であるとき、下位Max(0,M-3)桁を切り捨てたものが答えとなります。 そのため、K=Max(0,M-3)としたとき、Floor(N/K)*Kが答えとなります。

public static void Solve()
{
    var N = Scanner.Scan<long>();
    var M = N.ToString().Length - 3;
    var k = 1;
    for (var i = 0; i < M; i++)
    {
        k *= 10;
    }

    Console.WriteLine(N / k * k);
}

問題C

コンテスト提出

各番号の人を頂点としたBFSを行います。 遷移できるかの判定において、距離の2乗で判定を行うことで、浮動小数点による誤差を無視して判定することができます。

public static void Solve()
{
    var (N, D) = Scanner.Scan<int, int>();
    var P = new (int X, int Y)[N];
    for (var i = 0; i < N; i++)
    {
        var (x, y) = Scanner.Scan<int, int>();
        P[i] = (x, y);
    }

    var used = new bool[N];
    used[0] = true;
    var queue = new Queue<int>();
    queue.Enqueue(0);
    var D2 = D * D;
    while (queue.Count > 0)
    {
        var u = queue.Dequeue();
        for (var v = 0; v < N; v++)
        {
            if (used[v]) continue;
            var (dx, dy) = (P[u].X - P[v].X, P[u].Y - P[v].Y);
            var d = dx * dx + dy * dy;
            if (d <= D2)
            {
                used[v] = true;
                queue.Enqueue(v);
            }
        }
    }

    Console.WriteLine(string.Join(Environment.NewLine, used.Select(x => x ? "Yes" : "No")));
}

問題D

コンテスト提出

分割されたケーキのピースをそれぞれ、横i (1<=i<=A+1)番目、縦j (1<=j<=B+1)番目のピースとし、それぞれのピースにイチゴが何個乗っているかを数え上げます。

このとき、イチゴがどのピースに乗っているかを二次元配列で管理してしまうと、計算量がO((A+1)(B+1))になってしまいますが、イチゴの数は高々N個なので、ピース(i,j)をキーとする辞書などのデータ構造を使うことで、計算量をO(log(N))に抑えて管理することができます。

また、イチゴがどの位置のピースに乗っているかについて、愚直に探索してしまうと、イチゴごとに時間計算量O(A+B)かかりますが、二部探索をおこなうことで時間計算量O(logA+logB)に抑えることができます。
これにより、イチゴがあるピースにおける最小値と最大値を求めることができます。 しかし、この最小値はイチゴがないピースは対象としていないため、イチゴがないピースが存在した場合は最小は0となります。
これは、(i,j)の組み合わせのピースを全て走査することで判定することができますが、イチゴの数はN個なので、Min(N+1,(A+1)(B+1))個の組み合わせを調べるだけで、イチゴがないピースが存在するかを判定することができます。

public static void Solve()
{
    var (W, H) = Scanner.Scan<int, int>();
    var N = Scanner.Scan<int>();
    var Berries = new (int X, int Y)[N];
    for (var i = 0; i < N; i++)
    {
        var (x, y) = Scanner.Scan<int, int>();
        Berries[i] = (x, y);
    }
    var AN = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToList();
    var BN = Scanner.Scan<int>();
    var B = Scanner.ScanEnumerable<int>().ToList();
    A.Insert(0, 0);
    B.Insert(0, 0);

    var dict = new Dictionary<(int, int), int>();
    foreach (var (x, y) in Berries)
    {
        var i = LowerBound(A, x);
        var j = LowerBound(B, y);
        if (!dict.ContainsKey((i, j))) dict[(i, j)] = 0;
        dict[(i, j)]++;
    }

    const int Inf = (int)1e9;
    var min = Inf;
    var max = 0;
    foreach (var v in dict.Values)
    {
        min = Math.Min(min, v);
        max = Math.Max(max, v);
    }

    var ok = false;
    for (var i = 1; i <= AN + 1 && !ok; i++)
    {
        for (var j = 1; j <= BN + 1 && !ok; j++)
        {
            if (!dict.ContainsKey((i, j)))
            {
                min = 0;
                ok = true;
            }
        }
    }

    Console.WriteLine($"{min} {max}");
}

問題E

コンテスト提出

G上で頂点xと頂点yを結ぶパスが存在しないということは、x、yが属する連結成分をgx、gyとしたとき、gxとgyが別の連結成分であることが良いグラフである条件になります。
このことから、gxとgyを接続する辺を追加したときは、Gは良いグラフではなくなります。
そのため、連結成分ごとに互いに接続してはいけない連結成分を管理し、クエリごとにp、qが互いに接続してはいけない連結成分に属していないかを判定することで答えを求めることができます。
各頂点がどの連結成分に属しているかは、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 K = Scanner.Scan<int>();
    var dict = new Dictionary<int, HashSet<int>>();
    for (var i = 0; i < K; i++)
    {
        var (x, y) = Scanner.Scan<int, int>();
        x--; y--;
        var xl = dsu.LeaderOf(x);
        var yl = dsu.LeaderOf(y);
        if (!dict.ContainsKey(xl)) dict[xl] = new HashSet<int>();
        if (!dict.ContainsKey(yl)) dict[yl] = new HashSet<int>();
        dict[xl].Add(yl);
        dict[yl].Add(xl);
    }

    var Q = Scanner.Scan<int>();
    for (var i = 0; i < Q; i++)
    {
        var (p, q) = Scanner.Scan<int, int>();
        p--; q--;
        var pl = dsu.LeaderOf(p);
        var ql = dsu.LeaderOf(q);
        var answer = true;
        if (dict.ContainsKey(pl)) answer &= !dict[pl].Contains(ql);
        if (dict.ContainsKey(ql)) answer &= !dict[ql].Contains(pl);

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