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

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

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

## [B - Unique Nicknames](https://atcoder.jp/contests/abc247/tasks/abc247_b)
#### やりたいこと
それぞれの人間について以下の判定を行う
1. 該当人間の姓と同一の姓が該当人間以外に存在する or 該当人間の姓と同一の名前が該当人間以外に存在する
1. 該当人間の名前と同一の姓が該当人間以外に存在する or 該当人間の名前と同一の名前が該当人間以外に存在する

上記2条件を **全てを満たした場合** 該当人間は **ニックネームを作成できない**
N人の内、ニックネームを作成できない者の数が1人以上の場合「No」を出力、0人の場合「Yes」を出力

#### 入力値の取得
```kotlin
    // 入力値の取得
    val n = readLine()!!.toInt()
    // n人分の(姓,名）のリスト
    val st = (1..n).map { readLine()!!.split(" ") }
```

#### ニックネームを作成可能かどうかの判定
nの最大値が100と少ないため、愚直な実装で十分間に合う
```kotlin
    for (i in st.indices) {
        // nm: 処理対象となる（姓, 名）のリスト
        val nm = st[i]
        // 処理対象以外の姓のセット
        val s = st.indices.filter { it != i }.map { st[it][0] }.toSet()
        // 処理対象以外の名のセット
        val t = st.indices.filter { it != i }.map { st[it][1] }.toSet()
        if (nm.all { it in s || it in t }) {
            // 姓と名の両方が、処理対象以外の姓または名と同一のため、ニックネームを作成できない
        }
    }
```
#### サンプルコード
```kotlin:main.kt
fun main(args: Array<String>) {
    println(if (canUniqueNicknames()) "Yes" else "No")
}

fun canUniqueNicknames(): Boolean {
    // 入力値の取得
    val n = readLine()!!.toInt()
    // n人分の(姓,名）のリスト
    val st = (1..n).map { readLine()!!.split(" ") }
    for (i in st.indices) {
        // nm: 処理対象となる（姓, 名）のリスト
        val nm = st[i]
        // 処理対象以外の姓のセット
        val s = st.indices.filter { it != i }.map { st[it][0] }.toSet()
        // 処理対象以外の名のセット
        val t = st.indices.filter { it != i }.map { st[it][1] }.toSet()
        if (nm.all { it in s || it in t }) {
            // 姓と名の両方が、処理対象以外の姓または名と同一のため、ニックネームを作成できない
            return false
        }
    }
    // 全員ニックネームを作成できる
    return true
}
```
## [C - 1 2 1 3 1 2 1](https://atcoder.jp/contests/abc247/tasks/abc247_c)
#### やりたいこと
列$S_n$を求める関数を仮にF(n)とする。
n = 1 の時、F(n)は数列[1]を返す
n > 1 の時、F(n)はF(n-1) + [n] + F(n-1)を返す。
関数 **F(n)の中でF(n-1)が呼ばれる** 。
関数が自らを呼び出す**再帰処理**を実装しよう。

:::note warn
再帰処理は呼び出しの階層が100を超えるとエラーとなります。これはKotlinに限らず、多くの言語で共通する仕様です。今回はNの入力制限が最大16のため呼び出しの階層が100を超えることはありませんが、100を超えるような入力の場合は別の処理を考える必要があります。
:::

#### 入力値の取得
```kotlin
    // 入力値の取得
    val n = readLine()!!.toInt()
```
#### 関数F(n)の実装
引数nが1の場合は1を唯一の要素とする数列を返そう。
引数nが1より大きい場合はF(n-1) + [n] + F(n-1)を返そう。
```kotlin
fun f(n: Int): List<Int> {
    // 引数 n = 1 の場合は、1を唯一の要素とする数列を返す
    if (n == 1) {
        return listOf(1)
    }
    // 引数 n > 1 の場合は、f(n-1) + [n] + f(n-1)を返す
    val ret = mutableListOf<Int>()
    // f(n-1)の取得。同じ結果を2度使うので、一度変数に格納する。
    val tmp = f(n - 1)
    // 戻り値用数列にf(n-1)を追加
    ret.addAll(tmp)
    // 戻り値用数列に[n]を追加
    ret.add(n)
    // 戻り値用数列にf(n-1)を追加
    ret.addAll(tmp)
    return ret
}
```
#### サンプルコード
```kotlin:main.kt
fun main(args: Array<String>) {
    // 入力値の取得
    val n = readLine()!!.toInt()
    println(f(n).joinToString(" "))
}

fun f(n: Int): List<Int> {
    // 引数 n = 1 の場合は、1を唯一の要素とする数列を返す
    if (n == 1) {
        return listOf(1)
    }
    // 引数 n > 1 の場合は、f(n-1) + [n] + f(n-1)を返す
    val ret = mutableListOf<Int>()
    // f(n-1)の取得。同じ結果を2度使うので、一度変数に格納する。
    val tmp = f(n - 1)
    // 戻り値用数列にf(n-1)を追加
    ret.addAll(tmp)
    // 戻り値用数列に[n]を追加
    ret.add(n)
    // 戻り値用数列にf(n-1)を追加
    ret.addAll(tmp)
    return ret
}
```
## [D - Cylinder](https://atcoder.jp/contests/abc247/tasks/abc247_d)
#### やりたいこと
筒の右側からボールを入れる、取り出すときは筒の左側から。
先に入れたものが取り出し時に先に取り出される、FIFO（ファースト・イン・ファースト・アウト）でデータを保持するQueueを使おう。
![abc247_d_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/f4e28673-fdc7-5ae6-44b8-5ebf1fd6d1bf.png)
Kotlinで使えるQueueはいくつかあるけれど、ここではシンプルで動作の軽い **LinkedList** を使っていこう。
#### 入力値の取得
```kotlin
    val q = readLine()!!.toInt()
    repeat(q) {
        val query = readLine()!!.split(" ").map { it.toInt() }
        if (query[0] == 1) {
            // 筒にボールを入れるクエリの処理
        } else {
            // 筒からボールを取り出すクエリの処理
        }
    }
```

#### ボールのデータを保持するクラスの作成
1回のクエリでボールは最大$10^9$個追加される。一つずつ処理することはできないので、一度のクエリで追加されるボールは一つのオブジェクトにまとめよう。
![abc247_d_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/0470c25a-5359-51af-53e9-0f0852dc3e60.png)
```kotlin
// number: ボールに書いてある数字、count: ボールの個数
class Ball(val number: Int, var count: Int)
```

#### 筒のデータを保持するQueueの作成
Ballクラスのオブジェクトを内部に保持するLinkedListを作成しよう。
```kotlin
    // 筒のデータを保持するQueue
    val queue = LinkedList<Ball>()
```

#### クエリの処理（ボール追加）
クエリで読み込んだ数列の最初の要素が1であった場合に筒にボールを追加する処理を実装しよう。
```kotlin
        val query = readLine()!!.split(" ").map { it.toInt() }
        if (query[0] == 1) {
            // 筒にボールを入れるクエリの処理
            queue.add(Ball(query[1], query[2]))
        } else {
            // 筒からボールを取り出すクエリの処理
        }
```
#### クエリの処理（ボール取り出し）
クエリで読み込んだ数列の最初の要素（入力制約的に1か2しかあり得ない）が1以外であった場合に筒からボールを取り出し、取り出したボールに書かれた数の合計値を出力する処理を実装しよう。
```kotlin
        if (query[0] == 1) {
            // 筒にボールを入れるクエリの処理
            queue.add(Ball(query[1], query[2]))
        } else {
            // 筒からボールを取り出すクエリの処理
            // 取り出したボールに書かれた数の合計値を格納する変数
            var total = 0L
            //　取り出さなければならない残りボールの数
            var remain = query[1]
            while (remain > 0) {
                // queueの先頭要素から取り出すべきボールの数を決定する
                val removeCount = Math.min(remain, queue.peek().count)
                // queueの先頭要素から取り出したボールの数*ボールに書かれた数字を合計値に加える
                total += queue.peek().number.toLong() * removeCount
                // 取り出さなければならない残りボール数を減らす
                remain -= removeCount
                // queueの先頭要素から取り出したボール数分のcount値を減らす
                queue.peek().count -= removeCount
                if (queue.peek().count <= 0) {
                    // 先頭要素のcountが0になった場合、queueから取り除く
                    queue.pop()
                }
            }
            // 取り出したボールに書かれた数の合計値を出力
        }
```
:::note info
**peek()** と **pop()**　について。
両者はどちらもqueueの先頭要素を返します。
pop()は先頭要素を返した上で**queueから削除**するのに対し、peek()は先頭要素をqueueから**削除しません**。
単純に先頭から一つずつ処理していくときはpop()を、参照だけしたいときはpeek()等、状況によって使い分けましょう。
:::
:::note warn
int と int の演算について
`total += queue.peek().number.toLong() * removeCount` で toLong()の処理をしていますが、これはnumberの最大値とremoveCountの最大値が共に$10^9$であり、乗算すると場合によってはIntの最大値を超えてオーバーフローとなるため、toLong()でそれを回避しています。
:::

#### サンプルコード
データの出力について、出力行数が極端に多い場合1行ずつ `println()`で出力するとTLEとなる場合がある。出力行数が多いとき（大体1万行を超えそうなとき）は StringBuilder に一旦格納して、最後にまとめて出力しよう。
```kotlin:main.kt
import java.lang.StringBuilder
import java.util.*

fun main(args: Array<String>) {
    val q = readLine()!!.toInt()
    // 筒のデータを保持するQueue
    val queue = LinkedList<Ball>()
    // 最終的な出力を保持するStringBuilder
    val ans = StringBuilder()
    repeat(q) {
        // クエリの読み込み
        val query = readLine()!!.split(" ").map { it.toInt() }
        if (query[0] == 1) {
            // 筒にボールを入れるクエリの処理
            queue.add(Ball(query[1], query[2]))
        } else {
            // 筒からボールを取り出すクエリの処理
            // 取り出したボールに書かれた数の合計値を格納する変数
            var total = 0L
            //　取り出さなければならない残りボールの数
            var remain = query[1]
            while (remain > 0) {
                // queueの先頭要素から取り出すべきボールの数を決定する
                val removeCount = Math.min(remain, queue.peek().count)
                // queueの先頭要素から取り出したボールの数*ボールに書かれた数字を合計値に加える
                total += queue.peek().number.toLong() * removeCount
                // 取り出さなければならない残りボール数を減らす
                remain -= removeCount
                // queueの先頭要素から取り出したボール数分のcount値を減らす
                queue.peek().count -= removeCount
                if (queue.peek().count <= 0) {
                    // 先頭要素のcountが0になった場合、queueから取り除く
                    queue.pop()
                }
            }
            // 取り出したボールに書かれた数の合計値をStringBuilderに格納
            ans.appendln(total)
        }
    }
    // 最後にまとめて出力
    print(ans.toString())
}

// number: ボールに書いてある数字、count: ボールの個数
class Ball(val number: Int, var count: Int)
```