ABC302

Published on
Updated on
atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc302

問題A

コンテスト提出

Ceil(A/B)が答えになるので、(A+B-1)/Bで切り上げた値を得ることができます。
また、double型などの浮動小数点型だと、精度の問題で正しい値を求めることができないことがあります。

public static void Solve()
{
    var (A, B) = Scanner.Scan<long, long>();
    var answer = (A + B - 1) / B;
    Console.WriteLine(answer);
}

問題B

コンテスト提出

snuke文字列の始点のマスの位置を(ch,cw)、snuke文字列が続く方向を(dh,dw)とすると、snuke文字列のk文字目は(ch+dh*k,cw+dw*k)の位置のマスになります。この位置のマスがグリッド上にあり、5文字全て一致している場合、始点から順に出力することで答えを得ることができます。

public static void Solve()
{
    var (H, W) = Scanner.Scan<int, int>();
    var S = new char[H][];
    const string Snuke = "snuke";

    for (var i = 0; i < H; i++)
    {
        S[i] = Scanner.Scan<string>().ToCharArray();
    }

    for (var ch = 0; ch < H; ch++)
    {
        for (var cw = 0; cw < W; cw++)
        {
            for (var dh = -1; dh <= 1; dh++)
            {
                for (var dw = -1; dw <= 1; dw++)
                {
                    var ok = true;
                    for (var k = 0; k < 5 && ok; k++)
                    {
                        var nh = ch + dh * k;
                        var nw = cw + dw * k;
                        if (nh < 0 || nh >= H || nw < 0 || nw >= W)
                        {
                            ok = false;
                            break;
                        }

                        ok &= S[nh][nw] == Snuke[k];
                    }

                    if (ok)
                    {
                        for (var k = 0; k < 5; k++)
                        {
                            Console.WriteLine($"{ch + 1 + dh * k} {cw + 1 + dw * k}");
                        }
                        return;
                    }
                }
            }
        }
    }
}

問題C

コンテスト提出

N個の文字列の順列を全探索し、いずれかの場合において条件を満たすことができるかを判定します。

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

    foreach (var perm in Permute(Enumerable.Range(0, N)))
    {
        var answer = true;
        for (var k = 0; k + 1 < N; k++)
        {
            var curr = perm[k];
            var next = perm[k + 1];
            var diff = 0;
            for (var i = 0; i < M; i++)
            {
                if (S[curr][i] != S[next][i]) diff++;
            }

            answer &= diff == 1;
        }

        if (answer)
        {
            Console.WriteLine("Yes");
            return;
        }
    }

    Console.WriteLine("No");
}

public static IEnumerable<T[]> Permute<T>(IEnumerable<T> source)
{
    if (source is null) throw new ArgumentNullException(nameof(source));
    IEnumerable<T[]> Inner()
    {
        var items = source.ToArray();
        var n = items.Length;
        var indices = new int[n];
        for (var i = 0; i < indices.Length; i++)
        {
            indices[i] = i;
        }
        T[] Result()
        {
            var result = new T[n];
            for (var i = 0; i < n; i++)
            {
                result[i] = items[indices[i]];
            }
            return result;
        }
        yield return Result();
        while (true)
        {
            var (i, j) = (n - 2, n - 1);
            while (i >= 0)
            {
                if (indices[i] < indices[i + 1]) break;
                i--;
            }
            if (i == -1) yield break;
            while (true)
            {
                if (indices[j] > indices[i]) break;
                j--;
            }
            (indices[i], indices[j]) = (indices[j], indices[i]);
            Array.Reverse(indices, i + 1, n - 1 - i);
            yield return Result();
        }
    }
    return Inner();
}

問題D

コンテスト提出

全ての組み合わせを考えてしまうと、時間計算量がO(NM)になり、実行時間制限に間に合いません。 Aを固定して考えたとき、A[i]に対して選ぶことができるBの最大の贈り物はA[i]+D以下のものになります。
ここで、BのうちA[i]+D以下になる最大のものをBをソートして二部探索で求めることで、各A[i]に対して時間計算量O(logM)で求めることができ、まとめると時間計算量O(NlogM)で求めることができます。 同様に、Bを固定して考えたとき、時間計算量O(MlogN)で求めることができるため、全体時間計算量はO(NlogM+MlogN)となります。

public static void Solve()
{
    var (N, M, D) = Scanner.Scan<int, int, long>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    var B = Scanner.ScanEnumerable<long>().ToArray();

    Array.Sort(A);
    Array.Sort(B);
    long answer = -1;

    for (var i = 0; i < N; i++)
    {
        var a = A[i];
        var j = Math.Max(0, UpperBound(B, a + D) - 1);
        var b = B[j];
        if (Math.Abs(a - b) <= D)
        {
            answer = Math.Max(answer, a + b);
        }
    }

    for (var i = 0; i < M; i++)
    {
        var b = B[i];
        var j = Math.Max(0, UpperBound(A, b + D) - 1);
        var a = A[j];
        if (Math.Abs(b - a) <= D)
        {
            answer = Math.Max(answer, b + a);
        }
    }

    Console.WriteLine(answer);
}

public static int UpperBound<T>(ReadOnlySpan<T> source, T key) where T : IComparable<T>
{
    var (l, r) = (-1, source.Length);
    while (r - l > 1)
    {
        var m = l + (r - l) / 2;
        if (source[m].CompareTo(key) > 0) r = m;
        else l = m;
    }

    return r;
}

問題E

コンテスト提出

頂点ごとに辺で結ばれている頂点の集合を管理しながら、クエリごとにシミュレートを行います。
「他のどの頂点とも辺で結ばれていない頂点」の数をanswerとします。 初期状態として、answerはNになります。

1番のクエリについて、頂点uがその時点でほかのどの頂点とも辺で結ばれていない場合、頂点vと辺で結ばれるため、answerは-1されます。 同様に、頂点vの場合も、その時点でほかのどの頂点とも辺で結ばれていない場合、頂点uと辺で結ばれるため、answerは-1されます。

2番のクエリについて、頂点vがその時点でいずれかの頂点と辺で結ばれている場合、answerは+1されます。 また、頂点vと辺で結ばれている各頂点について、その頂点の辺で結ばれている頂点集合から頂点vを削除した後、その頂点の辺で結ばれている頂点が存在しない場合、answerは+1されます。 その後、頂点vの辺で結ばれている頂点の集合をすべて削除します。

辺で結ばれている頂点の集合をHashSetなどのデータ構造を用いることで、追加と削除を時間計算量O(1)で行うことができ、全体時間計算量O(Q)でシミュレートすることができます。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var connected = new HashSet<int>[N].Select(_ => new HashSet<int>()).ToArray();
    var answer = N;

    for (var i = 0; i < Q; i++)
    {
        var query = Scanner.ScanEnumerable<int>().ToArray();
        var queryType = query[0];
        var queryArgs = query.AsSpan(1);

        void QF1(ReadOnlySpan<int> queryArgs)
        {
            var (u, v) = (queryArgs[0] - 1, queryArgs[1] - 1);
            if (connected[u].Count == 0) answer--;
            if (connected[v].Count == 0) answer--;
            connected[u].Add(v);
            connected[v].Add(u);
            Console.WriteLine(answer);
        }

        void QF2(ReadOnlySpan<int> queryArgs)
        {
            var u = queryArgs[0] - 1;
            if (connected[u].Count != 0) answer++;
            foreach (var v in connected[u])
            {
                connected[v].Remove(u);
                if (connected[v].Count == 0) answer++;
            }
            connected[u].Clear();

            Console.WriteLine(answer);
        }

        switch (queryType)
        {
            case 1:
                QF1(queryArgs);
                break;
            case 2:
                QF2(queryArgs);
                break;
            default:
                break;
        }
    }
}

問題F

コンテスト提出

各集合を頂点とした幅優先探索を行います。

整数xが属する集合群をHas[x]としたとき、始点はHas[1]に属する集合群になります。 また、Has[1]に属する集合をuとしたとき、S[u]の整数集合の最小操作回数は0になります。

幅優先探索において、遷移元の集合をuとしたとき、uから遷移することができる集合群は、整数S[u][i] (1<=i<=A[u])を含む集合、つまりHas[S[u][i]]の集合群になります。 整数S[u][i]をs1、s1を含む集合をv、vに含まれる整数S[u][j] (1<=j<=A[v])をs2、整数xへの最小操作回数をcosts[x]としたとき、s2への遷移回数はMin(costs[s2],costs[s1]+1)になります。

よって、時間計算量O(N+M+Sum(A))で答えを求めることができます。

2023/05/22更新

頂点1からNを集合の番号、頂点N+1からN+Mを1からMの整数に対応させ、集合から整数、整数から集合に対してそれぞれコスト1の辺を張ったグラフを作成し、幅優先探索を行います。

集合から整数、整数から集合に対しての移動で2回の移動をしているため、答えが2倍になることに注意します。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var S = new int[N][];
    var G = new List<int>[N + M + 1].Select(x => new List<int>()).ToArray();
    for (var i = 0; i < N; i++)
    {
        _ = Scanner.Scan<int>();
        S[i] = Scanner.ScanEnumerable<int>().ToArray();
        foreach (var s in S[i])
        {
            G[i + 1].Add(N + s);
            G[N + s].Add(i + 1);
        }
    }

    var queue = new Queue<int>();
    var costs = new int[N + M + 1];
    Array.Fill(costs, -1);
    costs[N + 1] = 0;
    queue.Enqueue(N + 1);

    while (queue.Count > 0)
    {
        var u = queue.Dequeue();
        foreach (var v in G[u])
        {
            if (costs[v] != -1) continue;
            costs[v] = costs[u] + 1;
            queue.Enqueue(v);
        }
    }

    var answer = costs[N + M];
    if (answer != -1) answer = (answer - 1) / 2;
    Console.WriteLine(answer);
}