初めまして。mikhailです。
これまでずっとJavaで競技プログラミングをやっていたのですが、いわゆる"Better Java"と呼ばれるKotlinにふと興味が湧き、ここ数日Javaからの移行作業に勤しんでいました。
自作ライブラリのKotlinへの移植、おわり！！！！！ Javaで700行以上あったテンプレートが200行まで縮まった！！！！！！ pic.twitter.com/1jl9KVWdJD
— mikhail (@mikhail_kyopro) March 20, 2020
今回は表題の通り、AtCoder Beginners Selectionの問題（AtCoderに登録したら解くべき精選過去問10問）を解いたことで得られた知見をまとめてみようと思います。
1問目 ABC086A - Product
問題のリンク
考察
標準入力と条件分岐の問題ですね。
競プロ慣れしていれば瞬殺できる問題ですが、使い始めの言語だとまず標準入力のお作法を確認するところから始まります。
KotlinではJavaと同じくScannerクラスが使えますが、Kotlin標準のreadLine()の方が何かと便利そうなのでこちらを使っていくことにします。
fun main(args: Array<String>){
val (a, b) = readLine()!!.split(" ").map{ it.toInt() }
if(a * b % 2 == 0) println("Even") else println("Odd")
}
何やらギッチリ詰まったコードですね……
流れとしては
readLine()で一行分の入力をString型として受け取る（"!!"でnull非許容に）
↓
split()で空白区切りにパース
↓
map{}でInt型に変換して各変数に代入
という感じです。
Kotlinではval（定数）やvar（変数）による型推論が使えるので、型の指定は基本的には必要ないみたいです。
また、このコードでは()内に変数を複数記述することで入力された各要素を一挙に代入していますが、変数を一つだけ宣言すればListとしてそのまま使えます。
val list = readLine()!!.split(" ").map{ it.toInt() } // Int型のList
これはなかなか便利ですね！
ただ、この文法を毎回入力するのはちょっと骨が折れるので、使用頻度の高そうな標準入力文法はあらかじめメソッド化しておこうと思います。
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = next().split(" ").map{ it.toInt() }
fun nextLongList() = next().split(" ").map{ it.toLong() }
fun nextDoubleList() = next().split(" ").map{ it.toDouble() }
これなら楽チン。
2問目 ABC081A - Placing Marbles
問題のリンク
考察
入力された文字列に"1"がいくつ含まれているか数える問題です。
JavaではString型の文字列を1文字ずつ参照するためにcharAt()というメソッドを使う必要がありますが、Kotlinではs[0]みたいに配列ライクな表記で参照できます。
String型に限らず、Listなどのコレクションにおいても同様みたいです。
val s = "Kotlin"
val list = listOf(1, 2, 3)
println(s[0])
println(list[0])
> kotlinc main.kt -include-runtime -d main.jar
> java -jar main.jar
K
1
この仕様を利用して、for文で全文字を探索します。
fun main(args: Array<String>){
val s = next()
var ans = 0
for (i in s.indices) {
if(s[i] == '1') ans++
}
println(ans)
}
indicesは「配列やコレクションのインデックス一覧」を意味します。
val ary = arrayOf(1, 2, 3)
for (i in 0..2) { // これと
println(ary[i])
}
for (i in ary.indices) { // これは同じ動きをする
println(ary[i])
}
> kotlinc main.kt -include-runtime -d main.jar
> java -jar main.jar
1
2
3
1
2
3
これは超便利！！！！！
ちなみに、Kotlinでは配列に対してもそのままStream APIみたいなことができるみたいなので、別解でこういうのも。
fun main(args: Array<String>){
val s = next()
println(s.count{ it == '1' })
}
> kotlinc main.kt -include-runtime -d main.jar
> java -jar main.jar
110
2
なんだか変態感が
3問目 ABC081B - Shift only
問題のリンク
考察
題意を分かりやすく言い換えると「2で割り切れる回数が最も少ない数字を探す」という問題です。
fun main(args: Array<String>){
next()
val list = nextIntList()
var ans = Int.MAX_VALUE
for (i in list.indices) {
var a = list[i]
var count = 0
while(a % 2 == 0){
a /= 2
count++
}
ans = Math.min(ans, count)
}
println(ans)
}
1行目のNは邪魔なので使わないので「next()で受け取るだけ受け取って何もしない」という操作を挟みます。
Kotlinは未使用変数があるとコンパイルエラーになるみたいなので、使わない変数は切り捨ててしまいます。
fun main(args: Array<String>){
val n = nextInt() // nが未使用なのでコンパイルエラーになる
val a = nextInt()
println(a)
}
> kotlinc main.kt -include-runtime -d main.jar
main.kt:15:9: warning: variable 'n' is never used
val n = nextInt()
4問目 ABC087B - Coins
問題のリンク
考察
全探索の入門的な問題ですね。
各硬貨の使用枚数の組み合わせを全て調べることで答えを出します。
fun main(args: Array<String>){
val a = nextInt()
val b = nextInt()
val c = nextInt()
val x = nextInt()
var ans = 0
for (i in 0..a) {
for (j in 0..b) {
for (k in 0..c) {
val sum = i * 500 + j * 100 + k * 50
if(sum == x) ans++
}
}
}
println(ans)
}
書くことが特にない
5問目 ABC083B - Some Sums
問題のリンク
考察
「各桁の和を求める」という操作をどうやって実現するかが課題です。
「10で割った余りを足していく」という方法が自然だと思いますが、ここはあえて変化球的な解き方をしてみます。
fun main(args: Array<String>){
val (n, a, b) = nextIntList()
val ans = (1..n).filter{ check(it.toString(), a, b) }.sum()
println(ans)
}
fun check(s: String, a: Int, b: Int) : Boolean {
var sum = 0
for (i in s.indices) sum += s[i] - '0'
if(sum in a..b) return true else return false
}
(1..n)は「1以上n以下の整数」を意味します。
これに「各桁の和がa以上b以下になるか」でfilterをかけ、最後にそれらの和をsum()で返す、という流れです。
各桁の和を求める方法については、まず対象の整数を文字列に変換し、1文字ずつ「'0'で引いたものを足し合わせていく」という操作をします。
各文字はchar型として扱われている（っぽい？）ので、'0'で引くとASCIIコード的に該当する数字と同じものが得られる、という感じですね。
どんどん"Kotlinらしい"コードになってきているような気がして、ワクワクしてきますね……！！
次にいきましょう！
6問目 ABC088B - Card Game for Two
問題のリンク
考察
いわゆるゲーム問題ですね。
ルール自体はシンプルなので、貪欲法で考えることで答えが出せます。
具体的には「その時点で残っているカードの中で最も大きい数のカードを取る」が最適戦略となるので、これを実現するためにソートを使います。
fun main(args: Array<String>){
next()
val list = nextIntList()
val card = list.sortedDescending()
var alice = 0
var bob = 0
var turn = true
for (i in card.indices) {
if(turn) alice += card[i] else bob += card[i]
turn = !turn
}
println(alice - bob)
}
1行目いらない
sorted()で昇順ソート、sortedDescending()で降順ソートができます。今回は簡単化のために後者を選択。
ソート後はAliceとBobの持ち点に交互に加算していき、最後に差を求めればOKです。
7問目 ABC085B - Kagami Mochi
問題のリンク
考察
同じ直径で重複している餅を取り除くと、最後に残った餅の数がそのまま答えになります。
各数字の出現回数を数えるのもアリですが、今回は「重複を取り除く」という部分に注目してみます。
fun main(args: Array<String>){
val n = nextInt()
val ary = Array(n){ nextInt() }
println(ary.distinct().count())
}
ここにきてArrayが初登場です。
Array(回数){各行で入力を受け取る処理}と書くことで「1行につき1つ入力された要素を格納した配列」を宣言することができます。
distinct()は「配列やコレクションから重複を取り除いたものを返す」という処理をします。
まさにこの問題のためにあるようなメソッドですね。
count()は配列やコレクションの要素数を返します。
filterやdistinct()などの処理を挟んだ後に使うことで真価を発揮しそうですね。
8問目 ABC085C - Otoshidama
問題のリンク
考察
4問目のCoinsと似ていますが、こっちはNの制約が最大2000となっています。
愚直にfor文を3つ回すと2000の3乗で計算量が80億というとんでもない数字になってしまいます。
競プロにおいてはO(10^8)、つまり計算量1億が実行時間の一つの目安となっているので、余裕でアウトですね。
しかし、よくよく考えると「紙幣の枚数は"合計で"N枚」と定められているので、例えば10000円札と5000円札の枚数を決めてしまえば1000円札の枚数も次のように一意に決まります。
val n = 2000 // お札の枚数
val yukichi = 500 // 諭吉さん
val higuchi = 1000 // 樋口さん
val noguchi = n - yukichi - higuchi // 野口さんは500枚
これで「2000の3乗」から「2000の2乗（実際はもっと少ない）」に計算量を減らせます。
一定以上の難易度の問題になると、こういった計算量の削減が考察の核となることも少なくありません。
fun main(args: Array<String>){
val (n, y) = nextIntList()
for (a in 0..n) {
for (b in 0..n - a) {
val c = n - a - b
val sum = a * 10000 + b * 5000 + c * 1000
if(sum == y){
println("$a $b $c")
return
}
}
}
println("-1 -1 -1")
}
println()内になにやら見慣れない表記が出てきましたね。
Kotlinでは"$変数名"と記述することで、Javaみたいに+演算子を使わずとも数値型や真偽値型の変数を文字列に組み込めます。
なんだかprintfに近いものを感じますね。
int a = 10;
int b = 20;
System.out.println(a + " " + b); // Javaのprintlnでは+演算子で結合するけど…
val a = 10
val b = 20
println("$a $b") // KotlinならこれでOK!
9問目 ABC049C - 白昼夢
問題のリンク
考察
個人的には10問中最大の難問だと思います。
"dream","erase","eraser"の3種類だけならまだ解きやすいのですが、"dreamer"の存在が壁として立ちはだかります。
最後の"er"の2文字が"erase","eraser"と衝突してしまうので、愚直に文字列Sの先頭から見ていくとどこかでズレが生じてしまいます。
"dreamerase" -> "dream" + "erase"となるはずが…
"dreamerase" -> "dreamer + "aseとなってしまう！
かといって"dream"の優先順位を上げると
"dreamerdream" -> "dreamer" + "dream"で本来成立するはずが…
"dreamerdream" -> "dream" + "erdream"となってしまう！ ジレンマ！
これを解決するために「文字列の末端から見ていく」という方法をとります。
fun main(args: Array<String>){
var s = next()
var result = true
while(s.length > 0 && result){
when{
s.endsWith("dreamer") -> s = s.substring(0, s.lastIndexOf("dreamer"))
s.endsWith("eraser") -> s = s.substring(0, s.lastIndexOf("eraser"))
s.endsWith("dream") -> s = s.substring(0, s.lastIndexOf("dream"))
s.endsWith("erase") -> s = s.substring(0, s.lastIndexOf("erase"))
else -> result = false
}
}
println(if(result) "YES" else "NO")
}
whenはswitch文と似たような働きをしますが、よりスッキリしていて使いやすそうですね。
endsWith()は「その文字列が指定した文字列で終了しているか」を判定するメソッドです。Javaでもおなじみ（？）のやつですね。
これでtrueが返ってくれば「末端だけ切り落としてもう一度判定する」という処理を繰り返し、最終的にSが空文字列になればOKです。
10問目 ABC086C - Traveling
問題のリンク
考察
いよいよ最後！
時系列順に旅行プランを見ていき、「次の目的地にピッタリ止まれない」「そもそも時間が間に合わない」のいずれかに引っかかったらその時点で実行不可能とみなせます。
目的地にピッタリ止まれるかどうかは「時間差と距離差の偶奇が一致しているか」で判定できます。
問題は「時系列順にプランを見ていく」という部分ですね。
例えばt,x,yをそれぞれ別の配列に格納すると、tだけソートしても残りのxとyには反映されません。
今回は「二次元配列でt,x,yを同じ次元に格納し、tを基準にソートする」という方法で解いてみます。
fun main(args: Array<String>){
val n = nextInt()
val ary = Array(n + 1) { IntArray(3) { 0 }}
repeat(n) {
val (t, x, y) = nextIntList()
ary[it][0] = t
ary[it][1] = x
ary[it][2] = y
}
val result = ary.sortedBy { it[0] }
for (i in 0 until n) {
val time = result[i + 1][0] - result[i][0]
val dist = Math.abs((result[i + 1][1] + result[i + 1][2]) - (result[i][1] + result[i][2]))
if(dist > time || dist % 2 != time % 2){
print("No")
return
}
}
println("Yes")
}
Kotlinで多次元配列を宣言するときは、Array(要素数){中身}を入れ子のように書いていきます。
repeat()は「指定回数分だけ同じ処理を繰り返す」というメソッドです。
現在のループ回数はitで参照できます。これも便利そう！
そして、肝心要の「多次元配列のソート」についてはsortedByを使うことで簡単に実現できます。
このコードではit[0]と記述することで「二次元目の1個目の要素(=t)を基準にソート」という処理をしています。
sortedByは配列に限らずListやMapなどのコレクションでも同様に使えます。
val son1 = listOf(4, 5, 6)
var son2 = listOf(7, 8, 9)
val son3 = listOf(1, 2, 3)
val par = listOf(son1, son2, son3) // 最初は[[4, 5, 6], [7, 8, 9], [1, 2, 3]]となっている
val result = par.sortedBy { it[0] } // 1個目の要素を基準に昇順ソート
println(result)
> kotlinc main.kt -include-runtime -d main.jar
> java -jar main.jar
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
競技プログラミングにおけるKotlinの長所と短所
ここまで問題を解いてみて、競プロにおけるKotlinのポテンシャルを「主にJavaと比較すると」というスタンスで考察してみます。
まだ十数問しか解いていないので見当外れな部分もあるかもしれませんが、どうかご容赦ください……
長所
- 型推論のおかげで変数宣言が楽
- var（変数）かval（定数）かを意識することで、変数関連のバグが減りそう（な気がする）
- 未使用変数がコンパイル時点で取り締まられるので、変数関連のバグが減りそう（これは多分間違いない）
- 配列やコレクションの取り回しがしやすく、かつ便利なメソッドが充実している（重要）
- "Better Java"の謳い文句通りJavaでできることは基本的に何でもできる（つまり競プロにおいて機能面で困ることはない）し、記述量や可読性という点でもJavaより優れていると思う
- 「ことりん」っていう名前の響きがかわいい（は？）
短所
- 実行時間がJavaよりやや遅い
- コンパイル時間がJavaよりかなり遅い
- 「mutable（書き換え可能）なコレクションとそうでないコレクションがある」という初見殺しが存在する
- 他の言語で文末にセミコロンを書くことに苦痛を感じるようになる（個人差あり）
こんな感じでしょうか。
総括すると「Javaユーザーなら移行も容易で、かつJavaより使いやすい」という印象ですね。
Java以外の言語をメインとしている人にとっての習得難易度がどれほどのものかは、私からは何とも言えませんが……
- 機能が充実している
- 実行速度も十分速い
- 変数や型などにかなり厳格なチェックが入るので、割とバグりにくい
これらの特徴から、言語としてのポテンシャルは高いと思います。
「これから競技プログラミングを始めたい！」という人にもオススメできるかも。
おわりに
すっかりKotlinの魅力にハマってしまい、Javaから完全移行する決意まで固めてしまいました。
今後はKotlinで競プロにいそしみつつ、問題の考察やコンテストの感想などの記事を書いていけたらいいなあと思っています。
ここまでお読みいただきありがとうございます。mikhailでした。