Kotlinでアルゴリズムの問題を解く際のTips集

大学でアルゴリズムとデータ構造という科目があり、課題がAizu Online Judgeで出されていたのでKotlinで解きました。その際に得た知見をまとめてみようと思います。
当方は競プロ勢ではなくKotlinでコンテストに出たこともないので、記事の内容も非効率なものかもしれません。コメントなどで遠慮なくご指摘ください。

はじめに基本的な入出力を紹介し、高速化編でより早い入出力の例を紹介しています。後日他の項目も追加するかもしれません。

# 入力編
## 基本
Kotlinでは、JavaのScannerを使うことができます。

```kotlin
import java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
}
```
しかし、Kotlinで標準で用意されている`readLine()`を使ったほうがいいでしょう。

```kotlin
val n = readLine()!!.toInt()
```
`readLine()`は標準入力から一行読み込み、`String?`(StringのNull許容型)を返します。
Stringには`toInt()`や`toDouble()`などのメソッドが用意されているので、それを使い目的の型に変換します。
`readLine()`の戻り値が`String?`ですが、今回はAOJやAtCoderなどでアルゴリズムの問題を解く状況を想定しているので`readLine()!!.toInt()`でreadLine()の`String?`を`String`に強制アンラップしています。個人的には以下の書き方が好みですが、今回の記事では上の強制アンラップを使うやり方で解説していこうと思います。

```kotlin
val n = readLine()?.toInt() ?: 0
```
KotlinのNull許容型まわりの詳しい解説は[【Null安全】Kotlin Java比較メモ 正しいNull安全の使い方](https://qiita.com/farman0629/items/e8b9bd6fc22d5fa9cfea)などを参考にしてください。

## リスト
値のまとまりを入力して何かをするというアルゴリズムの問題も多いと思います。いくつかのパターンを挙げて解説していきます。
### 1. 一行に要素が空白区切りで渡される場合
例えば以下の様な入力があった場合です。

```
5 // 要素数
2 6 1 4 3 // 要素のまとまりが空白区切りで入力される
```
C言語などを使う場合、一旦要素数を読み込みその分for文を回して配列に値を入れていくというパターンが多いと思いますが、KotlinにはStringクラスに`split`という区切り文字を指定して文字列を分割する便利なメソッドが用意されているため、2行目を読み込むだけでリストを作成することができます。

```kotlin
readLine() // 要素数を取得する必要はないため変数に代入しない
val list = readLine()!!.split(" ").map(String::toInt)
```
`split`で半角スペースを区切り文字に指定しています。`split`は`List<String>`を返すため、`map(String::toInt)`で`List<Int>`に変換しています。
また、入力が1行で先頭に要素数を入力しその後空白区切りで要素を入力するというパターンの場合、以下のようにして書くことができます。

```
5 2 6 1 4 3
```

```kotlin
// val list = readLine()!!.split(" ").let { it.subList(1, it.size) }.map(String::toInt)
val list = readLine()!!.split(" ").drop(1).map(String::toInt)
```
~~`let`というスコープ関数内で元のリストの先頭を取り除いたサブリストを生成しています。
`let { it.subList(1, it.size) }`は`run { subList(1, size) }`にしても同じことができます。また、`map`以降の操作も`let`(または`run`)のブロック内に記述しても同じように動作します。このあたりはお好みでどうぞ。~~
コメントにてsikaniさんにご指摘を頂きました。`drop`を使うほうが簡潔でわかりやすくいいと思います。
### 2. 要素数nを入力し、続くn行に要素を入力していく場合
例えば以下の様な入力があった場合です。

```
5 // 要素数n 以下にn行入力が続く
2
6
1
4
3
```

C言語などの場合1と同じく要素数を読み込みその分for文を回して配列に値を入れていくというパターンになるかと思いますが、KotlinのListやArrayは以下のようにして生成と値の代入を同時に行うことができます。

```kotlin
val n = readLine()!!.toInt()
val list = List(n) {
    readLine()!!.toInt()
} // 2 6 1 4 3
```
上の例ではList<Int>が生成されます。Listのクロージャの最後の行の値がリストに入るので、クロージャ内で一旦入力を変数に格納し、それをもとに別のクラスのインスタンスを生成しそれのリストにすることもできます。僕が実際にある問題を解いたときのコードを載せます。

```kotlin
val nodeList = List(readLine()?.toInt() ?: 0) {
    val input = readLine()?.split(" ".toRegex())?.map(String::toInt) ?: listOf()
    Node(input[0], input.subList(2, 2 + input[1]))
}
```
この例では僕が独自に定義したNodeクラスのインスタンスを生成しそれをリストの要素に入れています。

# 出力編
## 基本

```kotlin
print("Foo")
println("Bar")
println("FooBar")
// 出力:
// FooBar
// FooBar
```
Kotlinの出力には改行なしの`print`と改行ありの`println`があります。
使い方はJavaの`System.out.print()`や`System.out.println()`と同じです。(内部でJavaのそれを呼び出している)
`String`以外のオブジェクトを入れた場合自動的に`toString()`されて出力されます。つまり、独自に定義したクラスでも`toString()`をオーバーライドして望む形で返すようにすればそのように出力されます。

```kotlin
fun main() {
    val hoge = Hoge("hoge", 100)
    println(hoge) // hoge, 100
}

class Hoge(val str: String, val num: Int) {
    override fun toString() = "$str, $num"
}
```
上の例でも使いましたが、Kotlinでの文字列結合はJavaのような`+`で結合する方法に加え、String Templateという方法で書くこともできます。

```kotlin
val a = 2
val b = 3
println("$a + $b = ${a + b}") // 2 + 3 = 5
```
`Int`や`Double`などで桁数指定をしたいときは、`String`に用意されているメソッド`format`を使います。

```kotlin
val pi = 3.14159265
println("%.2f".format(pi)) // 3.14
```

## リスト
Kotlinに限らず、JVM言語でアルゴリズムの問題を解く上での一つの壁として、出力が遅いということがあります。
リストを出力する際には、ループで回して1要素ずつ出力するのではなく、事前にリストを結合して1回の出力で終わるようにしましょう。
Kotlinの`List`などが継承している`Iterable`インターフェースや、各種`Array`には、`joinToString`というメソッドが用意されています。

```kotlin
fun <T> Iterable<T>.joinToString(
    separator: CharSequence = ", ", 
    prefix: CharSequence = "", 
    postfix: CharSequence = "", 
    limit: Int = -1, 
    truncated: CharSequence = "...", 
    transform: (T) -> CharSequence = null
): String
```

|引数|説明|デフォルト値|
|---|---|---|
|`separator`|区切り文字          |`, ` |
|`prefix`   |先頭に設定する文字列 |`""` |
|`postfix`  |末尾に設定する文字列 |`""` |
|`limit`    |連結する要素の最大値 |-1   |
|`truncated`|省略された要素の表記 |`...`|
|`transform`|各要素を任意の値に変換する処理|`null`|

よく使うのが`separator`です。これに`"\n"`を指定すれば1行ごとに改行されます。出力するときに値をいじる必要があるときは`transform`で操作します。`transform`は殆どの場合クロージャで書くと思います。
以下にFizzBuzzを出力する例を載せます。

```kotlin
println(
    (1..100).joinToString(separator = "\n") {
        when {
            it % 15 == 0 -> "FizzBuzz"
            it % 3 == 0 -> "Fizz"
            it % 5 == 0 -> "Buzz"
            else -> it.toString()
        }
    }
)
```
たったこれだけで100行のFizzBuzzの出力ができます。ループを回して出力するより遥かに手軽で高速です。

# 高速化編

競技プログラミングでJVM言語を使う欠点として、入出力でのTLEやMLEが起こりやすいことが挙げられます。
以下に自分が実際にAOJの問題を解く上で起きた問題とその解決策を載せていきます。

## 1. 入力が多い

入力をリストで渡すような問題で、入力数が膨大なケースがあると思います。こういった問題では特にTLEが起きやすいです。
この場合に試せる解決策をいくつか紹介します。

### `String`を数値に直すときに`Integer.parseInt`を使う

Javaの`Integer`に`parseInt`というstaticメソッドがあり、Kotlinの`String`の`toInt`より若干早いです。

```kotlin
fun main() {
    val inputs = (1..100000).map(Int::toString)
    val time1 = measureTimeMillis {
        inputs.map(String::toInt)
    }
    val time2 = measureTimeMillis {
        inputs.map(Integer::parseInt)
    }
    
    println("toInt: ${time1}msec") // toInt: 12msec
    println("parseInt: ${time2}msec") // parseInt: 4msec
}
```

### `System.in.bufferedReader()`を使う

Kotlinの`readLine()`より、Javaの`System.in`の`BufferedReader`を生成してそこから`readLine()`するほうが若干早いです。

```kotlin
fun main() {
    val reader = System.`in`.bufferedReader() // inは予約語のためバッククォートでエスケープする
    val time1 = measureTimeMillis {
        repeat(100000) {
            readLine()
        }
    }
    val time2 = measureTimeMillis {
        repeat(100000) {
            reader.readLine()
        }
    }
    println("readLine: ${time1}msec") // readLine: 118msec
    println("reader.readLine: ${time2}msec") // reader.readLine: 12msec
}
```

### あえて`Scanner`を使う

空白区切りで1行で渡される入力は`String`の`split`でリストを直接生成するというやり方を今までの例でも使ってきましたが、これで生成できるリストはイミュータブルなので、要素の入れ替えや変更などの破壊的操作ができません。Kotlinのリストは`toArray`など配列に変換するためのメソッドが用意されているため、ソートなどのリストの破壊的変更を行うときはそれを使う場合が多いと思います。
しかし、リストを配列に変換する処理は時間がかかるため、入力ケースによってはTLEが起こることもあります。
この場合は、入力のリストのケース2で紹介した方法と`Scanner`を組み合わせて使うほうが早い可能性があります。

```kotlin
val scanner = Scanner(System.`in`)
val n = scanner.nextInt()
val array = IntArray(n) {
    scanner.nextInt()
}
```

`scanner.nextInt()`のかわりに`Integer.parseInt(scanner.next())`を使うとまた少し高速化できます。また、Javaの標準の`Scanner`のかわりに独自にFastScannerのようなものを定義して使うのもいいと思います。

## 2. 出力で`joinToString`が使えない
自分でスタックやキュー、双方向連結リストなどを実装する問題など、リストを出力したいけど`joinToString`が使えない場合があります。しかし、１つずつ`print`していくのは効率が悪いです。

### `StringBuilder`を使う

僕が双方向連結リストの問題を解いたときのコードの一部を例として載せます。

```kotlin
override fun toString(): String {
    var element = nil.next
    val strBuilder = StringBuilder()
    while (element != nil) {
        strBuilder.append(element?.value)
        strBuilder.append(" ")
        element = element?.next
    }
    strBuilder.deleteCharAt(strBuilder.lastIndex)
    return strBuilder.toString()
}
```
`StringBuilder`の`append`で要素を追加していき、`toString()`でStringにしています。
末尾に空白文字を入れたくない場合も`deleteCharAt`で簡単に削除できます。

# あとがき

KotlinからはJavaの標準ライブラリを使うことができるので、Javaの競プロのTipsもそのまま使える場合が多いです。そちらも参考にしてみてください。
[Java競技プログラミングメモ](https://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b)

また、今回紹介したTipsは実際の開発では可読性などの観点でそのまま使うのはよくないかもしれません。

「こういった場合はどうすればいいの？」という疑問があればコメントしていただけるとお答えできる…かも？しれません。

それでは良きKotlinライフを！