AtCoder ABC401 C問題「K-bonacci」解説（Java）

## 問題概要

[AtCoder Beginner Contest 401 C - K-bonacci](https://atcoder.jp/contests/abc401/tasks/abc401_c)

正整数N,Kが与えられ、長さN+1の数列A=(A_0, A_1, ..., A_N)を以下のように定義します：
- 0≤i<K のとき、A_i=1
- K≤i のとき、A_i=A_{i-K}+A_{i-K+1}+...+A_{i-1}

A_Nを10^9で割ったあまりを求める問題です。

## 解法のアプローチ

この問題は漸化式を用いた動的計画法（DP）で解くことができます。

### アルゴリズムの概要

1. dp[i]配列を用意し、dp[i] = A_iとなるように計算します
2. 最初のK個の要素（dp[0]〜dp[K-1]）を1で初期化します
3. K番目以降の要素は、「直前のK個の要素の合計」として計算します
4. 各ステップで10^9の剰余を取ります

### 効率的な実装のポイント

単純に各要素を計算すると、各ステップでK個の要素を合計する必要があり、計算量がO(N×K)になってしまいます。これを最適化するために「スライディングウィンドウ」の手法を使います：

1. 最初のK個の要素の合計をsum変数に保存
2. 新しい要素dp[i]を計算：dp[i] = sum
3. 次のステップのsumを更新：sum = sum - dp[i-K] + dp[i]
   - 「最も古い要素を引く」＋「新しい要素を足す」

これによって計算量をO(N)に削減できます。

## スライディングウィンドウの図解

N=6, K=3の場合を例に、スライディングウィンドウの動作を図解します：

### ステップ1：初期状態
```
dp[0] = 1, dp[1] = 1, dp[2] = 1
```

最初のウィンドウ（K個の要素）:
```
[ dp[0], dp[1], dp[2] ]
[   1  ,   1  ,   1   ] → sum = 3
```

### ステップ2：dp[3]の計算
```
dp[3] = sum = 3
```

ウィンドウをスライドさせる:
```
     [ dp[1], dp[2], dp[3] ]
     [   1  ,   1  ,   3   ] → sum = 5
     ↑        ↑        ↑
古い要素を除去       新しい要素を追加
 (dp[0]=1)          (dp[3]=3)
```

### ステップ3：dp[4]の計算
```
dp[4] = sum = 5
```

ウィンドウをさらにスライド:
```
            [ dp[2], dp[3], dp[4] ]
            [   1  ,   3  ,   5   ] → sum = 9
            ↑        ↑        ↑
     古い要素を除去       新しい要素を追加
      (dp[1]=1)          (dp[4]=5)
```

### ステップ4：dp[5]の計算
```
dp[5] = sum = 9
```

ウィンドウをさらにスライド:
```
                   [ dp[3], dp[4], dp[5] ]
                   [   3  ,   5  ,   9   ] → sum = 17
                   ↑        ↑        ↑
            古い要素を除去       新しい要素を追加
             (dp[2]=1)          (dp[5]=9)
```

### ステップ5：dp[6]の計算
```
dp[6] = sum = 17
```

## 具体例によるトレース

例：N=6, K=3の場合

### 初期化
```
dp[0] = dp[1] = dp[2] = 1
```

### K-1番目までの合計計算
```
sum = dp[0] + dp[1] + dp[2] = 1 + 1 + 1 = 3
```

### K番目以降の計算

1. dp[3]の計算：
   ```
   dp[3] = sum = 3
   sum = sum - dp[0] + dp[3] = 3 - 1 + 3 = 5
   ```

2. dp[4]の計算：
   ```
   dp[4] = sum = 5
   sum = sum - dp[1] + dp[4] = 5 - 1 + 5 = 9
   ```

3. dp[5]の計算：
   ```
   dp[5] = sum = 9
   sum = sum - dp[2] + dp[5] = 9 - 1 + 9 = 17
   ```

4. dp[6]の計算：
   ```
   dp[6] = sum = 17
   ```

したがって、答えはdp[6] = 17です。

## 配列と計算の流れ図解

計算の流れを視覚的に表現します：

```
インデックス: 0  1  2  3  4  5  6
初期値:      1  1  1  ?  ?  ?  ?
```

dp[3]を計算（sum = dp[0] + dp[1] + dp[2] = 3）:
```
インデックス: 0  1  2  3  4  5  6
値:         1  1  1  3  ?  ?  ?
            ↑  ↑  ↑
            これらの合計がdp[3]
```

dp[4]を計算（sum = dp[1] + dp[2] + dp[3] = 5）:
```
インデックス: 0  1  2  3  4  5  6
値:         1  1  1  3  5  ?  ?
               ↑  ↑  ↑
               これらの合計がdp[4]
```

dp[5]を計算（sum = dp[2] + dp[3] + dp[4] = 9）:
```
インデックス: 0  1  2  3  4  5  6
値:         1  1  1  3  5  9  ?
                  ↑  ↑  ↑
                  これらの合計がdp[5]
```

dp[6]を計算（sum = dp[3] + dp[4] + dp[5] = 17）:
```
インデックス: 0  1  2  3  4  5  6
値:         1  1  1  3  5  9  17
                     ↑  ↑  ↑
                     これらの合計がdp[6]
```

## Java実装

```java
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int K = scanner.nextInt();
    
    long[] dp = new long[N+1];
    for(int i = 0; i < Math.min(K, N+1); i++) {
        // K-1番目までは1とする
        dp[i] = 1;
    }
    
    // K-1番目までの合計を計算
    long sum = 0;
    for (int i = 0; i < Math.min(K, N+1); i++) {
        sum = (sum + dp[i]) % 1_000_000_000;
    }

    // K番目以降を計算
    for (int i = K; i <= N; i++) {
        dp[i] = sum;
        sum = (sum - dp[i-K] + dp[i]) % 1_000_000_000;
        if (sum < 0) {
            sum += 1_000_000_000;
        }
    }

    System.out.println(dp[N]);
    scanner.close();
  }
}
```

## モジュロ演算における注意点

### 負の値の処理

Javaの`%`演算子は被除数の符号を保持します。つまり`-5 % 3 = -2`となります。しかし、この問題では常に0以上10^9未満の範囲の値が必要です。

計算中に`sum = (sum - dp[i-K] + dp[i]) % MOD`で負の値になる可能性があるため、以下の処理が必要になります：

```java
if (sum < 0) {
    sum += 1_000_000_000;
}
```

これにより、負の剰余を同等の正の剰余（0〜MOD-1の範囲）に変換します。これは「合同」の概念に基づいており、例えば「-7 ≡ 5 (mod 12)」のように同じ剰余類に属する値を使うことができます。

### 合同の概念と時計の例

モジュロ演算の「合同」を理解するために、12時間制の時計を例に考えてみましょう：

```
      12
       |
    11 |  1
       |
  10   |   2
       |
    9--|--3
       |
    8  |  4
       |  
     7 |  5
       |
       6
```

- 現在8時で、5時間後は何時？ → 1時（8+5=13 → 13 mod 12 = 1）
- 現在3時で、10時間前は何時？ → 5時（3-10=-7 → -7 mod 12 = 5）

時計の例では、-7時と5時は「同じ時刻」を指します。これが「-7 ≡ 5 (mod 12)」の意味です。

### 大きな数値の表記

コードでは`1_000_000_000`という表記を使っていますが、これはJavaで大きな数値を読みやすくするための表記法です。アンダースコア（_）は数値を視覚的に区切るだけで、値自体には影響しません。

## まとめ

この問題は漸化式を効率的に計算するための典型的なテクニック（スライディングウィンドウ、累積和の応用）と、剰余演算を正しく扱うための知識が試されています。適切な最適化により、O(N×K)からO(N)に計算量を削減できます。