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

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

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

## [B - Mex](https://atcoder.jp/contests/abc245/tasks/abc245_b)
#### やりたいこと
入力された配列に含まれない最小の非負整数を求めたい。配列の要素の範囲が0~2000なので、求める非負整数は0~2001の範囲となる。範囲は広くないので、0~2001のそれぞれについて配列に含まれるかどうかを順番に判定しよう。

#### 入力値の取得
```Kotlin
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
```

#### 判定
0~2001の数のうち、入力された配列に含まれない最小の数を取得しよう。
```Kotlin
    val aSet = a.toSet()
    val ans = (0..2001).first { it !in aSet }
```
:::note info
`val aSet = a.toSet()` で配列をセット化する必要性については過去記事の [B - Hit and Blow](https://qiita.com/paragraph14/items/9fd971600087392e57da#blow-を計上しよう) を参照してください。
:::

#### サンプルコード
```Kotlin:main.kt
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    val aSet = a.toSet()
    val ans = (0..2001).first { it !in aSet }
    println(ans)
}
```

## [C - Choose Elements](https://atcoder.jp/contests/abc245/tasks/abc245_c)
#### やりたいこと
数列Xが存在する場合、その各要素は数列A、もしくは数列Bの同インデックスの要素となる。数列A及び数列Bの各要素について、その要素が数列Xの要素になる可能性があるかどうかを判定しよう。
![245_c_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/2a74b3bb-7f86-4756-d4a7-acd715ad3b03.png)

1. 数列Aならびに数列Bの最初の要素を、 **数列Xの要素になる可能性があると仮定してフラグを立てよう。**
![245_c_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/578c3331-bbf6-b489-3997-b004a71c7e47.png)
1. 数列Xの要素になる可能性がある場合、数列A及び数列Bの次の要素について **現在の要素との差の絶対値がK以内** になるかどうかを判定して、 **数列Xの要素になりうる場合はフラグ** を立てよう。
![245_c_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/85f0819d-b42d-4d09-c8ad-36d22518fff5.png)
1. 最終的に数列Aの最終要素と数列Bの最終要素、 **どちらか1つ以上にフラグがあれば数列Xは存在する。**
![245_c_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/e37cb173-aa1f-66ae-ecda-b09a0e2dd69c.png)

#### 入力値の取得
```Kotlin
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    // 数列A
    val a = readLine()!!.split(" ").map { it.toInt() }
    // 数列B
    val b = readLine()!!.split(" ").map { it.toInt() }
```

#### フラグの初期化
フラグを格納する配列を作成し、最初の要素にフラグを立てよう
```Kotlin
    // 数列Aの要素に対するフラグ
    val flagA = BooleanArray(n)
    // 数列Bの要素に対するフラグ
    val flagB = BooleanArray(n)
    // 先頭の要素は数列Xの要素になりうると仮定する
    flagA[0] = true
    flagB[0] = true
```

#### 2つ目以降の要素の処理
数列Aおよび数列Bの2つ目以降の要素に対して、それぞれが数列Xの要素になりうるかを判定して、なりうる場合はフラグを立てよう
```Kotlin
    // ひとつ目の要素のindexは0なので、2つ目以降を対象とする場合indexは1から開始する
    for (i in 1 until n) {
        // 一つ前のA要素が数列Xの要素になりうる場合の処理
        if (flagA[i - 1]) {
            // 差の絶対値がK以内になるかどうかでフラグを立てる
            if (Math.abs(a[i - 1] - a[i]) <= k) {
                flagA[i] = true
            }
            if (Math.abs(a[i - 1] - b[i]) <= k) {
                flagB[i] = true
            }
        }
        // 一つ前のB要素が数列Xの要素になりうる場合の処理
        if (flagB[i - 1]) {
            // 差の絶対値がK以内になるかどうかでフラグを立てる
            if (Math.abs(b[i - 1] - a[i]) <= k) {
                flagA[i] = true
            }
            if (Math.abs(b[i - 1] - b[i]) <= k) {
                flagB[i] = true
            }
        }
    }
```

#### 数列Xが存在しうるかを判定
数列Aの最終要素または数列Bの最終要素が数列Xの最終要素になりうるかを判定しよう。
```Kotlin
    // 数列Xが存在しうるかどうかの判定
    return flagA.last() || flagB.last()
```

#### サンプルコード
```Kotlin:main.kt
fun main(args: Array<String>) {
    println(if (solve()) "Yes" else "No")
}

fun solve(): Boolean {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    // 数列A
    val a = readLine()!!.split(" ").map { it.toInt() }
    // 数列B
    val b = readLine()!!.split(" ").map { it.toInt() }
    // 数列Aの要素に対するフラグ
    val flagA = BooleanArray(n)
    // 数列Bの要素に対するフラグ
    val flagB = BooleanArray(n)
    // 先頭の要素は数列Xの要素になりうると仮定する
    flagA[0] = true
    flagB[0] = true

    // ひとつ目の要素のindexは0なので、2つ目以降を対象とする場合indexは1から開始する
    for (i in 1 until n) {
        // 一つ前のA要素が数列Xの要素になりうる場合の処理
        if (flagA[i - 1]) {
            // 差の絶対値がK以内になるかどうかでフラグを立てる
            if (Math.abs(a[i - 1] - a[i]) <= k) {
                flagA[i] = true
            }
            if (Math.abs(a[i - 1] - b[i]) <= k) {
                flagB[i] = true
            }
        }
        // 一つ前のB要素が数列Xの要素になりうる場合の処理
        if (flagB[i - 1]) {
            // 差の絶対値がK以内になるかどうかでフラグを立てる
            if (Math.abs(b[i - 1] - a[i]) <= k) {
                flagA[i] = true
            }
            if (Math.abs(b[i - 1] - b[i]) <= k) {
                flagB[i] = true
            }
        }
    }
    // 数列Xが存在しうるかどうかの判定
    return flagA.last() || flagB.last()
}
```