はじめに
業務では、Java, Kotlinを使用しています。
AtCoderは、rubyで緑色です。
Kotlinを業務等で使用している人が、AtCoderを始めた直後、あるいは解説を読んでいてKotlinではどう書くんだっけ？、といったときに見てもらうことを想定しています。
ちなみに、AtCoderの使用言語としてのKotlinはかなりマイナー*なようです。
2023年8月19日のABC315にコンテスト時間内に参加しE問題を正解したのは全体で2,997人いますが、Kotlinで正解した人は1人だけでした。残念ながら、私は時間内にはrubyを用いて正解しているためこの1人にはなれませんでした(なれたとしても2人目か)。
AtCoderでのKotlinのバージョン
2023年8月6日以降の大会から新ジャッジシステムとなり、Kotlinのバージョンが、1.8.20になりました。
それ以前は、1.3.71です。
バージョンによる違いからRE(Runtime Error)となることがあるため注意が必要です。
以下、例です。
| メソッド・クラス | 1.3.71 | 1.8.20 |
|---|---|---|
Collectionのmin, max等 |
戻り値がnull許容(empty -> null) |
戻り値がnull非許容(empty -> 例外) |
CollectionのsumOf
|
RE(Runtime Error)になる. sumByを使用する |
sumByは非推奨 |
ArrayDeque |
実験的導入であったため@ExperimentalStdlibApiの記述が必要 |
使用可能 |
ローカルでの実行環境の導入
AtCoderはブラウザ上でコードテストも可能であり、ローカルの実行環境を必要としません。
しかし、コードテストを使用する場合、問題にある入力例1をコピーして貼り付けてテストして、次に入力例2をコピーして貼り付けて...と手間です。
VScode等、使い慣れたIDEでコードを書いてローカルで自動テストし、提出できると非常に楽です。
導入には以下の2つのツールが必要です。
導入方法は、以下が参考になるかと思います。
コレクション
コレクションのメソッドの使用方法を忘れた時に以下を参照しています。
AtCoderのトレーニング(学習に使用したサイト・書籍)
AtCoder Beginners Selection
AtCoderに登録した後チャレンジしてみる問題集が用意されています。
解答例:AtCoder Beginners Selection
AtCoder Problems
Boot camp for Beginnersで、レベルに応じた練習問題(過去問)を解くことが出来ます（ログインが必要）。
また、コンテストの一覧や各問題のDifficultyを見ることが出来ます。
GitHubのアカウントでログインし、AtCoderのアカウントと紐づける(AtCoder User ID)ことで、自分が今までに解いた問題の統計データを視覚的に表現してくれます。
その他にも、いろいろありますが割愛します。
競プロ典型 90 問
AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」です。
解説は図を多用しわかりやすいです。
これのおかげで、緑になれたといっても過言ではありません(rubyでですが)。
ただし、
が7つのものは今でもほとんど解けていません。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】分野別 初中級者が解くべき過去問精選 100 問
AtCoderでよく出るアルゴリズムの学習強化に使用しました。
Educational DP Contest / DP まとめコンテスト
AtCoderでは動的計画法(DP)を用いて解ける問題が多く出題されていると感じています。
そもそも、問題を見てそれがDPで解けることに気づけないことが多々あり、さまざまなDPをこれで学習しました。
入出力
入力
基本的な入力
// 10
val N = readLine()!!.toInt()
// N = 10
// 10 3
val (N, M) = readLine()!!.split(" ").map(String::toInt)
// N = 10, M = 3
// 1 2 3 4 5
val A = readLine()!!.split(" ").map(String::toInt)
// A = [1, 2, 3, 4, 5]
// 1 2 3 4 5
// 数値を1始まりではなく0始まりにしたい場合
val A = readLine()!!.split(" ").map(String::toInt).map(Int::dec)
// A = [0, 1, 2, 3, 4]
// abcd
val S = readLine()!!.toList()
// S = ['a', 'b', 'c', 'd']
// 1 2 3
// 4 5 6
val A = List(N) { readLine()!!.split(" ").map(String::toInt) }
// A = [[1, 2, 3], [4, 5, 6]]
N頂点M辺の単純無向グラフの入力
// 1 2
// 3 4
// 2 5
val G = List(N + 1) { mutableListOf<Int>() }
repeat(M) {
val (u, v) = readLine()!!.split(" ").map(String::toInt)
G[u].add(v)
G[v].add(u)
}
// G = [[], [2], [1, 5], [4], [3], [2]]
整数が出てくる回数
// 1 2 3 1 1 4 2
val A = readLine()!!.split(" ").map(String::toInt).groupBy { it }.mapValues { it.value.size }.withDefault { 0 }
// もしくは
val A = readLine()!!.split(" ").map(String::toInt).groupingBy { it }.eachCount().withDefault { 0 }
// {1=3, 2=2, 3=1, 4=1}
withDefaultを使用するとgetValueで値を取得するときにキーが存在しなくても設定したデフォルト値が返ります。
出力(少量の場合)
// 配列をスペース区切り
// A = [1, 2, 3]
println(A.joinToString(" "))
// 1 2 3
// 配列を改行区切り
// A = [1, 2, 3]
A.forEach(::println)
// 1
// 2
// 3
// 2次元配列を1行毎にをスペース区切り
// A = [[1, 2, 3], [4, 5, 6]]
A.forEach { println(it.joinToString(" ")) }
// 1 2 3
// 4 5 6
出力(大量の場合)
printlnは都度flushされるため、大量の出力($10^5$を超える)が必要な場合にはボトルネックになるようです。その場合は、PrintWriterを使用し、最後にまとめて出力する(flush)する方法があります。
AtCoderのコードテストにおいて、以下の処理を通常のprintlnで行うと、実行時間は1,386msかかりますが、PrintWriterを使用した場合、271msで終わります(何の処理もしない場合でも実行に39ms程度かかるため、実行時間が$1/5$ ~ $1/6$になります)。
import java.io.PrintWriter
fun main() {
// 第2引数はautoFlushの有無
val pw = PrintWriter(System.out, false)
(1 .. 1_000_000).forEach(pw::println)
pw.flush()
pw.close()
}
使用例(競プロ典型90問010)
最大100,000行出力する問題
解答例:PrintWriter使用:実行時間732ms
解答例:PrintWriter未使用:実行時間1,244ms
参考
途中で処理を終了するにはexitProcess(0)
Whileループから抜ける方法には、breakがあります。
foEach等だとラベルとrunを組み合わせで可能です*。
これらとは、少し異なり、答えが求まった時点で処理を終了したい場合があります。
例えば、解がない時は解なしを出力しなければならない場合、あるいはその逆の場合などです。
その場合には、exitProcess(0)を用います。
以下例です。
import kotlin.system.exitProcess
fun main() {
var cnt = 0
while (cnt < 3) {
cnt++
if (listOf(true, false).random()) {
println("$cnt回で終了")
exitProcess(0)
}
}
println("途中終了できず")
}
使用例(AtCoder Beginners Selection/ABC049C - 白昼夢)
解答例:AtCoder Beginners Selection/ABC049C - 白昼夢
動的計画法ではプリミティブ型配列を推奨
配列の要素数は決まっていて、要素の変更を順次していく場合があります。
例えば、動的計画法(DP法)などです。
以下の3パターンが考えられるかと思います。
MutableList(N + 1) { 0 } // 可変リスト
Array<Int>(N + 1) { 0 } // 参照型オブジェクトの配列
IntArray(N + 1) { 0 } // プリミティブ型の配列
この中で、一番処理速度が速いのはIntArrayです。IntArrayはプリミティブ型の配列です。
MutableListを使用すると問題によっては、TLE(Time Limit Exceeded)する場合があります。
MutableListだとTLEする例(Educational DP Contest / DP まとめコンテストJ)
解答例:DoubleArray使用:実行時間440ms
解答例:MutableList使用:22ケース中15ケースがTLE(> 2,000ms)
参考
再帰関数はRE(Runtime Error)することがある
深さ優先探索(DFS)を行う場合、多くが再帰関数を使うことになるかと思います。
AtCoderで再帰関数を使用する場合、多くがスタックオーバーフローしRE(Runtime Error)となります。
対処法は2つ(Kotlin 1.8.20の場合3つ)あります。
再帰：末尾再帰の場合
メソッドのreturnが自身のメソッドである場合、末尾再帰です。
メソッド定義の先頭にtailrec(末尾再帰)キーワードをつけることで、コンパイラが高速に最適化(while文?)してくれるようです。
最小公倍数の項で提示しているメソッドが末尾再帰に対するtailrecの例です。
再帰：その他
末尾再帰の場合、while文に変換できますが、AtCoderで使用する再帰の多くがそれ以外です。
Thread
解決策の1つは、別スレッドを立てて処理を行う方法です。
fun solve() {
// 問題の解答をここで作成(通常はmainメソッド内で記述する部分)
}
fun main() {
// Thread(group: ThreadGroup?, target: Runnable?, name: String, stackSize: Long)
Thread(null, ::solve, "solve", 1.shl(26)).start()
}
使用例(競プロ典型90問003)
参考
DeepRecursiveFunction
Kotlinのバージョン1.3.71では使用できません。
Kotlinのバージョン1.8.20では、DeepRecursiveFunctionが使用できます。
以下に通常のメモ化再帰とDeepRecursiveFunctionを用いたメモ化再帰の例を示します。
import java.math.BigDecimal
fun main() {
val N = 20000
val memo1 = Array<BigDecimal>(N + 1) { BigDecimal("-1") }
val memo2 = Array<BigDecimal>(N + 1) { BigDecimal("-1") }
// 通常のメモ化再帰
fun fibo1(n: Int): BigDecimal {
if (memo1[n] >= BigDecimal.ZERO) return memo1[n]
memo1[n] = if (n <= 1) BigDecimal.valueOf(n.toLong()) else fibo1(n - 2).add(fibo1(n - 1))
return memo1[n]
}
// DeepRecursiveFunctionを用いたメモ化再帰
val fibo2 = DeepRecursiveFunction<Int, BigDecimal> { n ->
if (memo2[n] < BigDecimal.ZERO) {
memo2[n] = if (n <= 1) BigDecimal.valueOf(n.toLong()) else callRecursive(n - 2).add(callRecursive(n - 1))
}
memo2[n]
}
// fibo1のみ、StackOverflowError になります
println(fibo1(N))
println(fibo2(N))
}
使用例(ABC315/E)
解答例:DeepRecursiveFunction使用
解答例:DeepRecursiveFunction未使用:37ケース中4ケースがRE(Runtime Error)
参考
幅優先探索ではArrayDequeを使用する
Kotlinのバージョン1.3.71では@ExperimentalStdlibApiが必要
通常、幅優先探索では、両端キュー(Doubleended Queue)を用いるかと思います。
Kotlinには、ArrayDequeクラスがあります。
Kotlinのバージョンが1.3.70では、ArrayDequeはまだ実験的導入であったため、以下のようにアノテーションをつける必要があります。
// 1.3.70の場合、以下のアノテーションが必要
@ExperimentalStdlibApi
fun main() {
// 初期化
val deque = ArrayDeque(listOf(1))
// 先頭の値取り出し
val first = deque.removeFirst()
// 末尾に値追加
deque.add(2)
}
ArrayDequeではなく、MutableListを使用することも可能ですが、速度はArrayDequeの方が速そうです。
使用例(競プロ典型90問003)
解答例:ArrayDeque使用:実行時間712ms
解答例:MutableList使用:実行時間1,434ms
ビット演算
ビット全探索やビットDP(動的計画法)で、ビット演算を使用することがあります。
// 左シフト
2.shl(1) // 4
// 右シフト
2.shr(1) // 1
// 論理積
2.and(1) // 0
// 排他的論理和
2.xor(1) // 3
// ビット反転
2.inv() // -3
ビット全探索
val N = readLine()!!.toInt()
val A = readLine()!!.split(" ").map(String::toInt)
(1 .. 1.shl(N) - 1).forEach { bits ->
repeat(N) { i ->
if (bits.shr(i).and(1) == 0) return@repeat
// A[i]に対してやりたい処理
}
}
使用例(競プロ典型90問002)
累積和はScanを使う
AtCoderでは、累積和を用いる問題も多く出題されます。
ListやArrayのScanメソッドを使用すると簡単に累積和を求めることができます。
val csum = array.scan(0L, Long::plus)
// array: [1, 2, 3, 4, 5] の場合
// csum: [0, 1, 3, 6, 10, 15]
自作ライブラリ
最小公倍数
他の言語では、メソッドが用意されていたりしますが、Kotlinにはないため自作します。
末尾再帰を使用しています。
/**
* 最大公約数
*
* @param num1 数1
* @param num2 数2
* @return 最大公約数
*/
tailrec fun gcd(num1: Long, num2: Long): Long = if (num1 == 0L) num2 else gcd(num2 % num1, num1)
tailrec fun gcd(num1: Int, num2: Int): Int = if (num1 == 0) num2 else gcd(num2 % num1, num1)
累乗、冪剰余
Kotlinには、累乗を計算するメソッドfun Double.pow(n: Int): Doubleがありますが、戻り値がDouble型です。また、AtCoderでは冪剰余を使用する問題が出題されますが、使用できるメソッドがないため自作します。
冪剰余は、逆元を使用する問題(フェルマーの小定理を用いる)で使用します。
フェルマーの小定理は$p$を素数とし、$a$を整数とすると、下記が成り立つという定理です。
$a^p \equiv 1 \pmod p$
これを変形すると下記の式となるため、割り算を掛け算として扱うことが出来ます。
$a^{(p - 2)} \equiv \displaystyle\frac{1}{a} \pmod p$
例えば、組み合わせ$nCr$などを求める問題で使用します。
/**
* 冪剰余
*
* @param x 底
* @param n 指数
* @param mod 除数
* @return 冪剰余
*/
fun pow(x: Int, n: Int, mod: Int): Long {
var base = x.toLong()
var exp = n
var ans = 1L
while (exp > 0) {
if (exp.and(1) == 1) ans = ans * base % mod
exp /= 2
base = base * base % mod
}
return ans
}
順列・組み合わせ
順列の数や組み合わせの数を取得するときに使用します。AtCoderでは、場合の数が$10^9$を超えることが多く、1,000,000,009等で割った余りを解答することが多いです。
/**
* 順列・組み合わせ
* @property size サイズ
* @property mod 除数
*/
class PermComb(
private val size: Int,
private val mod: Int
) {
// 階乗
private val fact = LongArray(size + 1) { 1L }
// 階乗の逆数
private val invFact = LongArray(size + 1) { 1L }
init { prepare() }
/**
* 順列
*
* @param n 位数
* @param r 選ぶ個数
* @return 場合の数
*/
fun perm(n: Int, r: Int): Long {
if (n < 0 || r < 0 || n < r) return 0L
return fact[n] * invFact[r] % mod
}
/**
* 組み合わせ
*
* @param n 位数
* @param r 選ぶ個数
* @return 場合の数
*/
fun comb(n: Int, r: Int): Long {
if (n < 0 || r < 0 || n < r) return 0L
return perm(n, r) * invFact[n - r] % mod
}
/**
* 準備
*/
private fun prepare() {
(2 .. size).forEach {
fact[it] = fact[it - 1] * it % mod
invFact[it] = invFact[it - 1] * pow(it, mod - 2) % mod
}
}
/**
* 冪剰余
*
* @param x 底
* @param n 指数
* @return 冪剰余
*/
private fun pow(x: Int, n: Int): Long {
var base = x.toLong()
var exp = n
var ans = 1L
while (exp > 0) {
if (exp.and(1) == 1) ans = ans * base % mod
exp /= 2
base = base * base % mod
}
return ans
}
}
素因数分解
/**
* 素因数分解
*
* @param num 素因数分解する数
* @return MutableMap<素因数, 指数>
*/
fun primeDivision(num: Long): MutableMap<Long, Int> {
val baseToExpMap = mutableMapOf<Long, Int>().withDefault { 0 }
var tmp = num
(2 .. Math.sqrt(num.toDouble()).toLong()).forEach { i ->
while (tmp % i == 0L) {
baseToExpMap[i] = baseToExpMap.getValue(i) + 1
tmp /= i
}
}
if (tmp > 1) baseToExpMap[tmp] = baseToExpMap.getValue(tmp) + 1
return baseToExpMap
}
二分探索法
Kotlinには二分探索のメソッド binarySearch が存在します。
binarySearch は、同じ値が複数含まれる場合、必ずしも一番左側のインデックスを返すとは限りません(下記例）。また、値が存在しない場合は、負数が返ります。
他の言語では以下のようなメソッドが用意されており使用されています。
-
lowerBound: ソート済みリストにおいて、指定された範囲に、指定した値と同じかそれ以上の値が出現する一番左のインデックスを返す -
upperBound: ソート済みリストにおいて、指定された範囲に、指定した値より大きい値が出現する一番左のインデックスを返す
val a = mutableListOf(1, 2, 3, 4, 4, 5)
println(a.lowerBound(4)) //-> 3
println(a.binarySearch(4)) //-> 4
println(a.upperBound(4)) //-> 5
そこで、lowerBoundとupperBoundを自作します。
/**
* LowerBound
*
* @param element 検索したい値
* @param fromIndex 開始位置
* @param toIndex 終了位置(この位置は含まない)
* @return element以上の値が出現する一番左のインデックス
*/
fun <T: Comparable<T>> MutableList<T>.lowerBound(element: T, fromIndex: Int = 0, toIndex: Int = size): Int {
return binarySearch(element, Comparator {a, b -> if (a.compareTo(b) >= 0) 1 else -1 }, fromIndex, toIndex).inv()
}
/**
* UpperBound
*
* @param element 検索したい値
* @param fromIndex 開始位置
* @param toIndex 終了位置(この位置は含まない)
* @return elementより大きい値が出現する一番左のインデックス
*/
fun <T: Comparable<T>> MutableList<T>.upperBound(element: T, fromIndex: Int = 0, toIndex: Int = size): Int {
return binarySearch(element, Comparator {a, b -> if (a.compareTo(b) > 0) 1 else -1 }, fromIndex, toIndex).inv()
}
使用例(競プロ典型90問007)
ダイクストラ法
最短経路問題を効率的に解くアルゴリズムです。
優先度付きキューを用います。
import java.util.PriorityQueue
/**
* ダイクストラ
*
* @param start 開始位置(頂点)
* @param n 要素数
* @param edge 辺 Array<MutableList<Pair<頂点, コスト>>>
* @return コストの配列
*/
fun dijkstra(
start: Int,
n: Int,
edge: Array<MutableList<Pair<Int, Int>>>
): LongArray {
val cost = LongArray(n + 1) { 1_000_000_000_000L }
cost[start] = 0L
val log = PriorityQueue(sortedSetOf(compareBy {it.second}, Pair(start, 0L)))
while (log.isNotEmpty()) {
val (from, fromC) = log.poll()
if (cost[from] < fromC) continue
edge[from].forEach { (to, toC) ->
if (cost[to] <= cost[from] + toC) return@forEach
cost[to] = cost[from] + toC
log.add(Pair(to, cost[to]))
}
}
return cost
}
使用例(競プロ典型90問013)
素集合データ構造(DSU, Union-Find木)
rootメソッドに再帰を使用しているのでただ実装するとRE(Runtime Error)になることがあります。
Union-Findはグループ分けを効率的に管理できるデータ構造です。
C問題以降で使用されるイメージです。2週連続で使用できる問題が出題されることもありました。
/**
* DSU(Union-Find木)
*
* @property n 木のサイズ
*/
class DSU(private val n: Int) {
// 負の整数の場合、絶対値が連結成分数を表す
private val parentOrSize = IntArray(n) { -1 }
var groupSize: Int = n
private set
/**
* 親を取得
* @param u 要素番号
* @return 親番号
*/
val root = DeepRecursiveFunction<Int, Int> { u ->
if (parentOrSize[u] < 0) {
u
} else {
parentOrSize[u] = callRecursive(parentOrSize[u])
parentOrSize[u]
}
}
val leader = root
/**
* 結合
* @param u 要素番号
* @param v 結合する要素番号
*/
fun unite(u: Int, v: Int) {
var ru = root(u)
var rv = root(v)
if (ru == rv) return
if (size(ru) < size(rv)) {
val temp = ru
ru = rv
rv = temp
}
parentOrSize[ru] += parentOrSize[rv]
parentOrSize[rv] = ru
groupSize--
}
val merge = ::unite
/**
* 親が同じか
* @param u 要素番号
* @param v 比較する要素番号
* @return true or false
*/
fun isSame(u: Int, v: Int): Boolean = root(u) == root(v)
/**
* 連結成分数
*
* @param u 要素番号
* @return 連結成分数
*/
fun size(u: Int) = -parentOrSize[root(u)]
/**
* グループ
*
* @return Map<ルート, グループメンバ>
*/
fun groupList(): List<List<Int>> {
val groups = mutableMapOf<Int, MutableList<Int>>()
(0 until n).forEach { groups.getOrPut(root(it)) { mutableListOf() }.add(it) }
return groups.values.toList()
}
/**
* ルートリスト
*
* @return ルートリスト
*/
fun rootList(): List<Int> = (0 until n).filter { parentOrSize[it] < 0 }
}
使用例(ABC075/C)