ABC309

Published on Saturday, 08 July 2023

Updated on Saturday, 08 July 2023

atcoder csharp

はじめに

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

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

Scannerクラス

public static class Scanner
{
    public static T Scan<T>() where T : IConvertible => Convert<T>(ScanStringArray()[0]);
    public static (T1, T2) Scan<T1, T2>() where T1 : IConvertible where T2 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]));
    }
    public static (T1, T2, T3) Scan<T1, T2, T3>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]));
    }
    public static (T1, T2, T3, T4) Scan<T1, T2, T3, T4>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]));
    }
    public static (T1, T2, T3, T4, T5) Scan<T1, T2, T3, T4, T5>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]));
    }
    public static (T1, T2, T3, T4, T5, T6) Scan<T1, T2, T3, T4, T5, T6>() where T1 : IConvertible where T2 : IConvertible where T3 : IConvertible where T4 : IConvertible where T5 : IConvertible where T6 : IConvertible
    {
        var input = ScanStringArray();
        return (Convert<T1>(input[0]), Convert<T2>(input[1]), Convert<T3>(input[2]), Convert<T4>(input[3]), Convert<T5>(input[4]), Convert<T6>(input[5]));
    }
    public static IEnumerable<T> ScanEnumerable<T>() where T : IConvertible => ScanStringArray().Select(Convert<T>);
    private static string[] ScanStringArray()
    {
        var line = Console.ReadLine()?.Trim() ?? string.Empty;
        return string.IsNullOrEmpty(line) ? Array.Empty<string>() : line.Split(' ');
    }
    private static T Convert<T>(string value) where T : IConvertible => (T)System.Convert.ChangeType(value, typeof(T));
}

コンテスト

https://atcoder.jp/contests/abc309

問題A

コンテスト提出

A<Bであることから、A+1==Bであることが条件の一つとなります。また、Aが3、6、9の場合、右に隣接するBは存在しないため、Aが3の倍数ではないときが、もう一つの条件となります。

public static void Solve()
{
    var (A, B) = Scanner.Scan<int, int>();
    var answer = A + 1 == B && (A % 3 != 0);
    Console.WriteLine(answer ? "Yes" : "No");
}

問題B

コンテスト提出

時計回りに1行目、N列目、N行目、1列目を更新していくことを考えます。
ある場所を更新するとき、その直前に更新した値がその場所に移動し、更新された値が次の場所に移動することがわかります。
このことから、直前に更新した値を保持しながら外側のマスを順番に更新していくことで、答えを得ることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = new int[N][];
    for (var i = 0; i < N; i++)
    {
        A[i] = Scanner.Scan<string>().Select(x => x - '0').ToArray();
    }

    var tmp1 = A[1][0];
    for (var i = 0; i < N; i++)
    {
        var tmp2 = A[0][i];
        A[0][i] = tmp1;
        tmp1 = tmp2;
    }

    for (var i = 1; i < N; i++)
    {
        var tmp2 = A[i][N - 1];
        A[i][N - 1] = tmp1;
        tmp1 = tmp2;
    }

    for (var i = N - 2; i >= 0; i--)
    {
        var tmp2 = A[N - 1][i];
        A[N - 1][i] = tmp1;
        tmp1 = tmp2;
    }

    for (var i = N - 2; i >= 0; i--)
    {
        var tmp2 = A[i][0];
        A[i][0] = tmp1;
        tmp1 = tmp2;
    }

    Printer.Print2D(A);
}

問題C

コンテスト提出

初日に飲む必要がある薬はbの総和となり、各a+1日目に飲む分はb錠減ることがわかります。
このことから、各a+1日目に何錠減るかをまとめ、薬が減る日が早い順に飲む必要がある薬を減らしていき、K以下になった日が答えとなります。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, long>();
    var dict = new Dictionary<long, long>();
    dict[1] = 0;
    long cum = 0;
    for (var i = 0; i < N; i++)
    {
        var (a, b) = Scanner.Scan<long, long>();
        cum += b;
        if (!dict.ContainsKey(a + 1)) dict[a + 1] = 0;
        dict[a + 1] += b;
    }


    foreach (var (a, b) in dict.OrderBy(x => x.Key))
    {
        cum -= b;
        if (cum <= K)
        {
            Console.WriteLine(a);
            return;
        }
    }
}

頂点1から頂点N1+N2への最長となる経路は、頂点1から最も遠い頂点と頂点N1+N2から最も遠い頂点間に辺を結ぶことで達成することができます。
このことから、N1個の頂点からなるグラフG1において頂点1から距離と、N2個の頂点からなるグラフG2において頂点N1+N2からの距離をそれぞれ幅優先探索などを行い求め、各距離の最大値に辺を一つ追加したものが答えとなります。

public static void Solve()
{
    var (N1, N2, M) = Scanner.Scan<int, int, int>();
    var G1 = new List<int>[N1].Select(x => new List<int>()).ToArray();
    var G2 = new List<int>[N2].Select(x => new List<int>()).ToArray();
    for (var i = 0; i < M; i++)
    {
        var (a, b) = Scanner.Scan<int, int>();
        a--; b--;
        if (a < N1)
        {
            G1[a].Add(b);
            G1[b].Add(a);
        }
        else
        {
            a -= N1;
            b -= N1;
            G2[a].Add(b);
            G2[b].Add(a);
        }
    }

    int MaxDist(List<int>[] G, int N, int s)
    {
        var dist = new int[N];
        Array.Fill(dist, -1);
        var queue = new Queue<int>();
        queue.Enqueue(s);
        dist[s] = 0;
        while (queue.Count > 0)
        {
            var u = queue.Dequeue();
            foreach (var v in G[u])
            {
                if (dist[v] != -1) continue;
                dist[v] = dist[u] + 1;
                queue.Enqueue(v);
            }
        }

        return dist.Max();
    }

    var answer = MaxDist(G1, N1, 0) + MaxDist(G2, N2, N2 - 1) + 1;
    Console.WriteLine(answer);
}

問題E

コンテスト提出

各親uから子vへの有向辺を張ったグラフをGとします。
人iからみた保証対象となる代の最大値をdp[i]、親をu、子をvとしたとき、dp[v]の最大値はMax(dp[v],dp[u]-1)になります。 P[i]<=i-1であることから、親を順に走査して子に最大値を伝播してくことで各dp[i]の値を求めることができ、dp[i]>=0となる人の数が答えとなります。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var G = new List<int>[N].Select(x => new List<int>()).ToArray();

    var P = Scanner.ScanEnumerable<int>().ToArray();
    for (var i = 0; i < P.Length; i++)
    {
        var u = P[i] - 1;
        var v = i + 1;
        G[u].Add(v);
    }

    var dp = new int[N];
    Array.Fill(dp, -1);
    for (var i = 0; i < M; i++)
    {
        var (x, y) = Scanner.Scan<int, int>();
        x--;
        dp[x] = Math.Max(dp[x], y);
    }

    var answer = 0;
    for (var u = 0; u < N; u++)
    {
        foreach (var v in G[u])
        {
            dp[v] = Math.Max(dp[v], dp[u] - 1);
        }

        if (dp[u] >= 0) answer++;
    }

    Console.WriteLine(answer);
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E