drken さんの記事で紹介されている AtCoder に登録したら解くべき精選 10 問 を Kotlin で解いてみました。
問題リストはこちら：AtCoder Beginners Selection
2017 年5月、Kotlin が Java に続くもう一つの Android アプリ開発における公式言語となることが Google によって発表されました。この発表によって、Kotlin は Android アプリ開発の世界で一気に注目度が高まりました。これにより、今後も活発に開発が進むことが期待されている言語です。ただ、Android アプリ開発専用言語というわけではなくて、Java と同じような汎用性のある言語です。
競技プログラミングの世界では、2018 年の ICPC の世界大会で Kotlin がサポートされることが発表（公式記事：英語）されました。 これにより、今後競技プログラミングサイトで Kotlin のサポートが広がることが期待できます。AtCoder 及び CodeForces ではすでにサポートされています。
競技プログラミングの観点から見た Kotlin の特徴は以下の通りです。Kotlin の特徴は端的に言えば "Better Java" で、それは競技プログラミングにおいてもあてはまっています。
各問題のアルゴリズム面の解説はしません。drken さんのオリジナル記事を参照してください。
2 つの整数の積の偶奇を判定する問題です。
入力を読み込む方法ですが、readLine()!! で行を読み込み、split(" ") して文字列のリストにした上で map(String::toInt) で整数のリストにし、それを変数の Tuple に代入します。このイディオムは今後も頻繁に使います。readline() の後に !! が必要なのは、readline() の返り値が String? 型 (nullable String)で、String 型 (non-nullable String) にキャストする必要があるためです。
出力する文字列を作る部分については、Kotlin には C++ や Java にある三項演算子の ? がないのですが、if 文が式として値を返せるのでそれを使います。
fun main(args: Array<String>) { val (a, b) = readLine()!!.split(" ").map(String::toInt) println(if (a * b % 2 == 0) "Even" else "Odd")}入力を受け取るのに Java の Scanner を使う方法もあります。この場合は以下のようになります。どちらを使うかは好みの問題でしょう。
import java.util.*fun main(args: Array<String>) { val scanner = Scanner(System.`in`) val a = scanner.nextInt() val b = scanner.nextInt() println(if (a * b % 2 == 0) "Even" else "Odd")}文字列に含まれる 1 の数を数える問題です。count 関数を使うと以下のように簡潔に書けます。
ラムダ式の引数が 1 つの場合、引数の宣言を省略して it を引数として使える、という文法は特徴的ですね。
fun main(args: Array<String>) { println(readLine()!!.count { it == '1' })}整数が n 個与えられ、2 で割り切れる回数が最小のものの、2 で割り切れる回数を求める問題です。
n 個の整数の入力を読み込む方法については、readLine()!!.split(" ").map(String::Int) のイディオムで、List<Int> を得るのが良いでしょう。そして、整数に対して 2 で割り切れる回数を求める関数 divCount を定義すれば、このリストに map(::divCount) を適用して各整数の 2 で割り切れる回数のリストに変換した上で、min を取れば答えが得られます。min() の返り値は nullable 型（リストが空の場合に null になるため）なのですが、今回は空にならないことがわかっているので non-nullable 型にキャストしましょう。
なお、以下のコードでは、変数 n は使われていません。
fun divCount(x: Int): Int { var count = 0 var currentX = x while (currentX % 2 == 0) { count++ currentX /= 2 } return count}fun main(args: Array<String>) { val n = readLine()!!.toInt() val xs = readLine()!!.split(" ").map(String::toInt) val ans = xs.map(::divCount).min()!! println(ans)}また、2 で割り切れる回数というのは 2 進表記での末尾の 0 の個数に等しいことに注目すると、Java の Integer.numberOfTrailingZeros 関数を用いて以下のように簡潔に書けます。
fun main(args: Array<String>) { val n = readLine()!!.toInt() val xs = readLine()!!.split(" ").map(String::toInt) val ans = xs.map(Integer::numberOfTrailingZeros).min()!! println(ans)}整数 a, b, c, n が与えられて、500 i + 100 j + 50 k = x を満たす整数 i, j, k (0 ≤ i ≤ a, 0 ≤ j ≤ b, 0 ≤ k ≤ c) の個数を求める問題です。
素直に三重ループを回せば良いでしょう。
fun main(args: Array<String>) { val a = readLine()!!.toInt() val b = readLine()!!.toInt() val c = readLine()!!.toInt() val x = readLine()!!.toInt() var ans = 0 for (i in 0..a) { for (j in 0..b) { for (k in 0..c) { if (500 * i + 100 * j + 50 * k == x) ans++ } } } println(ans)}1 以上 n 以下の整数のうち、10 進法で各桁の和が a 以上 b 以下であるものの総和を求める問題です。
1 以上 n 以下の整数は 1..n と Range 型で表現できるので、これに対して filter 関数を用いて条件を満たす整数だけを取り出し、sum を取るという方針で良いでしょう。
Kotlin では a <= x && x <= b は x in a..b と書くのが一般的なようです。こう書いても実際に a から b までの整数のリストが作られるわけではないので、計算量の心配は必要ありません。
fun main(args: Array<String>) { val (n, a, b) = readLine()!!.split(" ").map(String::toInt) val ans = (1..n).filter { it.toString().map { it - '0' }.sum() in a..b } .sum() println(ans)}n 個の整数が与えられ、Alice と Bob が大きい方から順に取って行き、二人が取る整数の合計の差を求める問題です。
降順にソートして、偶数番目 (0-index) の和と奇数番目の和の差と取れば良いです。偶数番目及び奇数番目の要素を抽出するには filterIndexed 関数が便利です。
fun main(args: Array<String>) { val n = readLine()!!.toInt() val xs = readLine()!!.split(" ").map(String::toInt) val sortedXs = xs.sortedDescending() val a = sortedXs.filterIndexed { index, value -> index % 2 == 0 }.sum() val b = sortedXs.filterIndexed { index, value -> index % 2 == 1 }.sum() println(a - b)}n 個の整数が与えられ、異なるものの個数を求める問題です。
入力を整数のリストして読み込み、Set に変換して size を調べれば良いです。
fun main(args: Array<String>) { val n = readLine()!!.toInt() val xs = IntArray(n, { readLine()!!.toInt() }) val ans = xs.toSet().size println(ans)}整数 n, t が与えられ、10000 * x + 5000 * y + 1000 * z = t かつ x + y + z = n なる (x, y, z) を求める問題です。
x, y について二重ループを回せば良いです。出力部分では文字列テンプレート機能を使っています。
fun main(args: Array<String>) { val (n, t) = readLine()!!.split(" ").map(String::toInt) for (x in 0..n) { for (y in 0..(n - x)) { val z = n - x - y if (10000 * x + 5000 * y + 1000 * z == t) { println("$x $y $z") return } } } println("-1 -1 -1")}文字列 s が与えられて、それが "dream", "dreamer", "erase" 及び "eraser" を好きな個数好きな順番でつなげることによって作れるかどうかを判定する問題です。
解法は色々あるのですが、drken さんのオリジナル記事で紹介されている貪欲法で解くことにします。文字列が 4 つのキーワードのどれかで終わっていたらそれを削るということを繰り返し、最終的に空文字列になるかどうかを判定します。
注意点として、Kotlin の String は Java の String と同じく不変型なので、数文字を削るという操作であっても、String を使って実装すると文字列全体がコピーされてしまいます。そこで、可変文字列型である StringBuidler クラスを使います。これは Java の StringBuilder クラスと同じです。
fun main(args: Array<String>) { val words = listOf("dream", "dreamer", "erase", "eraser") val s = readLine()!! val sb = StringBuilder(s) while (sb.isNotEmpty()) { var deleted = false for (word in words) { if (sb.endsWith(word)) { sb.delete(sb.length - word.length, sb.length) deleted = true } } if (!deleted) break } println(if (sb.isEmpty()) "YES" else "NO")}問題の説明がやや面倒なので省略します。原文を読んでください。
各チェックポイント毎に、時間とマンハッタン距離の大小関係、及び偶奇が一致するかを調べれば良いです。
注意点なのですが、 2018年3月現在 AtCoder では Kotlin のバージョンが 1.0 と古いため、Kotlin の Int.abs() 関数が使えません。そこで、絶対値の計算には Java の Math.abs() 関数を使っています。
以下のコードでは、チェックポイントの情報 (t, x, y) をまとまりとして扱うためにデータクラスを定義しています。このようにデータクラスは定義するのがとても簡単なので、いくつかの変数をまとまりとして扱いたいときはどんどん使うとコードの見通しが良くなると思います。データクラスは、equals() や hashCode() を自動的に実装するため、そのまま Set に入れることができるし、toString() も自動的に読みやすいものを実装するためデバッグに便利など、優れた機能です。
また、チェックポイントの配列 plans を作るときに、最初の要素として (0, 0, 0) を挿入しています。Array のコンストラクタの第二引数は配列の要素の初期値を返すラムダ式（引数はインデックス）なので、このようなコードになっています。
data class Plan(val t: Int, val x: Int, val y: Int)fun main(args: Array<String>) { val n = readLine()!!.toInt() val plans = Array(n + 1, { if (it == 0) { Plan(0, 0, 0) } else { val (t, x, y) = readLine()!!.split(" ").map(String::toInt) Plan(t, x, y) } }) for (k in 0 until n) { val dt = plans[k + 1].t - plans[k].t val distance = Math.abs(plans[k + 1].x - plans[k].x) + Math.abs(plans[k + 1].y - plans[k].y) if (distance > dt || distance % 2 != dt % 2) { println("No") return } } println("Yes")}以上のように、Kotlin は簡潔な記述が可能な言語で、特に現在 Java を使っている方には障壁が低くオススメできる言語です。
AtCoder に関してはバージョンが古いため使いにくいというのはあるのですが、ICPC World Finals で使える言語として競技プログラミングにおける地位が向上したことで、今後アップデートされることが期待できると言って良いでしょう。