Kotlin で競技プログラミングをやる上での注意点
Kotlin はプログラミングコンテスト ICPC で使用可能な言語の 1 つであり、また Kotlin 限定のプログラミングコンテストも開催されたことがあるなど、競技プログラミングにおいては注目の言語の 1 つです。
この記事では Kotlin を使って競技プログラミングに取り組む際の注意点を述べていきます。随時更新予定です。
バージョンに気を付けよう
Kotlin に限った話ではないですが、コンテストサイトで使われている言語のバージョンに気を付けましょう。バージョンが古い場合、使いたい機能が使えないことがあります。
参考までに、2022 年 10 月 6 日現在の Kotlin のバージョンを記録します。
- 最新版: 1.7.20
- AtCoder: 1.3.71
- Codeforces: 1.6.10
- yukicoder: 1.6.10
- AOJ: 1.1.60
バージョンの違いによりどのような差が出るかは下のほうで解説していきます。
main 関数の引数
Kotlin のもっとも基本的なプログラムは次のようなものです。
fun main(args: Array<String>) {
println("Hello world!")
}
Kotlin 1.3 以降では main 関数の引数を省略できます。それ以前ではできないので注意しましょう。
fun main() {
println("Hello world!")
}
max と maxOrNull
配列の最大値を取得したい場合、Kotlin 1.4 以降では maxOrNull を用います。
val arr = arrayOf(1, 5, 3)
val m = arr.maxOrNull() ?: -1
名前の通り null を返す場合があります。null を返すのは配列が空のときです。
この関数は 1.3 以前では max という名前でした。そのため AtCoder や AOJ では注意が必要です。
なお、1.7 からは再び max という関数が復活しています。この関数は過去の max と違い、空の場合に例外を投げるようになっています。
木上の再帰
競技プログラミングでは木の上で再帰 DFS をすることがあります。その際、Kotlin では普通に実装をするとすぐにスタックオーバーフローをしてしまいます。
そこで、スタックオーバーフローしないよう次のようにプログラムを書く必要があります。
fun solve() {
// ここにプログラムを書く
}
fun main() {
Thread(null, {
solve()
}, "solve", 1.shl(26)).start()
}
変更したものがこちらになります。(無事 RE から AC になりました)
ただし本来 RE になるはずのコードが WA になってしまうなど、注意が必要です。筆者の普段のコードはその辺りも対策しています。
なお、1.7 からは DeepRecursiveFunction という機能が追加されています。検証していないので、競技プログラミングで使えるかはわかっていません。
Set の最小値・最大値
Set あるいは MutableSet はよく使用されます。
val set = mutableSetOf(1, 1, 2, 3)
println(set.maxOrNull())
この Set は HashSet です。最小値・最大値の取得には要素数に比例した時間がかかってしまいます。最小値・最大値を高速に取得したい場合は TreeSet を使います。
val set = TreeSet<Int>()
set.add(3)
set.add(1)
set.add(4)
println(set.first())
println(set.last())
first() で最小値、last() で最大値が求まります。min(), max() でも最小値・最大値が求まりますが、時間がかかってしまうことに注意してください。また、HashSet の first(), last() は最小値・最大値を返しません。
キューは ArrayDeque を使う
スタックは次のように使います。
val stack = Stack<Int>()
stack.push(1)
val a = stack.pop()
一方キューは少し変更して次のように使います。
val queue: Queue<Int> = ArrayDeque()
queue.add(1)
val a = queue.poll()
ArrayDeque の代わりに LinkedList を使っても動きますが、遅くなると思われます。
ボクシング
整数の配列を扱うには Array<Int> または IntArray を用いますが、ボクシングの関係上 IntArray のほうが一般に高速です。LongArray や CharArray もあります。
以下の記事も参考にしてください。
binarySearch は lower_bound ではない
配列が昇順に並んでいるとき、二分探索で要素を見つけることができます。
val a = arrayOf(1, 3, 5, 7, 9)
println(a.binarySearch(3)) // 1
println(a.binarySearch(4)) // -3
要素が存在する場合はそのインデックスを返します。存在しない場合は、インデックス
ただし同じ値が複数存在する場合は注意が必要です。左端・右端のインデックスを返すとは限りません。
val a = arrayOf(1, 2, 2, 3, 3, 3)
println(a.binarySearch(2)) // 2
println(a.binarySearch(3)) // 4
ここが C++ における lower_bound との違いです。
募集中
他にも Kotlin で競技プログラミングをする上で気を付けるべきことがあればお知らせください。
Discussion