ABC240

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc240

問題A

コンテスト提出

10で割ったときのあまりの値を比較することで、ループを再現することができます。 また、隣り合っていることは差が1であればいいので、それを確かめます。 例えば、a=2, b=3のときは、2+1==3となり、a=1,b=10の時は1==0+1となります。

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

問題B

コンテスト提出

重複を削除したときの個数が答えとなります。 C#のLINQには、Distinctというシーケンス内の重複を除いたシーケンスを返すメソッドがあるため、それを使い個数を数えます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    var answer = A.Distinct().Count();
    Console.WriteLine(answer);
}

問題C

コンテスト提出

動的計画法で答えを求めます。 i番目のジャンプを座標j(0<=j<=X)から行うと、i+1番目では、j+aまたはj+bに存在することができます。初期状態の0をtrueとしたとき、そこからの遷移を計算し、N回ジャンプ後のXの値がtrueならば存在することができると表現できます。

public static void Solve()
{
    var (N, X) = Scanner.Scan<int, int>();
    var dp = new bool[N + 1, X + 1];
    dp[0, 0] = true;
    for (var i = 0; i < N; i++)
    {
        var (a, b) = Scanner.Scan<int, int>();
        for (var j = 0; j <= X; j++)
        {
            if (j + a <= X) dp[i + 1, j + a] |= dp[i, j];
            if (j + b <= X) dp[i + 1, j + b] |= dp[i, j];
        }
    }

    var answer = dp[N, X];
    Console.WriteLine(answer ? "Yes" : "No");
}

問題D

コンテスト提出

スタックに順番にボールを追加していき、同じ数字がK個連続した場合は削除する操作を行います。このとき一つの数字につき1つの値を入れていると、計算量はO(N^2)になってしまうので、連続した値は値と個数の一つのオブジェクトとしてまとめ、スタックに入っているボールの個数を管理することで、計算量をO(N)に抑えることができます。 具体的には、もしスタックが空またはスタックのトップと異なる値の場合は、値と個数1をタプルとしてまとめてスタックに追加し、もしスタックのトップと同じ値の場合は、スタックのトップの個数を更新します。その後、スタックのトップを順にみていき、値と個数が同じ場合はスタックから取り除き、現在の個数も減少させます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var curr = 0;
    var stack = new Stack<(int V, int C)>();
    foreach (var a in A)
    {
        curr++;
        if (stack.Count == 0)
        {
            stack.Push((a, 1));
            Console.WriteLine(curr);
            continue;
        }

        var (v, c) = stack.Pop();

        if (a == v)
        {
            c++;
            stack.Push((v, c));
        }
        else
        {
            stack.Push((v, c));
            stack.Push((a, 1));
        }

        while (stack.Count > 0)
        {
            (v, c) = stack.Peek();
            if (v == c)
            {
                stack.Pop();
                curr -= c;
            }
            else
            {
                break;
            }
        }

        Console.WriteLine(curr);
    }
}

問題E

コンテスト提出

問題文の根付き木について、子を持たない頂点に対してそれぞれ異なる値を与えたときに、部分木iが持つ値群の最小値と最大値をそれぞれLiとRiとしたとき、頂点iは区間[Li, Ri]を持つと解釈することができます。 そのため、深さ優先探索を行い、子を持たない頂点の場合はそれまでに出現していない値をLiとRiに設定し、子を持つ頂点は、子のLiとRiの中でそれぞれ最小、最大となるものを選択することで、答えとなる区間を求めることができます。

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

    const int inf = (int)1e9;
    var L = new int[N];
    var R = new int[N];
    var curr = 1;
    (int L, int R) Dfs(int u, int p)
    {
        var l = inf;
        var r = -inf;
        foreach (var v in G[u])
        {
            if (v == p) continue;
            var (ll, rr) = Dfs(v, u);
            l = Math.Min(l, ll);
            r = Math.Max(r, rr);
        }

        if (l == inf)
        {
            L[u] = curr;
            R[u] = curr;
            curr++;
        }
        else
        {
            L[u] = l;
            R[u] = r;
        }

        return (L[u], R[u]);
    }

    Dfs(0, -1);

    foreach (var (l, r) in L.Zip(R))
    {
        Console.WriteLine($"{l} {r}");
    }
}