Kotlinで競技プログラミングしてみた

弊社[リサーチ・アンド・イノベーション](https://r-n-i.jp/)では毎年[Google Code Jam](https://codingcompetitions.withgoogle.com/codejam)のQualification Roundに挑戦する文化があります。私は競技プログラミングはほんの少ししかやったことが無いですが、ふと普段Androidアプリ開発で使用しているKotlinでやるとどんな感じなんだろうと思い、やってみました。

# この記事は

普段Androidアプリ開発などでKotlinに慣れた人向けに、競技プログラミングにおける回答を作成できる環境作りやKotlinを使うメリットを紹介しようと思います。Google Code Jam 2020 Qualification Roundの最初の3問の回答も掲載しています。

# IntelliJ IDEA Community Editionをインストールする。

もしあなたが普段Androidアプリを開発しているとしたら、Android Studioがインストールされていると思います。しかし競技プログラミングはスマホアプリではなく、パソコンで動くコンソールアプリケーションなので、パソコンで動かすためのGradleプロジェクトを作成する必要があります。Android Studioにはその機能が含まれていないので、Android Studioの元となった、IntelliJ IDEAをインストールします。ダウンロードページにはUltimateとコミュニティがありますが、無料のコミュニティの方で問題ありません。

[ダウンロードリンク](https://www.jetbrains.com/ja-jp/idea/download/)

また、Android StudioとIntelliJ IDEAは共存できます。Android Studio 3.6とIntelliJ IDEA Community Edition 2019.3.3で確認しています。

# Kotlin Gradleプロジェクトを作成する

IntelliJ IDEAを起動して、`Create New Project`から`New Project`ダイアログを開き、左側で`Gradle`を選択して右側で`Kotlin/JVM`を選択して`Next`をクリックします。

![スクリーンショット 2020-04-05 21.41.25.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334798/3f8a59ae-3ff1-2dce-7eff-548104083d39.png)

`Next`をクリックして次のダイアログでは任意の`Name`と`Location`を設定して`Finish`をクリックします。

# 回答をプログラミングする

src/main/javaディレクトリに任意のパッケージを作成して、そこに任意のKotlinファイルを作成します。src/main/kotlinディレクトリでも良いです。

![スクリーンショット 2020-04-05 21.49.38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334798/9c945acc-30da-f9a6-84e2-6aae6d638e1c.png)

パッケージレベルファンクションmainから始まるプログラムを書きます。

```Q1.kt
package com.tfandkusu.codejam2020

fun main() {

}
```

入力は標準入力から行われます。Javaでの回答作成と同じようにjava.util.Scannerクラスを使います。inがKotlinの予約語なので標準入力の指定がSystem.\`in\`のようになってしまうがいけてないですが、もっと良い標準入力の方法は見つけられなかったので、これで行きました。

```kotlin
val reader = Scanner(System.`in`)
val t = reader.nextInt()
```

１問目は与えられた正方行列に対して、対角成分の合計、重複要素のある行の数、重複要素のある列の数を標準出力する問題になります。詳細は[Google Code Jam](https://codingcompetitions.withgoogle.com/codejam)のページでご確認頂ければ幸いです。全体の回答はこのようになりました。range式から始まり、map関数を後ろにつけて集計できる値に各要素を変換し、最後はsumByやcountで集計することで目的の整数を得ることができました。この書き方はforループを作るよりも可読性が高いと思います。

二次元配列の作成方法がJavaとは違うので注意が必要です。

```kotlin
package com.tfandkusu.codejam2020

import java.util.*

fun main() {
    val reader = Scanner(System.`in`)
    // テストケース数
    val t = reader.nextInt()
    (1..t).map { x ->
        // 正方行列の大きさ
        val n = reader.nextInt()
        // 正方行列を格納するための二次元配列を作成
        val m = Array(n) { IntArray(n)  /* 各要素を初期化するブロック */ }
        // 正方行列を読み込む
        (0 until n).map { i ->
            (0 until n).map { j ->
                m[i][j] = reader.nextInt()
            }
        }
        // 答えを作る
        // 対角成分の合計
        val k = (0 until n).sumBy { m[it][it] }
        // 重複要素のある行の数
        val r = (0 until n).map { m[it] }.map { it.distinct().size != n }.count { it }
        // 重複要素のある列の数
        val c = (0 until n).map { j -> (0 until n).map { m[it][j] } }.
            map { it.distinct().size != n }.count { it }
        // 結果出力
        println("Case #%d: %d %d %d".format(x, k, r, c))
    }
}
```

# コンソールで実行する

コンソールで実行できるように、`build.gradle`を書き換えます。`application`プラグインを取り込み、実行するクラス名を指定して、標準入力を受け取れるようにします。実行するクラス名は実行したいmain関数があるファイル名にKtをつけます。KotlinのパッケージレベルファンクションはJavaの世界では`ファイル名Kt`クラスに属するスタティックメソッドとして扱われるためです。

```build.gradle

plugins {
    id 'org.jetbrains.kotlin.jvm' version '1.3.61'
    // 実行できるようにする
    id 'application'
}

group 'org.example'
version '1.0-SNAPSHOT'

application {
    // 実行するクラス名を指定する
    mainClassName = 'com.tfandkusu.codejam2020.Q1Kt'
}

//noinspection GroovyAssignabilityCheck
run {
    // 標準入力を受け取れるようにする
    standardInput = System.in
}

// 以下略
```

問題文にあるサンプル入力をファイルとして準備します。

```q1.txt
3
4
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1
4
2 2 2 2
2 3 2 3
2 2 2 3
2 2 2 2
3
2 1 3
1 3 2
1 2 3
```

このようにgradlewコマンドを実行します。

```sh
./gradlew run < q1.txt
```

ビルドされ実行できました。

```
> Task :run
Case #1: 4 0 0
Case #2: 9 4 4
Case #3: 8 0 2

BUILD SUCCESSFUL in 0s
2 actionable tasks: 2 executed
```

# 提出する

IntelliJ IDEAで記述したソースコードをすべてGoogle Code Jamの提出ページにコピペして、左下の言語選択から`Kotlin`を選んで、`Submit attempt`ボタンを押せば提出できます。

![スクリーンショット 2020-04-05 23.20.00.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/334798/b8b4093a-036d-98ca-8377-cf97c9ffc73a.png)


# 2問目の3問目の回答

2問目と３問目の回答を記載します。回答することでコレクションに対して変換または集計を行う関数の知識を増やすことができました。

回答は提出して満点を頂いているものです。Qualification Roundは全部で5問ありますが、4問目と5問目は私には難解でしたので回答できて無く掲載していません。また問題の解説は詳細ではないので、詳細が気になる方は[Google Code Jam](https://codingcompetitions.withgoogle.com/codejam)のページでご確認頂ければ幸いです。


## 2問目

2問目は括弧の深さが整数に対応する文字列を出力する問題でした。

例えばこのような入力があれば

```
1
1243
```

このような出力になります。

```
(1(2((4)3)))
```


コレクションに対して`joinToString`メソッドを使うことで、引数ブロックの結果文字列を結合できることが新たな学びでした。当初は `map　{ /*略*/ }.joinToString(separator = "")`のように結合してたのですが、`joinToString`に統合できると、IntelliJ IDEAに教えて頂きました。賢いIDEを使えることがKotlinで回答することの魅力だと思いました。


```Q2.kt
package com.tfandkusu.codejam2020

import java.lang.Integer.max
import java.util.*

fun main() {
    val reader = Scanner(System.`in`)
    val t = reader.nextInt()
    (1..t).map { x ->
        val s = reader.next()
        // 現在レベル
        var d = 0
        val output = s.map { it - '0'  /* 文字を整数に変換 */ }.joinToString(separator = "") {
            val ret =
                // itのレベルまで下げる
                (0 until max(0, (d - it))).map { ')' }.joinToString(separator = "") +
                        // itのレベルまで上げる
                        (0 until max(0, (it - d))).map { '(' }.joinToString(separator = "") +
                        // itを出力
                        it.toString()
            // 現在レベルを記録する
            d = it
            // このブロックの結果を返却
            ret
        } +
                // 終端でレベル0になるようにする
                ")".repeat(d)
        // 結果を出力
        println("Case #%d: %s".format(x, output))
    }
}
```

## 3問目

3問目は活動に対して開始時刻と終了時刻があり、Cの人とJの人を被らないように活動に割り当てる問題でした。割当たらない活動があれば、`IMPOSSIBLE`と出力します。この問題では`sortBy`メソッドを活用しました。


```kotlin
package com.tfandkusu.codejam2020

import java.util.*

/**
 * 活動を表すデータ
 * @param s 開始時刻
 * @param e 終了時刻
 * @param i 何番目の活動か
 * @param cj CとJどっちがやるか
 */
data class Time(val s: Int, val e: Int, val i: Int, val cj: String)

fun main() {
    val reader = Scanner(System.`in`)
    val t = reader.nextInt()
    (1..t).map { x ->
        // 活動中配列
        val c = Array(24 * 60) { false }
        val j = Array(24 * 60) { false }
        val n = reader.nextInt()
        // 結果配列を作る
        val times = (0 until n).map {
            // 入力する
            val s = reader.nextInt()
            val e = reader.nextInt()
            Time(s, e, it, "")
        }.sortedBy {
            // 時系列にする
            it.s
        }.map { time ->
            // 活動中でない人に割り当てる
            if (!c[time.s]) {
                // 割当たったら、活動中の時刻をtrueにする
                (time.s until time.e).map { c[it] = true }
                // やった人を記録する
                time.copy(cj = "C")
            } else if (!j[time.s]) {
                (time.s until time.e).map { j[it] = true }
                time.copy(cj = "J")
            } else {
                time
            }
        }.sortedBy { 
            // 入力の順番に戻す
            it.i
        }
        // 結果出力
        var output = ""
        if (times.none { it.cj == "" })
        // すべての活動が割当たった
            output = times.joinToString("") { it.cj }
        else
        // 割当たらなかった活動がある
            output = "IMPOSSIBLE"
        println("Case #%d: %s".format(x, output))
    }
}
```