Posted at

Kotlinで競技プログラミングをしてみたらめっちゃ快適だった話

私は2年ほどJavaで競技プログラミング(以下競プロ)をしていたのですが、この前勉強ついでにKotlinで競プロをやってみました。

快適すぎて感動したのでJavaで競プロをしている人や、これから競プロを始める人に布教しようと思い至りました。

気づいた点などあれば気軽にコメントなどでご指摘ください。


始めに

image.png

この順番で説明していきます。


  • Kotlinという言語の特徴

  • おさえておくべき文法

  • 競プロでどう使うか

  • プログラム例


Kotlinとは

Better Java。最強のIDE開発会社JetBrainsが自社で開発した言語です。以下のような特徴があります。


洗練された文法

Kotlinは簡潔な言語です。偉い人の言葉を借りると、「簡潔とは、出来る限り書いた全てのコードが意味を持つこと」です。

KotlinではJavaで生まれるボイラープレートのほぼ全てを文法によって綺麗に解決します。


型システム

Kotlinでは値がnullになり得るかどうか(nullability)を型に組み込んでいます。

後ほど説明しますが、NullPointerException(ぬるぽ)に悩まされることはないでしょう。


強力なIDEサポート

JetBrains謹製の言語ということはJetBrainsのIDEとズブズブということです。つまり、非常に強力なIDEサポートを受けられます。

「この書き方はあまり良くない」といった警告から、「この書き方はこう書き換えられるよ~」といった高度なことまでIDEに教えてもらえるので、初学者でもいい感じのコードが書けます。


Javaからの移行のしやすさ

Kotlinの標準ライブラリは、後ほど説明する拡張関数などの機能を使って補強されたJavaの標準ライブラリと、Kotlinの独自パッケージからなっています。

そのため、Javaを使っていた人は今までと同じコレクションクラスやAPIを利用することができます。


おさえておくべき文法


セミコロン不要

Javaと違い、ほぼ全ての場所でセミコロンを使う必要はありません。

厳密には、enumの宣言でのみセミコロンが必要です。(わからなくても大丈夫です)


変数宣言

一度しか代入できない変数と、何度でも代入できる変数を明確に区別します。

// 一度しか代入できない変数の宣言

// val 変数名: 型名 = 値 (セミコロン不要)
val s: String = "Hello, World!"

// 何度も代入可能な変数の宣言
// var 変数名: 型名 = 値 (セミコロン不要)
var i: Int = 10
i = 1 //iはvarで宣言されたので変更可能

基本的にvalを使いましょう。型名は代入式の右辺から推論できる場合、以下のように省略可能です。

val s = "Hello, World"

var i = 10 //Int型になる

image.png

IDEでリテラル、クラスのコンストラクタを直接呼ぶ場合は型は省略すべきです。

それ以外、コンストラクタ以外の関数からの値を代入する場合は型を明示しても省略してもいいと思います。

私は画像の通り、IDEの型ヒントを表示する機能を使っているので、型は全て省略して書いています。


型システム


1つのクラスから2つの型が生まれる話

Javaでは、クラスAから作られる型Aの変数は、実際には型Aの値以外に、nullも入れることが可能です。

String nonnullString = "Hello, Hell of Null";

String nullableString = null;

例としてあげたこのコードでは、どちらもString型であるにもかかわらず、String型の値以外に、null値を入れることができることを示しています。

このことがNullPointerExceptionを引き起こします。

Kotlinではそうはいきません。

val nonNullString: String   = "Hello, Peaceful World!"

val nullableString: String? = null

型名をよく見るとString型とString?型があることに気づくと思います。

KotlinではString型にはString型の値しか入れることができません。nullを入れられるようにするには、型名の後ろに「?」を付けます。

nullを入れられない型をnull非許容型、入れられる型をnull許容型といいます。

自分の足を銃で打ち抜きたくないならば、よっぽどのことが無い限りnull非許容型を使うべきです。

ここでは解説しませんが、nullを上手く扱う構文が用意されており、面倒なnullチェックからは解放されます。

ここに詳しい説明があります。https://re-engines.com/2018/11/01/3088/


voidの代わりとか

JavaのvoidにあたるものはKotlinではUnitといいます。

voidとUnitはちょっと違いがあって、色々利点があるんですけどここでは解説しません。


関数定義

funキーワードによって宣言します。Kotlinコードを書くことは楽しさに満ち溢れているという暗示です。

可視性はデフォルトでpublicです。

fun 関数名(変数名: 型名): 戻り値の型名 {

//処理
return hoge
}

引数はvalになります。

何の面白みもない例 ↓

fun plus10(x: Int): Int {

return x + 10
}

引数はデフォルト値を持てます。これはJavaでの大量のオーバーロードなどのボイラープレートを消します。

fun printHello(message: String = "Hello, World", postfix: String = "!") = println(message + postfix)

fun main(args: Array<String>) {
printHello() // => Hello, World!
printHello("記事長すぎてごめんなさい") //=> 記事長すぎてごめんなさい!
}

Kotlinは沢山の省略構文を用意しています。


Unit系の省略構文

関数の戻り値がUnitの場合、戻り値の型もreturn文も省略できます。

以下の2つの関数は同値です。

fun returnUnit(): Unit {

return Unit
}
fun returnUnit2() {}


波括弧を省略

式が一つだけの関数というのは割とよくあります。その場合イコールを使い、関数の戻り値や波括弧を省略できます。

UnionFindの関数の一部を例に出してみます。(競プロっぽいので)

//findの定義は気にしないで

fun hasSameRoot(x: Int, y: Int) = find(x) == find(y)

fun size(k: Int) = -data[find(k)]


ラムダを渡す場合

KotlinではJava以上にラムダを使う機会があります。

このとき、引数にそのままラムダを渡すと括弧地獄が始まります。

listOf(1, 2, 3).joinToString(",", "list:", transform = {x -> "Number of $x" })

関数の引数に渡す最後のラムダは、外に出すことができるという省略構文があります。これを使って書き直すと

listOf(1, 2, 3).joinToString(",", "list:") {x -> "Number of $x" }


ラムダの引数名を省略

前述の関数は暗黙のラムダの引数itを用いてさらに短くなります。

listOf(1, 2, 3).joinToString(",", "list:") { "Number of $it" }


拡張関数

誰かが作ったクラスに自分で勝手にメソッドを生やせたら幸せですよね?

Kotlinではそれが可能です。これによってJavaの標準ライブラリをめっちゃ強化してます。

詳細は省略します。


データクラス

クラス定義に使うclassキーワードの前にdataを付けて、data class Hoge(~) {~}宣言すると、hashCode(), equals(), copy(), toString()などの関数が自動生成されます。

これは多くのボイラープレートを取り除きます。めっちゃ楽。

data class Point(val x: Int, val y: Int)

fun main(args: Array<String>) {
val p1 = Point(10, 20)
val p2 = Point(30, 40)
println(p1.equals(p2)) //=> false
println(p1.toString()) //=> Point(x=10, y=20)
println(p1.copy(x = 5)) //=> Point(x=5, y=20)
}


競プロで使うコード達


main関数

Javaの大量のおまじないと違い、kotlinのmain関数は非常に簡潔

fun main(args: Array<String>) {

//ここに書いていく
}


入力


一行の数字の入力

readLine()は一行読み取りString?型を返します。!!演算子によってString?型をString型に変換しています。

!!演算子はこれがnullになるわけがないのでnull非許容型にしろ!nullならクラッシュするべきだ、という演算子です。

toInt()で数字に変換しています。

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


n個の数字が一行にある入力

val list: List<Int> = readLine()!!.split(" ").map { it.toInt() }


n行続く数字の入力

val arr: Array<Int> = Array(n) {

readLine()!!.toInt()
}


出力


数字や文字列を出力する

println()という関数を使う。

println("Hello")


ListやArrayの中の要素をスペース区切りで一行に出力する

joinToString()という関数が非常に便利(引数の説明は省略)

val list = listOf(1, 2, 3)

println(list.joinToString(" "))


実際に問題を解くコード例

ABC065のD問題を解いていきます。

この問題でのアルゴリズムを簡単に説明すると


  • 整数nを入力

  • n個のノードを作成

  • 辺を入れるリストを作成

  • ノードをxでソートする

  • 辺を作ってリストに入れる

  • ノードをyでソートする

  • 辺を作ってリストに入れる

  • 最小全域木を作る(UnionFind利用)

import java.util.*

fun main(args: Array<String>) {
val n = readLine()!!.toInt()
val nodes: Array<Node> = Array(n) { i ->
readLine()!!.split(" ").map { it.toInt() }.let { Node(i, it[0], it[1]) }
}
val edges: ArrayList<Edge> = ArrayList(2 * n)
nodes.sortBy { it.x }
for (i in 0 until n - 1) {
val a = nodes[i]
val b = nodes[i + 1]
val d = b.x - a.x
edges.add(Edge(a.id, b.id, d))
}
nodes.sortBy { it.y }
for (i in 0 until n - 1) {
val a = nodes[i]
val b = nodes[i + 1]
val d = b.y - a.y
edges.add(Edge(a.id, b.id, d))
}
edges.sortBy { it.dist }
var d = 0L
val uf = UnionFind(n)
edges.forEach {
if (!uf.hasSameRoot(it.from, it.to)) {
d += it.dist
uf.unite(it.from, it.to)
}
}
println(d)
}

data class Node(val id: Int, val x: Int, val y: Int)

data class Edge(val from: Int, val to: Int, val dist: Int)

class UnionFind(size: Int) {
private val data: Array<Int> = Array(size) { -1 }

fun unite(x: Int, y: Int) {
val x = find(x)
val y = find(y)
if (data[x] > data[y]) {
val temp = data[x]
data[x] = data[y]
data[y] = temp
}
data[x] += data[y]
data[y] = x
}

fun find(k: Int): Int {
if (this.data[k] < 0) return k
data[k] = find(data[k])
return data[k]
}

fun hasSameRoot(x: Int, y: Int) = find(x) == find(y)

fun size(k: Int) = -data[find(k)]
}

val, varの使い分け、ラムダを多く使ったプログラミング、式が一つだけの関数の省略構文、データクラスの利用、型の省略などが見てとれると思います。

このコードはKotlin初めて3日目ぐらいで書きました。


最後に

なんかクッソ長い記事になってしまった。


  • 人の提出コード見ようとしたら大量のマクロやオレオレな書き方がしんどい。

  • セグフォやぬるぽでクラッシュする。


  • public static void main(String[] args) {という文字列にアレルギーがある。

  • 複雑なソート条件を表現する際に綺麗に書けずイライラする。

  • コンパイラの頭が悪い。

  • 型で優しく守られたい。

などの症状を感じたら、競プロでKotlinを使ってみるといいかもしれません。

Kotlinは楽しい!


See also

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

Kotlinイン・アクション