✍️

【C#】AtCoder ABC401 - C K-bonacci

に公開
abc
atcode
tech

AtCoder ABC401 - C K-bonacciをC#で解く

AtCoder最近始めました。
DP(動的計画法)について勉強中で理解が浅いため、アウトプットして知識の定着を目論見ます。

前提

  • AtCoder初心者(始めたばかり。初心者にオススメ10問が終わったところ)
  • 仕事はWebアプリ開発。シビアな計算量を求められることはほぼない。必要な場合は生成AIで解決している😂

問題文

正整数 N,KN,K が与えられます。長さ N+1N+1 の数列 A=(A0,A1,…,AN)A=(A0,A1,…,AN) の各要素の値を、以下の方法で定義します。

  • 0≤i<K のとき、

    Ai=1Ai=1

  • K≤i のとき、

    Ai=Ai−K+Ai−K+1+…+Ai−1Ai=Ai−K+Ai−K+1+…+Ai−1

An を 1e9(10の9乗)で割ったあまりを求めてください。

解説

  • DPの内容を表形式にしたもの

Sn = S[n-1] + A[-1]

１つ前(n-1)の数列と累積和の和で求められる

An = S[n] - A[n-k]

Snの累積和からS(n-k)の累積和の差で求められる

回答コード

上記をコードに落とし込んだ物
入力値によってはかなり値が大きくなるためMOD(10の9乗)で計算

static void Exec()
{
    var inputs = ConsoleHelper.ReadIntArray();
    var N = inputs[0];
    var K = inputs[1];

    Console.WriteLine(Calc(N, K));
}

private static long Calc(int n, int k)
{
    const long MOD = (long)1e9;

    var A = new long[n + 1];
    var S = new long[n + 2];

    // N = 7, K = 3
    // 数値       0, 1, 2, 3, 4, 5, 6, 7
    // 数列   Ai[ 1, 1, 1]
    // 累積和 Si[ 0, 1, 2, 3]

    // K = 3 なので A2, S3 まで計算
    for (var i = 0; i < k && i <= n; i++)
    {
        A[i] = 1;
        S[i + 1] = S[i] + A[i];
    }

    // N = 7, K = 3
    // 数値       0,  1,  2,  3,  4,  5, 6,  7
    // 数列   Ai[ 1,  1,  1,  3,  5,  9, 17, 31]
    // 累積和 Si[ 0,  1,  2,  3,  6, 11, 20, 37]

    // Ai = Si - S(i-k) : A4 = S4 - S(4-3) : (A4)5 = (S4)6 - (S(4-3))1
    for (var i = k; i <= n; i++)
    {
        // MODを足してMODの余りを入れるのはオーバーフローを防ぐため
        A[i] = (S[i] - S[i - k] + MOD) % MOD;
        S[i + 1] = (S[i] + A[i]) % MOD;
    }

    return A[n];
}

感想

解くのにかなり時間がかかってしまった。
解法?テクニック?数学?を知らないとC問題は厳しいと感じた。
最初はループでロジックを記載したが計算量が多くなりすぎてしまい変更。
調べるとDP(動的計画法)という処理方法があることを知り、計算量をO(N)にすることができた。

まずは過去問をこなして色々なパターンやアルゴリズムを覚えようと思います。

Discussion