ABC233

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc233

問題A

コンテスト提出

(Y-X)を10で割ったときの切り上げの値が必要な切手の数となります。 (Y-X)が負の場合は既に金額が足りているので、0とMaxを取ることで、if文なくすことができます。

public static void Solve()
{
    var (X, Y) = Scanner.Scan<int, int>();
    var answer = Math.Max(0, ((Y - X) + 9) / 10);
    Console.WriteLine(answer);
}

問題B

コンテスト提出

C#では、Array.Reverseメソッドを使うことで、配列の指定した範囲を逆順にすることができます。

public static void Solve()
{
    var (L, R) = Scanner.Scan<int, int>();
    L--;
    var S = Scanner.Scan<string>().ToCharArray();
    Array.Reverse(S, L, R - L);
    Console.WriteLine(string.Join("", S));
}

問題C

コンテスト提出

総積がXになるためには、要素となる数がXの倍数である必要があるため、それ以外を除いたものから、袋からそれぞれ1つずつ選んだ時の組み合わせの数となります。
再帰関数を使ってidxとなる袋を順にみていくとき、ボールの値が現在の値currの倍数であり、currが0より大きい場合、次の袋に進むことができます。
もしすべての袋から1つずつ拾うことができて、currの値が1のときは、それまでに選んだボールの値の総積がXとなるので、その時の数を数え上げることで答えを求めることができます。

public static void Solve()
{
    var (N, X) = Scanner.Scan<int, long>();
    var A = new long[N][];
    for (var i = 0; i < N; i++)
    {
        A[i] = Scanner.ScanEnumerable<long>().Skip(1).Where(x => X % x == 0).ToArray();
    }

    var answer = 0L;

    void Dfs(int idx, long curr)
    {
        if (idx == N)
        {
            if (curr == 1) answer++;
            return;
        }

        foreach (var a in A[idx])
        {
            if (curr % a == 0 && curr / a != 0)
            {
                Dfs(idx + 1, curr / a);
            }
        }
    }

    Dfs(0, X);

    Console.WriteLine(answer);
}

問題D

復習提出

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

• 累積和で範囲を求められそう
• 尺取り法は単調増加ではないから使えなさそう
• ディクショナリでまとめて数え上げられそう

Lを固定したときにRの数を数え上げましたが、実装が間違っていたのかWAで時間切れとなりました。

解説ではRを固定したときにLの数を数え上げていました。

public static void Solve()
{
    var (N, K) = Scanner.Scan<int, long>();
    var A = Scanner.ScanEnumerable<long>().ToArray();
    var cum = new long[N + 1];
    for (var i = 0; i < N; i++)
    {
        cum[i + 1] = cum[i] + A[i];
    }

    var dict = new Dictionary<long, long>();
    var answer = 0L;
    for (var i = 1; i <= N; i++)
    {
        if (!dict.ContainsKey(cum[i - 1]))
        {
            dict[cum[i - 1]] = 0;
        }
        dict[cum[i - 1]]++;
        if (dict.ContainsKey(cum[i] - K))
        {
            answer += dict[cum[i] - K];
        }
    }
    
    Console.WriteLine(answer);
}

問題E

コンテスト提出

大きい桁から累積和を取ると、その桁に最終的に足される数を求めることができます。 累積和を小さい桁から見たとき、その桁の累積和の1の位の数が桁として確定し、累積和の1の位より大きい値は、その次の桁に繰り上げられるため、次の桁の累積和に足す必要があります。
出力では、一番大きい桁が0の場合は除外して表示する必要があります。

public static void Solve()
{
    var X = Scanner.Scan<string>();
    var N = X.Length;
    var cum = new int[N + 1];
    for (var i = 0; i < N; i++)
    {
        cum[i + 1] = cum[i] + X[i] - '0';
    }

    var answer = new int[X.Length + 1];
    for (var i = N; i > 0; i--)
    {
        answer[i] = cum[i] % 10;
        cum[i - 1] += cum[i] / 10;
    }

    answer[0] += cum[0];
    if (answer[0] == 0)
    {
        Console.WriteLine(string.Join("", answer.Skip(1)));
    }
    else
    {
        Console.WriteLine(string.Join("", answer));
    }
}