ABC245

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc245

問題A

コンテスト提出

時刻が早いといえるのは、A時のほうがC時より早い(A<C)とき、あるいは時が同じとき(A==C)にB分のほうがD分より早い(B<D)ときとなります。

public static void Solve()
{
    var (A, B, C, D) = Scanner.Scan<int, int, int, int>();
    var answer = A < C;
    if (A == C) answer |= B <= D;

    Console.WriteLine(answer ? "Takahashi" : "Aoki");
}

問題B

コンテスト提出

小さい順に数字を見ていき、その数字がAに含まれているかを確認することで、O(N^2)で答えを求めることができます。 また、Aに含まれているものをメモしておき、Aに含まれていない最小の数値を答えることで、O(N)で答えを求めることができます。

public static void Solve()
{
    var N = Scanner.Scan<int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var used = new bool[2001];
    foreach (var a in A)
    {
        used[a] = true;
    }

    for (var i = 0; i <= 2000; i++)
    {
        if (!used[i])
        {
            Console.WriteLine(i);
            return;
        }
    }
}

問題C

コンテスト提出

全てのAとBの要素の組み合わせを考えると、O(2^N)となってしまい、Nが大きい場合は実行制限時間内に答えを求めることができません。
そのため、計算量を抑えて答えを求める方法を考える必要があります。

AとBのi (0<i<N)番目の要素がXの数列として採用されることがあり得るか考えたとき、i-1番目に採用した数と差の絶対値がK未満であれば採用することができます。
まず始めに、X[0]としてあり得る数を考えたとき、A[0]とB[0]の二つが存在するため、それぞれをX[0]の候補として保持しておきます。
次に、X[1]を考えたとき、A[1]があり得るためには、A[0]との差がK以下、あるいはB[0]との差がK以下である必要があります。 どちらか一方でも条件を満たす場合は、X[1]の候補としてA[1]を保持し、満たさない場合はA[1]はX[1]の候補としてあり得ないため除外します。 同様に、B[1]も考えます。 X[2]以降も同様に、X[i-1]であり得る可能性のある数との差がK以下であるかを確認して候補を保持していきます。 そして、最後まで見たときに、あり得る数が存在するかどうかが答えとなり、O(N)で求めることができます。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<int>().ToArray();
    var B = Scanner.ScanEnumerable<int>().ToArray();
    var dp1 = new HashSet<int> { A[0], B[0] };
    for (var i = 1; i < N; i++)
    {
        var dp2 = new HashSet<int>();
        var (a, b) = (A[i], B[i]);
        foreach (var v in dp1)
        {
            if (Math.Abs(v - a) <= K) dp2.Add(a);
            if (Math.Abs(v - b) <= K) dp2.Add(b);
        }

        dp1 = dp2;
    }

    var answer = dp1.Count > 0;
    Console.WriteLine(answer ? "Yes" : "No");
}

問題D

コンテスト提出
復習提出

B=C/Aとなる数列Bを求める問題です。

まず、Cがどんな数列かを考えます。 C#のコードで書くと以下のようになります。

for(var ai = 0; ai <= N; ai++)
{
    for(var bi = 0; bi <= M; bi++)
    {
        C[ai + bi] += A[ai] * B[bi];
    }
}

Aの次元0<=ai<=Nと0<=B<=Mの次元biを考えたとき、aiとbiはC[ai+bi]に影響を与えます。
Bの最上位の次元の係数を考えたとき、B[M]はC[N+M]/A[N]で求められることがわかります。
そして、Bの最上位の次元の係数が決定すると、Bの最上位の次元とAの各次元が影響を与えるC[ai+M]から、A[ai]*B[M]を引くことで、Cの各係数からBの最上位の係数が与えた影響をとり除くことができます。

このことから、Bの最上位の次元から順にbiとaiを固定しながらC[ai+bi]の値を更新していくことで、Bの次元の係数を確定していくことができます。

public static void Solve()
{
    var (N, M) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    var C = Scanner.ScanEnumerable<long>().ToArray();
    var B = new long[M + 1];

    for (var bi = M; bi >= 0; bi--)
    {
        B[bi] = C[bi + N] / A[N];
        for (var ai = N; ai >= 0; ai--)
        {
            C[ai + bi] -= A[ai] * B[bi];
        }
    }

    Console.WriteLine(string.Join(" ", B));
}

問題E

復習提出

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

• チョコレートが大きい順に処理したい(縦?横?縦+横?面積?)。
• 座標圧縮とFenwickTreeで使える箱があるかどうかは確認できそう。

解説では、チョコレートと箱をまとめて縦の降順にみていき、ソート可能なセットを使って横の長さを管理する方法が紹介されていました。

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

    var chocos = A.Zip(B).Select(x => new Element(0, x.First, x.Second));
    var cases = C.Zip(D).Select(x => new Element(1, x.First, x.Second));
    var list = chocos.Concat(cases).ToList();
    list.Sort((x, y) =>
    {
        var result = y.H.CompareTo(x.H);
        return result != 0 ? result : y.Type.CompareTo(x.Type);
    });

    var set = new RandomizedBinarySearchTree<int>();
    foreach (var e in list)
    {
        if (e.Type == 0)
        {
            var lb = set.LowerBound(e.W);
            if (lb < 0 || set.Count <= lb)
            {
                Console.WriteLine("No");
                return;
            }

            set.RemoveAt(lb);
        }
        else
        {
            set.Insert(e.W);
        }
    }

    Console.WriteLine("Yes");
}

問題F

復習提出

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

    var queue = new Queue<int>();
    for (var i = 0; i < N; i++)
    {
        if (deg[i] == 0) queue.Enqueue(i);
    }

    var answer = N;
    while (queue.Count > 0)
    {
        var u = queue.Dequeue();
        answer--;

        foreach (var v in G[u])
        {
            deg[v]--;
            if (deg[v] == 0) queue.Enqueue(v);
        }
    }

    Console.WriteLine(answer);
}