LoginSignup
14
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

KotlinAdvent Calendar 2022Day 17
@dhirabayashi

Kotlinで競技プログラミングする中で見かけた、業務ではあまり見ない書き方

Last updated at Posted at 2022-12-16

はじめに

競技プログラミング（競プロ）と呼ばれる競技があります。聞いたことはあるという方もいらっしゃると思います。私はKotlinを使って競プロに取り組んでいるので、それをネタに何か書こうと思って筆を執りました。

競プロは本格的に取り組むようになってから半年ほどになります。当初は他の言語を使っていましたが、業務で使っているKotlinを使ってみたらどんな感じだろうと思って試したところ、なかなかいい感じだったのでそのまま使い続けています。

競プロはコンテストサイトに登録することで参加できます。日本で最も大きなコンテストサイトとしてAtCoderというものがあります。
私はほぼAtCoderでしか競プロを経験していないので、これ以降の記述における「競プロ」とは基本AtCoderのことを指します。
（どのコンテストサイトも基本は変わらないとは思いますが）

なお、私はKotlinでの実務経験は1年ちょい、AtCoderでのレーティングは茶色です。（下から2番目）
なのであまり強くない人が書いています。

想定読者と内容

どちらかといえばKotlinは知っているが競プロはよく知らない人向けです。競プロについて全然知らないと内容もよくわからないかもしれないので、競プロ自体についても多少説明します。ただ、Kotlinのアドベントカレンダーの記事なのでそこはあまり長くならないようにします。
と言いつつ、けっこう長くなりました…

要約すると

  • 業務でのプログラミングと競プロはレイヤーが異なるので、書くコードも違ってくる1
  • そのため、業務のプログラミングだとあまり見ないけど競プロだとよく見る書き方が多くある
  • 業務でプログラミングするが競プロはよく知らない人向けにそういうのを紹介してみたら面白いかもと思った

という感じです。たぶんそんなに役に立つ記事ではなく、軽い読み物みたいな感じです。

難しそうなアルゴリズムとかデータ構造には言及せず、小ネタ集のような感じです。タイトルの通り自分がKotlinを使っているのでKotlinのコードに絞るということですが、考え方としては他言語でも通用するものも含みます。

そういう意味だと、他言語で競プロをやっていてKotlinはよく知らないという人でも暇つぶしくらいにはなるかもしれません。

この記事で書いていないこと

競プロを布教する意図ではなく、また競プロerにKotlinを布教する意図でもないので、そういった内容はありません。

それがわかれば十分という方は本題へ飛んでください。

競プロについて

競プロはWikipediaでは以下のように説明されています。

競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。

たとえば、以下のような問題があります。

問題文
英小文字からなる文字列 W が入力されます。
W の末尾に英小文字の s を付け足したものを出力してください。

コンテストの開始時刻になったらこういった問題ページにアクセス可能になるので、みんなで一斉に解き始めて早く解けた人の勝ちという感じです。この問題は非常に簡単な例なのでこれだけ見ると単純な早解き勝負のように思われそうですが、実際には高度な考察や複雑な実装が要求される難しい問題が多く出題されます。

簡単な問題を解く

もう少し難しい例は後で別途見てみますが、とりあえず雰囲気を掴むためにこの簡単な問題を解けるコードをKotlinで書いてみます。

fun main() {
    val w = readln()
    println(w + 's')
}

特に面白くはないですが、これだけでもわかることがいくつかあります。
まず、一般的にプログラムとして意味を成すためには入力と出力が必要ですが、AtCoderも含めて多くのコンテストサイトでは標準入出力でそれを行うことになっています。
そのため、競プロの問題を解くこととは、ざっくり言えば標準入力で与えられた値をもとに何らかの計算や加工を行い、結果を標準出力で表示するコードを書くことであるということになります。
上記のコードはまさにそうなっていますね。

書いたコードは問題ページのフォームから提出します。提出すると即座にそのコードに対してテストが実行され、正解か不正解か出力されるみたいな感じです。

もうちょっと難しい問題

上記だと簡単すぎるので、もう少し難しい問題も見てみます。

たとえば以下のような問題です。

image.png

はて…これのどこが難しいのでしょうね？
あり得るA, B, Cの値を全部列挙して、条件を満たす組み合わせだったら件数をカウントアップすればいいのでは？

fun main() {
    val n = readln().toLong()

    var count = 0L
    for(a in 1..n) {
        for(b in 1..n) {
            for(c in 1..n) {
                if(b in a..c && a * b * c <= n) {
                    count++
                }
            }
        }
    }
    println(count)
}

しかし、これではダメです。
オーバーフローする？それもありますが、もっと大きな問題があります。

このコードを提出すると以下のような結果になります。

image.png

TLEはTime Limit Exceeded、つまりプログラムの実行が制限時間以内に終わらなかったということです。

よく見ると問題の上のほうに「実行時間制限: 2 sec」とあります。つまり2秒以内に実行が終わらないといけないが、それを超えてしまったということです。

さらによく見ると、入力値$N$の最大値は$10^{11}$とあります。それで3重ループですので、入力値が最大なら$10^{33}$回もループが回ります。一般的なPCだと1秒間に実行できるループ回数の目安はC++などの高速な言語でも$10^8$回程度とされています。ループ内の処理の重さにもよるので軽ければ$10^9$回くらいいけることもありますが、いずれにしても$10^{33}$回のループが2秒以内に終わるなど全然無理ってことがわかりますね。
この問題が特殊なわけでは全くなくて、むしろ実行時間を考えずにシンプルな実装をしただけだと通らないことがほとんどで、単純な実装だと終わらない処理をいかに現実的な実行時間で終わらせるかを考えるのが競プロの難しさと面白さです。

実際この問題をどうやって解くのか？まで踏み込むとさすがにこれ何のアドベントカレンダーの記事だっけ？ってなるのでこれくらいにしておきます。
簡単に言えば数学的考察により解きます。数学がある程度できる人なら特に難しいと思わないかも…？

私は数学が苦手なので苦労しましたが、この問題は以前頑張って解いたことがあるので、興味のある方は見てみてください。もちろんKotlinで解いています！

競プロにおける使用言語

使用可能な言語はコンテストサイトごとに異なりますが、AtCoderでは非常に多くの言語を使用することができ、Kotlinもそのうちの一つです。
競プロで最もよく使われるのはC++で、次点はPythonです。この2つが圧倒的で、他の言語を使う人は多くないです。
Kotlinは書きやすく、それなりの簡潔さとそれなりの実行速度を兼ね備えているのでけっこう競プロに向いていると思うんですが、残念ながら使う人は少ないです。もっと増えろ！

業務でのプログラミングと競プロの違いについて

業務でのプログラミングと競プロとでは本質的には違いはないですが、レイヤーが違います。なので、自分が直接書く表面上のコードではけっこう違いが出ます。

本題

すみません、前置きが長くなりました。ここからが本題です。業務ではあまり見ないが競プロではよく見るようなコードを紹介していきます。Kotlinで！

標準入力

基本

業務でのプログラミングでは標準入力で値を受け取るというような状況は非常に限られますが、競プロだと必須です。

上でも見ましたが、Kotlinだと組み込みの readln() 関数で標準入力から値を取得できます。

val s = readln()

（多少）高速な入力

他の方法として、以下のような書き方もあります。

val br = System.`in`.bufferedReader()
val s = br.readLine()

System.`in` は java.lang.System.in です。Kotlinだと in が予約語なのでバッククオートでエスケープが必要です。また、 System.in の型はInputStreamで、本来は bufferedReader() というメソッドはありませんが、Kotlinだと拡張メソッドで追加されています。これを使うと標準入力の値を読み込めるBufferedReaderのインスタンスを取得できます。
ちゃんと検証したわけじゃないですが、体感的にはこの書き方のほうが readln() を使うより速い気がします。

競プロだと $10 ^ 5$ 行など大量入力の場合があるため、多少の性能差がトータルだと実行時間にかなり影響します。 たいていは組み込みの readln() で問題ないと思いますが、それだと微妙に間に合わない場合はBufferedReaderを使うといいかもしれません。

複数行の入力を受け取る

どちらのメソッドにせよ一回の呼び出しで一行分のデータを読み取るので、行数の回数分メソッドを実行する必要があります。何行入力されるかはもちろん問題によって異なり、固定の場合もあれば固定でない可能性もあり、固定でない場合は何行入力されるのかという情報が先に入力されます。

そのような場合はループを回してもいいのですが、配列のコンストラクタで要素数と初期化するための関数を渡せることを利用して以下のようにも書けます。

val n = readln().toInt()
val array = IntArray(n) { readln().toInt() }

これで要素数がn個で、各要素として標準入力で受け取った値を格納した配列を生成できます。

半角スペース区切りの複数の値を受け取る

複数の値が入力される形式はいくつかバリエーションがあり、半角スペース区切りで全部一行で入力される場合もあります。
その場合はこのように受け取れます。

val array = readln().split(" ").map { it.toInt() }.toIntArray()

値の数が明確にわかっている場合は分割代入が使えます。

val (x, y) = readln().split(" ").map { it.toInt() }

ただ、標準だと5個までしか受け取れません。それを超える場合は拡張メソッドを生やせばいいようです。

val (a, b, c, d, e, f) = readln().split(" ").map { it.toInt() }

private operator fun <E> List<E>.component6(): E {
    return this[5]
}

半角スペース区切りで複数の値が一行で入力されるのがN行続くみたいなこともあります。
その場合は上記の組み合わせで二次元配列に格納します。

val n = readln().toInt()
val arrays = Array(n) {
    readln().split(" ").map { it.toInt() }.toIntArray()
}

配列

上記の例では、複数の値をListのような型ではなくIntArrayに格納していました。競プロだとIntArrayのようなプリミティブな配列はよく使います。そのほうが高速なためです。
配列は固定長なので一般的には不便ですが、競プロの場合は入力される個数や値の範囲が制約としてバッチリ決まっているため、固定長で問題ないケースが多いです。
また配列はミュータブルなのでイミュータブルなListと比べると安全ではないですが、競プロでは多少安全ではなくとも高速さを優先しなければならないことが多いです…
競プロのコードは継続してメンテするものではなく、複数人が手を加えるということもないので、そういう意味では安全さの重要性は相対的に低いというのもあります。

バケット

配列の使い方ですが、入力値を一時保存する以外にも様々な使い方があります。たとえば、バケットと呼ばれる簡単なデータ構造があります。

たとえば、「1からNまでの整数がランダムに入力される。Nや入力件数は十分小さいとする。各整数ごとの入力件数を答えよ」みたいな問題があったとします。
（実際の問題ではこんな曖昧な書き方となっていることはないですが、まあ例なので）

これはMutableMapを使ってカウントしていけば解けるのですが、配列を使って解く方法もあります。
以下のような感じです。

fun main() {
    // 入力
    val n = readln().toInt()
    val input = readln().split(" ").map { it.toInt() }

    // 結果を格納するバケット
    val bucket = IntArray(n + 1)

    // 数える
    input.forEach {
        bucket[it]++
    }

    // 結果出力
    for (i in 1 .. n) {
        println("$i ${bucket[i]}")
    }
}

つまり入力された各数値を添え字として、それに対応する値を配列の要素として格納します。整数限定の簡易的な連想配列のように使えます。
配列の要素数は N + 1 にします。 NだとN自体が入力された場合に範囲外になってしまうので+ 1 が必要です。
0番目が無駄になりますが、それはまあ仕方ありません。+ 1の個数を確保した上で0番目を無視することで、0-indexedが実質1-indexedに補正されたとも言えます。このような補正はよく使われます。

このやり方のメリットはMapを使った場合より少し速いのと、値が全て0で初期化されているのでシンプルにインクリメントするだけで扱えるので書くのが楽、などでしょうか。2
逆にデメリットはメモリを無駄に食うかもしれない点や正の整数しか扱えない点、ある程度気をつけて添え字を操作しないといけない点などでしょうか。あとは、要素数がある程度正確にわかっていないと使えません。（最低でも上限はわかっていないといけない）

Mapは動的に要素を追加していくので必要な分しかメモリを使わなくてすみますし、任意の型を使用できます。（キーはhashCode()を実装している必要はありますが）
動的に要素を追加するので、要素数が不明でも問題ありません。バケットより若干遅いとはいえ致命的な差ではないので、Mapのほうが間違いなく汎用性はあります。ただ、一つの書き方としてはバケットは面白いと思います。

ちなみにMapを使うならこんな感じでしょうか。

fun main() {
    // 入力
    val n = readln().toInt()
    val input = readln().split(" ").map { it.toInt() }

    // 結果を格納するMap
    val map = mutableMapOf<Int, Int>()

    // 数える
    input.forEach {
        map[it] = map.getOrDefault(it, 0) + 1
    }

    // 結果出力
    for (i in 1 .. n) {
        println("$i ${map[i] ?: 0}")
    }
}

標準出力

学習の段階では頻繁にお世話になる標準出力です。業務だとデバッグ以外で使うことは滅多にないでしょうけど、競プロだと標準出力で結果を返すので必ず使います。

ご存知の通り、基本的には println() を使えばいいです。

println("test")

ただ、競プロだと場合によってはこれだけだと問題になる場合があります。それは性能の問題です。
答えを一つ出力して終わりならいいのですが、$10 ^ 5$行など大量に結果を出力しなければならない場合があり、それだと単純に println()を呼び出す実装だとその性能がボトルネックになって通らない恐れがあります。

何が問題かというと、println()は標準出力に値を書き込むだけでなく、フラッシュも行うという点です。まあフラッシュしないと結果が出力されないので普通はそのほうがいいのですが、大量に出力する場合は毎回フラッシュされてしまって性能劣化を無視できなくなるわけです。なので、そのような場合は書き込んだ後に毎回明示的なフラッシュはせず、最後にフラッシュするようにすればいいです。

KotlinだとSystem.outをPrintWriterでラップすることでそれを実現できます。

val out = PrintWriter(System.out)
repeat(100000) {
    out.println("test")
}
out.flush()

out.をつけ忘れるとか、最後にflush()を呼ぶのを忘れるなどのミスがあり得るのであんまりやりたくないのですが… しかし性能は段違いです。

スタックの拡張

競プロでは再帰をよく使います。そして、入力値が大きい場合はスタックを食いつぶすほど再帰呼び出しの階層が深くなってしまう場合があります。その場合は（データ構造の）スタックを使って再帰をシミュレートするなどの方法で回避することもできますが、もっと簡単な方法としてスタックを拡張してしまうという手があります。

Thread(
    null,
    {
        // ここに処理を書く
    },
    "",
    128 * 1024 * 1024
).start()

具体的なやり方としては、スタックサイズを指定してスレッドを生成し実行します。第四引数がスタックサイズですね。ここでデフォルトよりは大きなサイズを指定することでスタックを潤沢に確保して実行できます。
実際これをやらないとエラーになる（逆にこれをやれば通る）問題には何度も遭遇しました。どうもKotlinは他の言語に比べてスタックオーバーフローを起こしやすいようでして、DFS（深さ優先探索）などのアルゴリズムを再帰で実装する場合は必ずこうしたほうがいいと思ったくらいです。

2024年10月追記

記事執筆時点からバージョンが上がっており、今のバージョンだと以前よりはスタックオーバーフローが発生しづらくなっているようです。

多倍長整数

多倍長整数とは、要するにLongの最大値を超えるような整数でも扱える型です。KotlinだとBigIntegerが使えます。
BigIntegerはJavaの標準ライブラリですが、Kotlinだと演算子オーバーロードによって楽に扱えますし、Stringなどの型がtoBigInteger()を持っていて簡単にインスタンスを得られるのでJavaで使うよりも使いやすくなっています。

val (a, b, c, d, e) = readln().split(" ").map { it.toBigInteger() }

println(((a * b * c) - (d * e)) % BigInteger("998244353"))

Kotlinだとnewが不要なのも地味に良い。

競プロ以外でも普通に使うかもしれませんが、個人的にはけっこう競プロで使うことがあったので取り上げてみました。

なお、競プロだと多倍長整数を使わないと解けない問題というのはないはずです。でないと標準で多倍長整数を持たない言語では現実的には解けないことになってしまうので。しかし、使うと楽をできる場合がそれなりにあります。

まとめ

結局Kotlinというより競プロの色が濃い記事になってしまいましたが、少しでも面白いと思っていただけたら幸いです。

業務でのプログラミングと競プロの違いについての蛇足

業務でのプログラミングと競プロではレイヤーが違うと書きましたが、どう違うと思っているのかを蛇足として追記します。

その違いについては、AtCoderが提供している競プロ用C++学習教材の以下の記述が本質をついていると思いました。

プログラムとは何のためにあるのでしょうか？
「便利なアプリを作るため」「ゲームをつくるため」「『人工知能』をつくるため」など、色々あると思います。
これらの具体例は決して間違いではありませんが、プログラミングにはより根源的な用途があります。
それは「計算」です。
コンピュータが開発された当初、その用途は高度な電卓でした。
それから月日が流れ、様々な用途に応用されるようになっても、最終的にコンピュータが行っていることが計算であることには変わりません。
「スマホで友達にメッセージを送信する」「ゲームで当たり判定をする」「機械翻訳をする」等は全てコンピュータの高度な計算能力に支えられています。
そして、その計算をするコンピュータを動かすのがプログラムです。

そういう意味だと、業務でのプログラミングはその「計算」を数え切れないくらいの様々な要素で何重にもラップします。計算結果が現実世界で価値を生むためにはそうするしかないのです。しかし、たしかに内部には「計算」が存在します。
そのラップをあえて全て剥がして「計算」の部分だけを取り出し、そしてそれをめっちゃ難しくしたのが競プロ、ということができそうではないでしょうか。
私は、競プロにおけるプログラミングは純粋に計算を行うという意味で「純粋プログラミング」と脳内では呼んでいます。
（※そんな言葉はありません）

以上、蛇足でした。

  1. 業務といっても色々ありますので、「私の知っている業務」でしかありません。具体的にはWebシステム、それも性能要件がそこまでキツくないシステムの開発のようなものを想定しています。実際には競プロとかなり近いことをやる業務も存在すると思います。たぶん。 ↩

  2. Mapより配列のほうが速いのは、配列の場合はメモリ上に値が連続しているのを利用して探索なしでピンポイントで目当ての要素を取得、更新できるためです。特に事前準備も要りません。しかし、Mapの場合はハッシュ値を求める処理がまず発生するのと、そのハッシュをもとに振り分けられた内部的なバケット内を探索するため若干遅くなります。ただ、ハッシュが衝突しまくっているなどのケースを除けば十分速いです。 ↩

14
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?