ABC258

Published on Saturday, 02 July 2022

Updated on Saturday, 02 July 2022

atcoder csharp

はじめに

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

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

コンテスト

https://atcoder.jp/contests/abc258

問題A

コンテスト提出

1時間は60分なので、Kを60で割った商が経過時、Kを60で割った余りが経過分となるので、21+K/60時K%60分が答えとなります。
C#では文字列補間でカスタム数値形式文字列を使うことで、数値を0埋めで表示することができます。

public static void Solve()
{
    var K = Scanner.Scan<int>();
    var x = K / 60;
    var y = K % 60;
    Console.WriteLine($"{21 + x}:{y:00}");
}

問題B

コンテスト提出

全てのマスから縦横斜めの8方向にずらした数値を全探索します。
8方向全てを書くのは大変なので、行と列のそれぞれの移動差分を用意することで、差分に移動量を掛けて範囲内に収まるようにNで割った余りを取ることで、簡単に記述することができます。

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

    var D8 = new[] { (1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1) };

    long answer = 0;
    for (var i = 0; i < N; i++)
    {
        for (var j = 0; j < N; j++)
        {
            foreach (var (di, dj) in D8)
            {
                long v = 0;
                for (var k = 0; k < N; k++)
                {
                    var ii = (i + di * k + N) % N;
                    var jj = (j + dj * k + N) % N;
                    v = v * 10 + A[ii][jj];
                }

                answer = Math.Max(answer, v);
            }
        }
    }

    Console.WriteLine(answer);
}

問題C

コンテスト提出

クエリごとに文字列を操作してしまうと、クエリごとの計算量がO(N)、全体の計算量がO(QN)になってしまい、実行時間制限に間に合わないため、計算量を改善する必要があります。

クエリ1に注目すると、N文字目の次を1文字目としたとき、文字列をx回右にシフトしてることがわかります。
そして、文字列を右にシフトすると、先頭の位置は-x分移動し、移動先が負の場合はNを足した位置が先頭になります。
このように、文字列の先頭の位置がどこであるかのみを管理することで、クエリごとの計算量をO(1)に改善することができます。

public static void Solve()
{
    var (N, Q) = Scanner.Scan<int, int>();
    var S = Scanner.Scan<string>();
    var idx = 0;
    while (Q-- > 0)
    {
        var (t, x) = Scanner.Scan<int, int>();
        if (t == 1)
        {
            idx = (idx - x + N) % N;
        }
        else
        {
            var i = (idx + x - 1) % N;
            Console.WriteLine(S[i]);
        }
    }
}

i番目のステージまでに必要な最小の時間 + 初回攻略時間 + (i番目のステージで必要な時間 * 残り回数全てを)がi番目のステージおける時間の最小値となるとなるので、全てのステージにおける時間の最小値の最小値が答えとなります。ステージごとに毎度i番目のステージまでに必要な最小の時間を計算してしまうと時間計算量がO(N)かかってしまうので、累積和を用いることでO(1)に改善することができます。

public static void Solve()
{
    var (N, X) = Scanner.Scan<int, int>();
    var AB = new (long A, long B)[N];
    for (var i = 0; i < N; i++)
    {
        AB[i] = Scanner.Scan<long, long>();
    }

    var minStarts = new long[N];
    for (var i = 1; i < N; i++)
    {
        minStarts[i] = minStarts[i - 1] + AB[i - 1].A + AB[i - 1].B;
    }

    const long inf = (long)4e18;
    var answer = inf;
    for (var i = 0; i < N; i++)
    {
        var x = Math.Max(0, X - (i + 1));
        var time = sum + AB[i].A + AB[i].B + x * AB[i].B;
        answer = Math.Min(answer, time);
        sum += AB[i].A + AB[i].B;
    }

    Console.WriteLine(answer);
}

問題E

復習提出

i番目のじゃがいもを開始位置としたとき、1つの箱に必要なじゃがいもの個数をC[i]とすると、次の箱に使うじゃがいもの開始位置は(i+C[i])%Nとなり、開始位置の集合は最大でもNの有向グラフとして表すことができます。

# 入力例1
# 3 2 5
# 3 4 1
# 1
# 2

0番目のじゃがいもから箱を作る: {0, 1}    => 2個 => 次は (0+2)%3 = 2番目のじゃがいも
2番目のじゃがいもから箱を作る: {2, 0, 1} => 3個 => 次は (2+3)%3 = 2番目のじゃがいも
2番目のじゃがいもから箱を作る: {2, 0, 1} => 3個 => 次は (2+3)%3 = 2番目のじゃがいも
...

このことから、有効グラフのK番目の頂点に値する開始位置における必要なじゃがいもの個数が答えとなります。時間計算量について、C[i]は累積和と尺取り法を使うことでO(N)、有効グラフもO(N)で事前に計算でき、クエリに対してO(1)で答えを求めることができるので、全体の時間計算量はO(N+Q)となります。

public static void Solve()
{
    var (N, Q, X) = Scanner.Scan<int, int, long>();
    var W = Scanner.ScanEnumerable<long>().ToArray();
    var sum = W.Sum();

    var cumW = new long[N * 2 + 1];
    for (var i = 0; i < N * 2; i++)
    {
        cumW[i + 1] = cumW[i] + W[i % N];
    }

    var counts = new long[N];
    {
        var r = 0;
        var x = X % sum;
        for (var l = 0; l < N; l++)
        {
            counts[l] = X / sum * N;
            while (cumW[r] - cumW[l] < x) r++;
            counts[l] += r - l;
        }
    }

    var next = new int[N];
    for (var i = 0; i < N; i++)
    {
        next[i] = (int)((i + counts[i]) % N);
    }

    var steps = new List<int>();
    var dict = new Dictionary<int, int>();
    var noLoopLength = 0;
    var loopLength = 0;
    {
        var curr = 0;
        for (var i = 0;; i++)
        {
            if (dict.ContainsKey(curr))
            {
                noLoopLength = dict[curr];
                loopLength = i - dict[curr];
                break;
            }

            dict[curr] = i;
            steps.Add(curr);
            curr = next[curr];
        }
    }

    while (Q-- > 0)
    {
        var K = Scanner.Scan<long>() - 1;
        if (K <= noLoopLength)
        {
            var box = steps[(int)K];
            Console.WriteLine(counts[box]);
        }
        else
        {
            var mod = (K - noLoopLength) % loopLength;
            var box = steps[(int)(noLoopLength + mod)];
            Console.WriteLine(counts[box]);
        }
    }
}

はじめに

コンテスト

問題A

問題B

問題C

問題D

問題E