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

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

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

入力編

基本

Kotlinでは、JavaのScannerを使うことができます。

import java.util.*

fun main() {
    val scanner = Scanner(System.`in`)
    val n = scanner.nextInt()
}

しかし、Kotlinで標準で用意されているreadLine()を使ったほうがいいでしょう。

val n = readLine()!!.toInt()

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

val n = readLine()?.toInt() ?: 0

KotlinのNull許容型まわりの詳しい解説は【Null安全】Kotlin Java比較メモ 正しいNull安全の使い方などを参考にしてください。

リスト

値のまとまりを入力して何かをするというアルゴリズムの問題も多いと思います。いくつかのパターンを挙げて解説していきます。

1. 一行に要素が空白区切りで渡される場合

例えば以下の様な入力があった場合です。

5 // 要素数
2 6 1 4 3 // 要素のまとまりが空白区切りで入力される

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

readLine() // 要素数を取得する必要はないため変数に代入しない
val list = readLine()!!.split(" ").map(String::toInt)

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

5 2 6 1 4 3

// 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は以下のようにして生成と値の代入を同時に行うことができます。

val n = readLine()!!.toInt()
val list = List(n) {
    readLine()!!.toInt()
} // 2 6 1 4 3

上の例ではListが生成されます。Listのクロージャの最後の行の値がリストに入るので、クロージャ内で一旦入力を変数に格納し、それをもとに別のクラスのインスタンスを生成しそれのリストにすることもできます。僕が実際にある問題を解いたときのコードを載せます。

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クラスのインスタンスを生成しそれをリストの要素に入れています。

出力編

基本

print("Foo")
println("Bar")
println("FooBar")
// 出力:
// FooBar
// FooBar

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

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という方法で書くこともできます。

val a = 2
val b = 3
println("$a + $b = ${a + b}") // 2 + 3 = 5

IntやDoubleなどで桁数指定をしたいときは、Stringに用意されているメソッドformatを使います。

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

リスト

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

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を出力する例を載せます。

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より若干早いです。

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()するほうが若干早いです。

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を組み合わせて使うほうが早い可能性があります。

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を使う

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

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競技プログラミングメモ

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

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

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