AtCoder に登録したら解くべき精選過去問 10 問を Swift 5 で解いてみた

元記事 https://qiita.com/drken/items/fd4e5e3630d0f5859067

問題 https://atcoder.jp/contests/language-test-202001

## AtCoder in Swift

2020年4月12日のAtCoder Beginner Contest 162(ABC162)より、Swiftのバージョンが`5.2.1`になりました。iOSアプリ開発者からの参戦など、参加者が増えることを願っています。

(追記) 過去問も`5.2.1`に対応しました。

### 良いところ

- 簡潔な構文
- 意味の通りやすいコーディング
- 普通に速い
- 第一級関数
- Null安全設計による条件分岐がきれい
- **Swift Algorithm Club** というGitHubリポジトリでアルゴリズムとデータ構造を学べる(結構充実しています) (https://github.com/raywenderlich/swift-algorithm-club)
  - 初心者向けの解説でときどき非効率的な実装があるのでご注意ください。

### 悪いところ

- ArrayやStringの扱いが少しめんどくさい
- 引数の名前指定がめんどくさい
- Null安全がたまにめんどくさい
- 型に厳しすぎてめんどくさいときがある(例: いわゆる**暗黙の型変換**が存在しない)
- 競プロで使える便利ライブラリが少ない

### 心構え

一応システムプログラミング言語らしい([システムプログラミング言語: Wikipedia](https://ja.wikipedia.org/wiki/システムプログラミング言語))ので

- 安全性
- 速度
- メモリ効率

この辺りは意識してみます。

### Swiftで競技プログラミングを始めるにあたって参考になる他の方の記事

本記事もできるだけ参考になりそうな内容にはしましたが、
下記の記事がより精査されていて、コメント欄での議論を含めとても充実しています。

* @kntkymt様. [[AtCoder]Swiftでも競プロがしたい！](https://qiita.com/kntkymt/items/4f02c6b90462f354de6d)(https://qiita.com/kntkymt/items/4f02c6b90462f354de6d) 
* @TARDIGRADE様. [Swift版 競プロ用チートシート(初心者向け)](https://qiita.com/TARDIGRADE/items/71b0a774d7f22418fdf5)(https://qiita.com/TARDIGRADE/items/71b0a774d7f22418fdf5) 

## 精選過去問 10 問解いてみた。

## 入力と出力について( PracticeA - Welcome to AtCoder )

```swift
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let a = Int(readLine()!)!
    let line = readInts()
    let s = readLine()!

    print(a + line[0] + line[1], s)
}

main()
```

ポイント

- `readLine()!`
- `Int(String)!`
- `print`関数
- `readLine()!.split(separator: " ").map{ Int($0)! }`

1. `readLine`関数は、標準入力を一行受け取る関数です。標準入力のEOF(End Of File)の際に`nil`を返すため、戻り値の型は`Optional<String>`(糖衣構文: `String?`)です。`Optional`型の値に対して`!`を後ろにつけると、「`nil`は入っとらん！」という主張のもと、**強制アンラップ**され中身が取り出されます。強制アンラップの結果が`nil`だとクラッシュするため、本来は慎重に使用すべきですが、EOFに達しないように使えば強制アンラップで問題ありません。

2. `Int(String)`は、渡された`String`型の値をもとに、`Int`型の値を作り出します。整数っぽくない文字列が渡される場合(`Int`型に変換できない場合)を想定しているため、戻り値の型は`Int?`です(変換できない文字列に対しては`nil`が返ります)。文字列が整数であると保証されている場合は`!`を後ろにつけて強制アンラップして構いません。

3. `print`関数は以下のような定義になっています。

```swift
func print(_ items: Any..., separator: String = " ", terminator: String = "\n")
```

引数`items`は可変長引数です。また、初期で`" "`(スペース)で区切って出力するようになっているので

```swift
print(a, b)
```

とすれば、aとbがスペース区切りで出力されます。

```swift
print(a, b, separator: "\n")
```

とすれば、aとbが改行区切りで出力されます。
4. 次はスペース区切りの数値入力についてです。そういう入力は頻繁にあります。

```swift
readLine()!.split(separator: " ").map { Int($0)! }
```

`readLine()!`で得た文字列を、`split`メソッドでスペース区切りで分割して配列にし、`map`メソッドで各要素を`Int`に変換しています。`map`メソッドは各要素に一定の処理を施し、新たな配列を作るメソッドです。引数に`(要素の型) -> 処理後の要素の型`というような**クロージャ**または**関数**を受け取ります。

上記のような記述は以下のような省略を経ています。

```swift
a.map({ (x: Substring) -> Int in Int(x)! })
// 型の省略
a.map({ x in Int(x)! })
// かっこの省略
a.map { x in Int(x)! }
// 引数の省略(第一引数 → $0, 第二引数 → $1 ...)
a.map { Int($0)! }
```

よく使うので関数化しました。

## ABC086A - Product

```swift
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let ab = readInts()
    print(ab[0] * ab[1] % 2 == 0 ? "Even" : "Odd")
}

main()
```

ポイント

- 三項演算子

1. `条件式 ? 真のときの値 : 偽のときの値` という形式で値を返す**三項演算子**という演算子を使った演算ができます。

## ABC081A - Placing Marbles

```swift
func main() {
    let a = readLine()!
    print(a.reduce(0) { $0 + Int(String($1))! })
}
 
main()
```

ポイント

- `reduce`メソッド

1. `reduce`メソッドは、要素に一定の処理を施し、結果をひとまとめにする(畳み込む)ためのメソッドです。渡す処理は引数を二つ(畳み込み先, 要素)受け取る必要があります。`reduce`メソッドの第一引数には畳み込み先の初期値が必要です。`Array`や`String`など、for文で回せるような**シーケンス**の型に実装されていることが多いメソッドです。

処理の流れは以下のようになっています。

```swift
"123456789".reduce(0) { total, x in 
    return total + Int(String(x))! 
}
```

1. total ← 0 (初期化)
2. total ← total + 1 (total == 1)
3. total ← total + 2 (total == 3)
4. total ← total + 3 (total == 6)
5. total ← total + 4 (total == 10)
6. total ← total + 5 (total == 15)
7. total ← total + 6 (total == 21)
8. total ← total + 7 (total == 28)
9. total ← total + 8 (total == 36)
10. total ← total + 9 (total == 45)

たとえ話をするなら、初期値は左手に持った粘土で、右手には次々追加で粘土が与えられるので、それを左手の粘土に混ぜ込むような感じです。
他にたとえるなら、わんこそばのように初期値は空腹で、次々そばが与えられるのでどんどん食べていくような感じです。

別解: (非推奨 追記: 2020/07/29)

```swift
func main() {
    let a = readLine()!
    print(a.filter { $0 == "1" }.count)
}
 
main()
```

ポイント

- `filter`メソッド
- `Array.count`, `String.count`などの`Collection.count`の計算量

1. `filter`メソッドもシーケンスの型によく実装されているメソッドで、渡したクロージャや関数の条件に合う要素をシーケンスから取り出し、新しいシーケンスを返します。
2. ~~`Collection.count`の計算量は、ランダムアクセスができるコレクションなら$O(1)$ですので、`String`の`count`は十分高速です。~~

`String.count`は$O(N)$です。。。(参考: https://qiita.com/kntkymt/items/4f02c6b90462f354de6d#%E7%AC%AC9%E5%95%8F-abc049c---%E7%99%BD%E6%98%BC%E5%A4%A2)

> The performance of some collection operations depends on the type of index that the collection provides. For example, a random-access collection, which can measure the distance between two indices in O(1) time, can calculate its count property in O(1) time. Conversely, because a forward or bidirectional collection must traverse the entire collection to count the number of contained elements, accessing its count property is an O(n) operation.
いくつかのコレクション操作のパフォーマンスはコレクションが提供するインデックスのタイプによって異なります。例えば、ランダムアクセスコレクションは二つのインデックスの距離をO(1)で測れるのでそのコレクションのcountプロパティはO(1)で計算できます。逆に順方向または双方向のコレクションはコレクションを総なめして含まれる要素の数を数えるので、そのコレクションのcountプロパティはO(N)の操作になります。

https://developer.apple.com/documentation/swift/collection

参考: https://qiita.com/_ha1f/items/bf12a761cd5e48b6f14d

## ABC081B - Shift only

A_1 ... A_N を2で割り切れなくなるまで割り続けます。`Array`などのシーケンスの要素**全て(all)** が、とある条件を **満たす(Satisfy)** かどうかは、そのためのメソッドがあるのでそれでチェックします。

```swift
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let _ = Int(readLine()!)!
    var A = readInts()
    
    var ans = 0
    while A.allSatisfy({ $0 % 2 == 0 }) {
        A = A.map { $0 / 2 } 
        ans += 1
    }
    
    print(ans)
}

main()
```

ポイント

- `/`(除算演算子)
- かっこを省略しないパターン

1. `Int`型の除算は小数点切り捨ての`Int`型です。また、型に厳しくいわゆる**暗黙の型変換**はないので除数、被除数の型は合わせる必要があります。`Int64 / Int32`のような計算もできません。

2. `A.allSatisfy({ $0 % 2 == 0 })`ですが、本来は`A.allSatisfy { $0 % 2 == 0 }`のようにかっこを省略できます。しかし、今回は`while`構文の条件式として使うため、かっこを省略すると`while`の波かっこなのか、クロージャの波かっこなのかの見分けが付かなくなるため、かっこは省略しません。

```swift
// 波かっこの見分けが付かない！
while A.allSatisfy { 
    $0 % 2 == 0 
} {
 // ...
}
```

## ABC087B - Coins

```swift
func main() {
    let read = { Int(readLine()!)! }
    let a = read()
    let b = read()
    let c = read()
    let x = read()

    var ans = 0
    for i in 0...a {
        for j in 0...b {
            for k in 0...c {
                if 500 * i + 100 * j + 50 * k == x {
                    ans += 1
                }
            }
        }
    }
    print(ans)
}

main()
```

ポイント

- 範囲を表すオブジェクト(`Range`)(糖衣構文: `s...e`)

1. 範囲の末尾を含める場合は`s...e`、含めない場合は`s..<e`です。

## ABC083B - Some Sums

問題文の通りに実装します。

```swift
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let line = readInts()
    let n = line[0]
    let a = line[1]
    let b = line[2]
    
    var ans = 0
    for i in 0...n {
        let x = i.description.reduce(0) { $0 + Int(String($1))! }
        if a <= x && x <= b {
            ans += i
        }
    }
    print(ans)
}

main()
```

ポイント

- `description`プロパティ

1. `description`(説明)**プロパティ**は、オブジェクトの説明を示すプロパティです。数値型は大抵そのまま文字列に変換します。**プロパティ**とは、**メソッド**と似ていますがかっこで呼び出さず文字通りプロパティとして扱いたい場合に実装されることが多いです。

## ABC088B - Card Game for Two

a_1 ... a_n を降順でソートし、奇数番目がAliceのもの、偶数番目がBobのものとすればOK。

Swiftではインデックスは0から始まるので、実装上は偶数がAlice, 奇数がBobとなります。

```swift
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let n = Int(readLine()!)!
    let A = readInts().sorted(by:>)

    var alice = 0
    var bob = 0
    for i in 0..<n {
        if i % 2 == 0 {
            alice += A[i]
        } else {
            bob += A[i]
        }
    }

    print(alice - bob)
}

main()
```

ポイント

- `sorted`メソッド
- `>`

1. `sorted`メソッドは`sorted()`と`sorted(by:)`メソッドがあり、引数の無いほうは昇順、`by`のあるほうは、任意の比較方法でソートすることが可能です。

```swift
readInts().sorted(by: >)
```

上記の処理は以下のような省略や変更を経ています。

```swift
a.sorted(by: { (a: Int, b: Int) -> Bool in a > b })
// 引数の省略
a.sorted(by: { $0 > $1 })
// Swiftの実装上、a > b は >(a, b) のように捉えるので「>」でOK
a.sorted(by: >)
```
　
2. 演算子は、関数またはメソッドと捉えて実装されています。適切なプロトコルを実装すれば、独自クラスに演算子を定義できます。

## ABC085B - Kagami Mochi

1. デカいほうから積み重ねれば良さそう。
2. 同じ大きさの餅は重ねられない。

全部違う餅なら並べ方は自明。餅の数が積み重なりの数になる。→ 重複削除した結果の個数が答え。

```swift
func main() {
    let n = Int(readLine()!)!
    let A = (1...n).map { _ in Int(readLine()!)! }
    let ans = Set(A).count

    print(ans)
}

main()
```

ポイント

- `Set`

**Set**型は**コレクション**型の一つで、**集合**を表現する型です。要素の重複を許容しません。また、順序を保持しません。インスタンス化の際に**シーケンス**を渡すと、要素の重複を削除したコレクションとなります。

## ABC085C - Otoshidama

三重ループは間に合わないので工夫します。

$ 2,000 × 2,000 × 2,000 = 8,000,000,000 = 8 × 10^9 $

$10^9$ 以上は大体間に合いません。

一定数選ぶことになっているため、二種類の個数を決めれば、三種類目の個数を割り出すことができます。

```swift
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let line = readInts()
    let N = line[0]
    let Y = line[1]

    for i in 0...N {
        for j in 0...(N-i) {
            let k = N - i - j
            if 10000 * i + 5000 * j + 1000 * k == Y {
                print(i, j, k)
                return
            }
        }
    }
    print("-1 -1 -1")
}

main()
```

Swiftに関して特記すべきポイントはありません。

## ABC049C - 白昼夢

後ろから部分文字列を構成していきます。ある時点での部分文字列が`["dream", "dreamer", "erase", "eraser"]`どれかに一致するなら部分文字列を空文字にリセットし、部分文字列の構成を再開します。
8文字以上の文字列を作った場合や、最終的に文字列が余った場合はNO

```swift
func main() {
    let S = Array(readLine()!)
    let n = S.count
    let A: Set = ["dream", "dreamer", "erase", "eraser"]

    var s = ""
    for i in 1...n {
        s.insert(S[n-i], at: s.startIndex)
        if s.count > 7 {
            print("NO")
            return
        }
        if A.contains(s) {
            s = ""
        }
    }

    if s.isEmpty {
        print("YES")
    } else {
        print("NO")
    }
}

main()
```

ポイント

- 競プロでは扱いづらい文字列
- `Set`の初期化

1. (Swiftの実装に詳しくないので間違っているかもしれません。) Swiftはなぜか文字列に対して数値でのアクセスができません。`String.Index`という型によるアクセスを受け付けます。おそらく文字のバイトサイズが関係してそうです。

わかりやすくするため、文字の配列に変換します。

```swift
let S = Array(readLine()!)
```
　
2. `Set`で型宣言をすると、配列を初期化するように`Set`を初期化できます。ただの豆知識です。

```swift
let A: Set = ["dream", "dreamer", "erase", "eraser"]
```

別解:

`hasSuffix`メソッドで、文字列の尻尾が引数の文字列と一致するかを調べることができます。

```swift
func main() {
    let A = ["dream", "dreamer", "erase", "eraser"]
    var S = readLine()!

    while let a = A.first(where: { S.hasSuffix($0) }) {
        S.removeLast(a.count)
    }

    if S.isEmpty {
        print("YES")
    } else {
        print("NO")
    }
}

main()
```

ポイント

- `while let`構文

```swift
A.first(where: { S.hasSuffix($0) })
```

まず`first`メソッドですが、これはシーケンスの要素を順に見ていって、最初に条件にあった要素を返すメソッドです。見つからない場合が想定されているため、戻り値の型は`Optional<E>`です。(見つからない場合は`nil`が返ります)

`Optional`に中身がある場合と無い場合での分岐は頻繁に見られますのでそのための構文が用意されています。

```swift
while let a = optionalA {
```

上記のような構文は、「optionalA(`Optinal`型)に中身がある場合、aに中身を代入してループする」という意味です。

if文も、条件を求める構文なのでこのような記述が可能です。

```swift
if let a = optionalA {
    // ...
} else {
    // ...
}
```

ついでですが、

```swift
A.first(where: { S.hasSuffix($0) })
```

↓

```swift
A.first(where: S.hasSuffix)
```

こうできます。

## ABC086C - Traveling

現時点から次の地点まで、手数が足りる、かつ手数と**マンハッタン距離**(格子をジグザグに進んだときの距離)の偶奇が一致するという条件をクリアし続ければYes、途中でダメだったらNo

```swift
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let N = Int(readLine()!)!

    var (t_, x_, y_) = (0, 0, 0)
    for _ in 1...N {
        let line = readInts()
        let t = line[0]
        let x = line[1]
        let y = line[2]

        let dT = t - t_
        let dX = abs(x - x_)
        let dY = abs(y - y_)
        if dT < dX + dY {
            print("No")
            return
        }

        if dT % 2 != (dX + dY) % 2 {
            print("No")
            return
        }
        (t_, x_, y_) = (t, x, y)
    }

    print("Yes")
}

main()
```

ポイント

- パターン代入

タプルによる**パターン記法**でまとめて代入できます。

```swift
var (x_, y_, t_) = (0, 0, 0)
```

```swift
(x_, y_, t_) = (x, y, t)
```