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

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

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

## [B - Get Closer](https://atcoder.jp/contests/abc246/tasks/abc246_b)
#### やりたいこと
原点(0,0)と点(A,B)を結んだ直線と、原点を中心とした半径1の円の交点を求めよう。
![246_b_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/e76c48da-4217-5a79-b0e5-a28632428655.png)
Aが0の場合、Bが0の場合、それ以外の場合の3パターンでそれぞれ処理していこう。

#### 入力値の取得
```kotlin
    val (a, b) = readLine()!!.split(" ").map { it.toInt() }
```
#### A = 0 の場合
A = 0 の場合、直線を式で表すと以下のようになる。
$x = 0$
![246_b_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/899e8284-3062-5d71-d690-f41264c5874c.png)
その場合答えとなる座標は(0,1)となる。入力制約により、**A=0の場合、Bは1以上になるのが保証されている。**
```kotlin
    var x = 0.0
    var y = 0.0
    if (a == 0) {
        y = 1.0
    }
```
#### B = 0 の場合
A = 0 の場合、直線を式で表すと以下のようになる。
$y = 0$
![246_b_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2597866/a5527822-3321-44fa-2f54-a987654c79b5.png)
その場合答えとなる座標は(1,0)となる。入力制約により、**B=0の場合、Aは1以上になるのが保証されている。**
```kotlin
    if (b == 0) {
        x = 1.0
    }
```

#### それ以外の場合（ A > 0 かつ B > 0 ）
A > 0 かつ B > 0 の場合、直線を式で表すと以下のようになる。
$y = (b/a)x$
また半径1の円を式で表すと以下のようになる。
$x^2+y^2=1$
この式のyに直線の式の右辺を代入すると以下のようになる。
$x^2+(b/a)^2*x^2=1$

これを組み替えると以下のようになり、xの値を求められる。
$x^2(1+(b/a)^2)=1$
$x^2 = 1 / (1+(b/a)^2)$
$x = \sqrt(1 / (1+(b/a)^2))$

これをKotlinで実装すると以下のようになる。
```kotlin
        x = Math.sqrt(1 / (1 + (b.toDouble() / a).let { it * it }))
```
xが定まればyも求めることができる
```kotlin
        y = x * b / a
```

#### サンプルコード
```kotlin:main.kt
fun main(args: Array<String>) {
    val (a, b) = readLine()!!.split(" ").map { it.toInt() }
    var x = 0.0
    var y = 0.0
    if (a == 0) {
        // A = 0 の場合
        y = 1.0
    } else if (b == 0) {
        // B = 0 の場合
        x = 1.0
    } else {
        // A > 0 かつ B > 0 の場合
        x = Math.sqrt(1 / (1 + (b.toDouble() / a).let { it * it }))
        y = x * b / a
    }
    println("$x $y")
}
```

## [C - Coupon](https://atcoder.jp/contests/abc246/tasks/abc246_c)
商品の値段がX円以上である場合、クーポン1枚につきX円が値引きされる。
商品の値段がX円未満である場合、1枚当たりの値引き額はX円よりも少なくなる。
#### やりたいこと
できる限り値引き額を最大化しよう。
1. X円以上の商品に対して、(商品価格/X)枚のクーポンを使用しよう。値引き後の商品は（商品価格 mod X)円の商品として扱おう。
1. クーポンが余った場合、残りの商品の内、より大きい値引き額となる商品からクーポンを使おう。

#### 入力値の取得
```kotlin
    val (n, k, x) = readLine()!!.split(" ").map { it.toLong() }
    val a = readLine()!!.split(" ").map { it.toLong() }.sortedDescending().toMutableList()
```
商品を降順ソートすることで、高額商品からクーポンを適用していく。
#### X円以上の商品に対してクーポンを使用
```kotlin
    // 残りクーポン数
    var remain = k
    for (i in a.indices) {
        if (a[i] < x) {
            // あらかじめ降順ソートしてあるため、これ以降は処理する必要はなし
            break
        }
        // 使うクーポンの枚数
        val useCoupon = Math.min(a[i] / x, remain)
        remain -= useCoupon
        // 値引き後の値段に変更
        a[i] -= (useCoupon * x)
        if (remain <= 0) {
            // クーポンを全て使い切った場合
            break
        }
    }
```
#### X円未満の商品に対してクーポンを使用した後合計を求める。
残りクーポン数が0より大きい場合、可能な限り使い切ってしまおう
```kotlin
    // 値引き額を最大化するため、再度降順にソートした上で、残りクーポン枚数分の商品を除外して合計を求める
    println(a.sortedDescending().drop(remain.toInt()).sum())
```
#### サンプルコード
```kotlin:main.kt
fun main(args: Array<String>) {
    val (n, k, x) = readLine()!!.split(" ").map { it.toLong() }
    val a = readLine()!!.split(" ").map { it.toLong() }.sortedDescending().toMutableList()
    // 残りクーポン数
    var remain = k
    for (i in a.indices) {
        if (a[i] < x) {
            // あらかじめ降順ソートしてあるため、これ以降は処理する必要はなし
            break
        }
        // 使うクーポンの枚数
        val useCoupon = Math.min(a[i] / x, remain)
        remain -= useCoupon
        // 値引き後の値段に変更
        a[i] -= (useCoupon * x)
        if (remain <= 0) {
            // クーポンを全て使い切った場合
            break
        }
    }

    // 値引き額を最大化するため、再度降順にソートした上で、残りクーポン枚数分の商品を除外して合計を求める
    println(a.sortedDescending().drop(remain.toInt()).sum())
}
```