AtCoder B,C問題をKotlinで解こう - ABC248

当記事ではAtCoder、ABCのB問題ならびにC問題（時々D問題も）のKotlinでの解法を超初心者向けに詳細に解説します。

https://atcoder.jp/contests/abc248/tasks

## [B - Slimes](https://atcoder.jp/contests/abc248/tasks/abc248_b)
#### やりたいこと
答えは最大に見積もっても30そこそこなので、**$AK^n >= B$ となる最小のn**をそのまま求めよう。

:::note warn
入力値は全てIntの範囲ですが、$AK^n >= B$ を判定する際、Intの最大値を超えることがあるため、オーバーフローにならないよう対策する必要があります。
:::

#### サンプルコード
```kotlin:main.kt
fun main(args: Array<String>) {
    // 入力値の取得
    val (a, b, k) = readLine()!!.split(" ").map { it.toInt() }
    // AK^n >= B の判定用変数、オーバーフロー対策でLong型にする
    var cur = a.toLong()
    var n = 0
    while (cur < b) {
        cur *= k
        n++
    }
    println(n)
}
```

## [C - Dice Sum](https://atcoder.jp/contests/abc248/tasks/abc248_c)
#### やりたいこと
**M面体のサイコロN個を振って合計値がK以下になる組み合わせの数**を求めよう。サイコロは
それぞれ区別できるものとする。
上記を求める関数を仮にf(N,K)とする。f(N,K)を求めるには、一つ目のサイコロで出た値をLとして、Lの取りうる範囲（1~M)でf(N-1,K-L)を求めて合計すれば良い。関数fの中でさらにfを呼ぶ **再帰処理** を使おう。

:::note info
**再帰処理**については、過去記事「AtCoder B,C問題をKotlinで解こう - ABC247 [C - 1 2 1 3 1 2 1](https://qiita.com/paragraph14/items/d34df3f52abd8119064e#c---1-2-1-3-1-2-1)」も併せて参照することをお勧めします。
:::

#### 入力値の取得
```kotlin
    val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
```
#### 関数fの実装
```kotlin
    // diceCount: 振らなければならない残りのサイコロ数
    // total: 合計値がそれ以上にならなければならない値
    fun f(diceCount: Int, total: Int): Long {
        // サイコロ1個の出目の最小値は1なので、totalがdiceCountより小さい場合は条件を達成できない
        if (total < diceCount) {
            return 0
        }
        // サイコロ数が残り1個の場合、条件を達成できる出目の数を返す
        if (diceCount <= 1) {
            return Math.min(total, m).toLong()
        }
        // 戻り値の初期化
        var ans = 0L
        // サイコロが取りうる範囲で再帰処理を行い、結果を合計していく
        for (i in (1..m)) {
            ans += f(diceCount - 1, total - i)
        }
        return ans
    }
```

#### 余剰を求める設問
問題文に「**答えを 998244353 で割った余りを求めてください。**」とある。こういった設問の場合、答えはLongの範囲を超える値になる事が多い。最終的な答えに対して余剰を求めるような方法ではオーバーフローとなってしまう。
**x が 素数の場合、 ```(a+b+c)%x``` と ```((a%x)+(b%x)+(c%x))%x``` は等しくなる。**
計算途中の値を余剰にして、オーバーフローを防ごう。

```kotlin
    val MOD = 998244353
    // diceCount: 振らなければならない残りのサイコロ数
    // total: 合計値がそれ以上にならなければならない値
    fun f(diceCount: Int, total: Int): Long {
        // サイコロ1個の出目の最小値は1なので、totalがdiceCountより小さい場合は条件を達成できない
        if (total < diceCount) {
            return 0
        }
        // サイコロ数が残り1個の場合、条件を達成できる出目の数を返す
        if (diceCount <= 1) {
            return Math.min(total, m).toLong()
        }
        // 戻り値の初期化
        var ans = 0L
        // サイコロが取りうる範囲で再帰処理を行い、結果を合計していく
        for (i in (1..m)) {
            ans += f(diceCount - 1, total - i)
            // 余剰を求める
            ans %= MOD
        }
        return ans
    }

```

#### 関数fの呼び出し回数を減らす
入力値が最大の場合、関数fの呼び出し回数は 8 * 10^80 を超えるほどになる。その場合はTLEとなってしまうため、対策しよう。
仮に1回目と2回目のサイコロの出目がそれぞれ ```(1,2)``` であった場合、次に呼ばれる関数f は ```f(n-2, k-3)``` となる。
同様に1回目と2回目の出目が ```(2,1)``` の場合も次に呼ばれる関数fも前述と同じく ```f(n-2, k-3)``` となる。引数が同じならば、関数は同じ結果を返す。
呼び出し回数 8 * 10^80超 に対して、その引数が取りうる値の組み合わせはわずか 50^3 である。 **計算結果を配列等に保持して、同じ引数の処理結果を使いまわそう。**

##### 具体的にはどうする？
引数の値をキーとして値を取り出せるよう、計算結果を保持する配列を宣言しよう。
nはdiceCountの最大値、kはtotalの最大値、それぞれ+1するのは配列のindexが0始まりのため。
```kotlin
    val dic = Array(n + 1) { arrayOfNulls<Long>(k + 1) }
```
##### 値の設定
戻り値を返す前に同じ引数で関数が呼ばれた時に再利用できるよう、diceCountとtotalをキーとして配列に値を格納しよう
```kotlin
        // サイコロが取りうる範囲で再帰処理を行い、結果を合計していく
        for (i in (1..m)) {
            ans += f(diceCount - 1, total - i)
            // 余剰を求める
            ans %= MOD
        }
        // 値を再利用できるよう配列に保持
        dic[diceCount][total] = ans
        return ans
    }

```


##### 値の取り出し

f関数の中で実際の値を出す処理をする前に、配列の中に使いまわせる値が入っていないかを確認しよう。diceCountとtotalをキーとして配列の値を参照し、nullでなければそれを戻り値として使おう。
```kotlin
    fun f(diceCount: Int, total: Int): Long {
        // サイコロ1個の出目の最小値は1なので、totalがdiceCountより小さい場合は条件を達成できない
        if (total < diceCount) {
            return 0
        }
        // サイコロ数が残り1個の場合、条件を達成できる出目の数を返す
        if (diceCount <= 1) {
            return Math.min(total, m).toLong()
        }

        // 配列の中に使いまわせる数が入っていないかどうかを確認。値があれば（nullでなければ）それを使う。
        dic[diceCount][total]?.let { return it }
```

#### サンプルコード
```kotlin:main.kt
fun main(args: Array<String>) {
    val (n, m, k) = readLine()!!.split(" ").map { it.toInt() }
    println(Solve(n, m, k).f())
}

class Solve(val n: Int, val m: Int, val k: Int) {
    companion object {
        const val MOD = 998244353
    }

    fun f(): Long {
        return f(n, k)
    }

    val dic = Array(n + 1) { arrayOfNulls<Long>(k + 1) }
    // diceCount: 振らなければならない残りのサイコロ数
    // total: 合計値がそれ以上にならなければならない値
    private fun f(diceCount: Int, total: Int): Long {
        // サイコロ1個の出目の最小値は1なので、totalがdiceCountより小さい場合は条件を達成できない
        if (total < diceCount) {
            return 0
        }
        // サイコロ数が残り1個の場合、条件を達成できる出目の数を返す
        if (diceCount <= 1) {
            return Math.min(total, m).toLong()
        }
        // 配列の中に使いまわせる数が入っていないかどうかを確認。値があれば（nullでなければ）それを使う。
        dic[diceCount][total]?.let { return it }
        // 戻り値の初期化
        var ans = 0L
        // サイコロが取りうる範囲で再帰処理を行い、結果を合計していく
        for (i in (1..m)) {
            ans += f(diceCount - 1, total - i)
            // 余剰を求める
            ans %= MOD
        }
        // 値を再利用できるよう配列に保持
        dic[diceCount][total] = ans
        return ans
    }
}
```