Kotlinで競技プログラミングをするための高速化テクニックと注意点

長らく競技プログラミングにJavaで参加していたのですが、去年Kotlinに移行して以来簡潔な文法や豊富な言語機能に感動していまして、もっとKotlinユーザーが増えないかと記事を書くことにしました。

KotlinはC/C++やRust等には劣るものの、多くのアルゴリズム系のコンテストで困らない速度で動きます。ですが知っていないと解き方は合っているのに制限時間を超えてしまう注意点や、知っていると特にマラソン系コンテストで有利になるテクニックがいくつかあり、本記事ではそのあたりを自分用のメモも兼ねてまとめてみようと思います。

# 標準入力のReadが遅い

Kotlinでは`readLine`で標準入力を簡単に取れるためこれを使いたくなるのですが、残念ながら速度面では今ひとつで入力が$10^6$程度を超えてくると時間制限のリスクが出てきます。`BufferedReader`を使うか、高速な入力ライブラリを使いましょう。[^1]

```kotlin
fun testRead(){
    val timeA = measureTimeMillis { // ~1800 ms
        for (i in 1..10_000_000){
            val a = readLine()
        }
    }

    val timeB = measureTimeMillis { // ~250 ms
        val reader = System.`in`.bufferedReader()
        for (i in 1..10_000_000){
            val a = reader.readLine()
        }
        reader.close()
    }
}
```

# インスタンス生成に注意する

Kotlinでは`val`の導入に代表されるように変数をなるべくイミュータブルなものにし、副作用のないコードを書くことが目指されているように思います。これは品質の高いコードを書く上では有効に働くことが多いと思いますが、競技プログラミングではこれによって増えるインスタンス生成のコストやガベージコレクションにかかる時間が問題になることがあります。

回数の多いループの内側でのインスタンス生成は可能な限り避けましょう。計算結果を新しいインスタンスとして返す関数にも注意が必要です。

```kotlin
fun testFraction(){
    val timeA = measureTimeMillis { // ~600 ms
        var max = FractionA(0L, 1L)
        for (i in 1L..100_000_000L) {
            val f = FractionA(i, i + 1)
            if (f.larger(max)) max = f
        }
        println(max)
    }

    val timeB = measureTimeMillis { // ~200 ms
        val max = FractionB(0L, 1L)
        val f = FractionB(1, 1)
        for (i in 1L..100_000_000L) {
            f.set(i, i + 1)
            if (f.larger(max)) max.set(f.num, f.deno)
        }
        println(max)
    }
}

class FractionA(val num: Long, val deno: Long){
    fun larger(f: FractionA) = num * f.deno > f.num * deno

    override fun toString() = "$num/$deno"
}

class FractionB(var num: Long, var deno: Long){
    fun larger(f: FractionB) = num * f.deno > f.num * deno

    fun set(num: Long, deno: Long){
        this.num = num
        this.deno = deno
    }

    override fun toString() = "$num/$deno"
}
```

#標準の乱数生成が遅い

特にマラソン系コンテストでお世話になることが多い乱数生成ですが、標準の`Random`を大量に呼び出すとそのコストが問題になります。少しでも高速化したい場合は[XorShift](https://ja.wikipedia.org/wiki/Xorshift)のような高速な疑似乱数生成を使うと良いです。

```kotlin
fun testRandom(){
    val timeA = measureTimeMillis { // ~5300 ms
        val random = Random(0)
        for (i in 1..1_000_000_000) {
            val a = random.nextInt(i)
        }
    }

    val timeB = measureTimeMillis { // ~2400 ms
        val random = XorShiftRandom()
        for (i in 1..1_000_000_000) {
            val a = random.nextInt(i)
        }
    }
}
```

# ArrayListのAddとRemove

`ArrayList`の`add`にはIndexを指定する`add(index)`と末尾に追加する`add()`の2種類が、removeにはIndexを指定する`removeAt`とバージョン1.4で追加された`removeFirst`, `removeLast`の3種類があります。
この計5つのAPIのうち、定数時間で高速に動作するのは`add()`と`removeLast`の2つのみで、特に`removeFirst`と`removeLast`で動作速度が大きく異なるため注意が必要です。
競技プログラミングで使う上では低速な3つのAPIは$10^5$程度の要素数で危なくなると考えておけば良さそうです。

|API  |実行時間 ($10^5$要素) |実行時間 ($5×10^5$要素)  |
|---|---|---|
|add()  |~1 ms  |5 ms  |
|add(index)  |313 ms  |12710 ms  |
|removeAt(index)  |313 ms  |12751 ms  |
|removeFirst()  |314 ms  |13112 ms  |
|removeLast()  |~1 ms  |1 ms  |


#コンテストサイトごとの対応バージョン
Kotlinに限った話ではないですが、コンテストサイトが言語のどのバーションまで対応しているかには注意が必要です。本番で手元で動いていたコードがコンパイルエラーになると焦るので、念のため事前に見ておくと良いです。
2021年3月現在の各サイトの対応状況は以下の通りです。

| コンテストサイト | 対応バージョン |
|:-|-:|
| [AtCoder](https://atcoder.jp/home) | 1.3.71 |
| [Google Code Jam](https://codingcompetitions.withgoogle.com/codejam) / [Google Kick Start](https://codingcompetitions.withgoogle.com/kickstart) | 1.4.10 |
| [CodeForces](https://codeforces.com/) | 1.4.0 |


#参考・おすすめ記事
- https://qiita.com/naoppy/items/e9064b297efae1a89642  
Kotlinのメリットや特徴の紹介から競技プログラミングの問題を解いてみるまでがまとまっています。
- https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4  
Java向けの記事ですがKotlinにも通じる部分が多くとても参考になります。

---

書くことを思いつき次第随時更新していこうと思います。
ご意見ご指摘ありましたらコメントいただけると嬉しいです！

---

[^1]: 実行時間は全てノートPC（XPS13, core-i7 1065g7）のものです。厳密な条件調整は行っていませんので参考程度でお願いします。