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

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

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

標準入力のReadが遅い

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

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

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

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のような高速な疑似乱数生成を使うと良いです。

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	1.3.71
Google Code Jam / Google Kick Start	1.4.10
CodeForces	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）のものです。厳密な条件調整は行っていませんので参考程度でお願いします。 ↩