ABC297

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc297

問題A

コンテスト提出

最初にT[i]-T[i-1]<=DとなるT[i]を走査します。

public static void Solve()
{
    var (N, D) = Scanner.Scan<int, int>();
    var T = Scanner.ScanEnumerable<int>().ToArray();
    for (var i = 1; i < N; i++)
    {
        var d = T[i] - T[i - 1];
        if (d <= D)
        {
            Console.WriteLine(T[i]);
            return;
        }
    }

    Console.WriteLine(-1);
}

問題B

コンテスト提出

1つ目の条件をF1、2つ目の条件をF2としたとき、F1 && F2を判定します。

F1; Bが2文字あることが保証されているので、文字列の先頭から見て初めて出現するBのインデックスをx、文字列の末尾から見て初めて出現するBのインデックスをyとしたとき、x%2 != y%2を判定します。

F2; Rが2文字あることが保証されているので、文字列の先頭から見て初めて出現するRのインデックスをx、文字列の末尾から見て初めて出現するRのインデックスをyとしたとき、x<z<y && S[z]=='K'となるインデックスzが存在するかを判定します。

public static void Solve()
{
    var S = Scanner.Scan<string>();

    bool F1(string s)
    {
        var x = 0;
        var y = s.Length - 1;
        while (x < s.Length && s[x] != 'B') x++;
        while (y >= 0 && s[y] != 'B') y--;
        return x % 2 != y % 2;
    }

    bool F2(string s)
    {
        var x = 0;
        var y = s.Length - 1;
        while (x < s.Length && s[x] != 'R') x++;
        while (y >= 0 && s[y] != 'R') y--;
        for (var i = x + 1; i < y; i++)
        {
            if (s[i] == 'K') return true;
        }

        return false;
    }

    var answer = F1(S) && F2(S);
    Console.WriteLine(answer ? "Yes" : "No");
}

問題C

コンテスト提出

文字列中の全てのTTをPCに置き換えたものが答えとなります。

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

    for (var i = 0; i < H; i++)
    {
        for (var j = 0; j + 1 < W; j++)
        {
            if ((S[i][j], S[i][j + 1]) == ('T', 'T'))
            {
                S[i][j] = 'P';
                S[i][j + 1] = 'C';
            }
        }
    }

    Printer.Print2D(S);
}

問題D

コンテスト提出

操作を愚直に実装してしまうと、AとBの差がを大きいときに実行時間制限に間に合わなくなってしまうため、同じ操作が行われているものをまとめることを考えます。
A<Bのとき、1回の操作でBの値はA減少します。
この操作はA<Bの間繰り返されることから、D=B-AとしたときCeil(D/A)回の操作が行われます。
A>Bのとき、AとBの値を入れ替えることで、A<Bとしたときと同様の操作が行われます。
このことから、A==Bになるまでに行われる操作の合計が答えとなります。

public static void Solve()
{
    var (A, B) = Scanner.Scan<long, long>();

    long F(long a, long b)
    {
        long result = 0;
        while (a != b)
        {
            if (a > b) (a, b) = (b, a);
            var d = b - a;
            var t = (d + a - 1) / a;
            result += t;
            b -= t * a;
        }

        return result;
    }

    var answer = F(A, B);
    Console.WriteLine(answer);
}

問題E

コンテスト提出

支払う金額としてあり得るものにA[i] (1<=i<=N)を足したものも、支払う金額としてあり得るものになります。
そのため、支払う金額としてあり得るものを優先度付きキューを使って小さい順に取り出していき、K回目に取り出したものが答えとなります。
支払う金額としてあり得るもののうち、同じ金額は1回だけ数えることに注意が必要です。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, int>();
    var A = Scanner.ScanEnumerable<long>().Distinct().ToArray();
    var queue = new PriorityQueue<long>(A);
    var used = new HashSet<long>(A);
    while (K > 1)
    {
        K--;
        var x = queue.Dequeue();
        foreach (var a in A)
        {
            var y = x + a;
            if (used.Contains(y)) continue;
            queue.Enqueue(y);
            used.Add(y);
        }
    }

    var answer = queue.Dequeue();
    Console.WriteLine(answer);
}