AtCoder B,C問題をKotlinで解こう - ABC243

当記事ではAtCoder、ABCのB問題ならびにC問題（時々D問題も）のKotlinでの解法を超初心者向けに詳細に解説します。

https://atcoder.jp/contests/abc243/tasks

## [B - Hit and Blow](https://atcoder.jp/contests/abc243/tasks/abc243_b)
二つの配列から 「 **Hit** 」と「 **Blow** 」に相当する要素数を計上する。
![hitandblow.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/48af11ba-8270-4b1a-a2fd-2234fb51f282.png)
#### 入力値を取得しよう
```Kotlin
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    val b = readLine()!!.split(" ").map { it.toInt() }
```
#### **Hit** を計上しよう
配列a と 配列b は要素数が同じ。配列のインデックスごとに要素の一致を見ていく。
```Kotlin
    val hit = a.indices.count { a[it] == b[it] }
```
#### **Blow** を計上しよう
配列bの各要素のうち、配列aに同要素が含まれるものを計上する。
ここで計上された値はHitとBlowを含むため、Hitの値を引くことでBlowの値を得ることができる。
```Kotlin
    val aSet = a.toSet()
    val blow = b.count { it in aSet } - hit
```
:::note info
`b.count{ it in aSet }` ですが、`b.count{ it in a }` でも正常に動作はします。ただし、後者の場合、パフォーマンスが良くありません。入力制約次第では **TLE** となります。
ある値と同値がリストの中に含まれているかどうかを判定する処理は、リストの要素数が多い場合には何らかの工夫が必要になります。今回は `List<Int>` を `Set<Int>` へと変換することで、パフォーマンスを改善しました。
:::
#### サンプルコード
```Kotlin:main.kt
fun main(args: Array<String>) {
    // 入力値を取得
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    val b = readLine()!!.split(" ").map { it.toInt() }

    // Hitを計上
    val hit = a.indices.count { a[it] == b[it] }

    // Blowを計上
    val aSet = a.toSet()
    val blow = b.count { it in aSet } - hit

    // 答えを出力
    println(hit)
    println(blow)
}
```

## [C - Collision 2](https://atcoder.jp/contests/abc243/tasks/abc243_c)
ここでいう **衝突** は以下の条件が全て満たされた時に発生する。
1.  **同一のY** 上に **左向き** の人間と **右向き** の人間が存在する。
2.  **右向きの人間のX座標** < **左向きの人間のX座標** である。
![conflict1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/690b0747-6eb8-cf5b-c2e6-7363b2a3d55b.png)

#### やりたいこと
任意の2人について、それぞれ衝突するかどうかを全組み合わせについて判定するとTLEとなる。
入力された **人間をYの値でグループ分け** グループの中で衝突が発生するかどうかを判定しよう。
一つのYグループに該当する人間がたくさんいた場合はどうすればいいか？
衝突する要素があるかどうかの判定には、各グループごとに最もX値が小さい右向きの人間と最もX値が大きい左向きの人間のX値を比較すれば良い。
![衝突3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/bd53f460-c3ef-51a2-fe47-0096e9571dfb.png)
#### 入力値を取得しよう
```Kotlin:
    data class Person(val x: Int, val y: Int)

    val n = readLine()!!.toInt()
    val p = (1..n).map { readLine()!!.split(" ").map { it.toInt() }.let { Person(it[0], it[1]) } }
    val s = readLine()!!
```
#### Y値でグループ化しよう
右向きの人間を保持するMutableMapと左向きの人間を保持するMutableMapを用意して格納していく。Yをキーとする。
```Kotlin:
    // 左向きの要素を格納するMutableMap
    val toLeft = mutableMapOf<Int, Int>()
    // 右向きの要素を格納するMutableMap
    val toRight = mutableMapOf<Int, Int>()

    p.indices.forEach {
        if (s[it] == 'R') {
            if ((toRight[p[it].y] ?: 1_000_000_001) > p[it].x) {
                toRight[p[it].y] = p[it].x
            }
        } else {
            if ((toLeft[p[it].y] ?: -1) < p[it].x) {
                toLeft[p[it].y] = p[it].x
            }
        }
    }
```
:::note info
`?: 1_000_000_001` や `?: -1` は処理時点で該当グループに設定された値がなかった場合に確実に値をセットできるようデフォルト値を設定しています。`p.indicies.forEach` のブロックのは以下の書き方でも同じ処理です。
```Kotlin:
    p.indices.forEach {
        if (s[it] == 'R') {
            if (toRight[p[it].y] == null) {
                toRight[p[it].y] = p[it].x
            } else if (toRight[p[it].y]!! > p[it].x) {
                toRight[p[it].y] = p[it].x
            }
        } else {
            if (toLeft[p[it].y] == null) {
                toLeft[p[it].y] = p[it].x
            } else if (toLeft[p[it].y]!! < p[it].x) {
                toLeft[p[it].y] = p[it].x
            }
        }
    }
```
:::

#### 衝突が起こるか判定しよう
toRightとtoLeftの共通のY値について、最も左にいる右向きの人のX値と最も右にいる左向きの人のX値を比較することで衝突の判定を行う。
```Kotlin:
    for ((y, tr) in toRight) {
        toLeft[y]?.let { tl ->
            // toRight と toLeft で同じY値がある場合、このブロックの処理に入る
            if (tr <= tl) {
                // X値を比較、衝突が発生した
                return true
            }
        }
    }
    // 衝突は一度も発生しなかった
    return false
```

#### サンプルコード
```Kotlin:
fun main(args: Array<String>) {
    println(if (solve()) "Yes" else "No")
}

fun solve(): Boolean {
    data class Person(val x: Int, val y: Int)

    val n = readLine()!!.toInt()
    val p = (1..n).map { readLine()!!.split(" ").map { it.toInt() }.let { Person(it[0], it[1]) } }
    val s = readLine()!!

    // 左向きの要素を格納するMutableMap
    val toLeft = mutableMapOf<Int, Int>()
    // 右向きの要素を格納するMutableMap
    val toRight = mutableMapOf<Int, Int>()

    p.indices.forEach {
        if (s[it] == 'R') {
            if ((toRight[p[it].y] ?: 1_000_000_001) > p[it].x) {
                toRight[p[it].y] = p[it].x
            }
        } else {
            if ((toLeft[p[it].y] ?: -1) < p[it].x) {
                toLeft[p[it].y] = p[it].x
            }
        }
    }

    for ((y, tr) in toRight) {
        toLeft[y]?.let { tl ->
            // toRight と toLeft で同じY値がある場合、このブロックの処理に入る
            if (tr <= tl) {
                // X値を比較、衝突が発生した
                return true
            }
        }
    }
    // 衝突は一度も発生しなかった
    return false
}
```