Help us understand the problem. What is going on with this article?

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アプリ開発者からの参戦など、参加者が増えることを願っています。

良いところ

  • 簡潔な構文
  • 意味の通りやすいコーディング
  • 普通に速い
  • 第一級関数
  • Null安全設計による条件分岐がきれい
  • Swift Algorithm Club というGitHubリポジトリでアルゴリズムとデータ構造を学べる(結構充実しています) (https://github.com/raywenderlich/swift-algorithm-club)

悪いところ

  • ArrayやStringの扱いが少しめんどくさい
  • 引数の名前指定がめんどくさい
  • Null安全がたまにめんどくさい
  • 型に厳しすぎてめんどくさいときがある(例: いわゆる暗黙の型変換が存在しない)

心構え

一応システムプログラミング言語らしい(システムプログラミング言語: Wikipedia)ので

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

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

具体的には、安全性の面でいえば、イミュータブル、関数型プログラミングなどを意識します。
しかし速度やメモリのことを考えると、ミュータブルを過剰に嫌うのは違う気もしますので普通にvarキーワードは使います。

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

全体

main関数を作ってグローバル変数を少なくしたほうが速くなります。

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

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

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

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

main()

ポイント

  • readLine()!
  • Int(String)!
  • print関数
  • readLine()!.split(separator: " ").map{ Int($0)! }
  1. readLine関数は、標準入力を一行受け取る関数です。入力が無い場合を想定しているため、戻り値の型はOptional<String>(糖衣構文: String?)です。Optional型の値に対して!を後ろにつけると、「nilは入っとらん!」という主張のもと、強制アンラップされ、中身が取り出されます。AtCoderは入力を保証しているため、強制アンラップで問題ありません。

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

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

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

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

print(a, b)

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

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

readLines()!で得た文字列を、splitメソッドでスペース区切りで分割して配列にして、mapメソッドで各要素をIntに変換しています。mapメソッドは引数に(要素の型) -> 型クロージャ関数を受け取り、配列の各要素にその処理を適用し、新たなシーケンスを作ります。今回渡した関数の型は(Substring) -> Intです。

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

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

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

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

main()

ポイント

  • 三項演算子
  1. 三項演算子があります。「if 」はありません。残念です。

ABC081A - Placing Marbles

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

main()

ポイント

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

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

"123456789".reduce(0) { $0 + Int(String($1))! }
  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)

別解:

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)$ですので、Stringcountは十分高速です。

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) かどうかは、そのためのメソッドがあるのでそれでチェックします。

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

func main() {
    let _ = Int(readLine()!)!
    var A = readInt()

    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の波かっこなのか、クロージャの波かっこなのかの見分けが付かなくなるため、かっこは省略しません。

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

ABC087B - Coins

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. クロージャでタイピング数を減らせます。ありがたい。
    let read = { Int(readLine()!)! }
    let a = read()
    let b = read()
    let c = read()
    let x = read()

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

ABC083B - Some Sums

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

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

func main() {
    let line = readInt()
    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。

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

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

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

    print(alice - bob)
}

main()

ポイント

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

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

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. 同じ大きさの餅は重ねられない。

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

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 $

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

func main() {
    let line = readInt()
    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

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.count == 0 {
        print("YES")
    } else {
        print("NO")
    }
}

main()

ポイント

  • 競プロでは扱いづらい文字列
  • Setの初期化
  1. (Swiftの実装に詳しくないので間違っているかも知れません。) Swiftはなぜか文字列に対して数値でのアクセスができません。アクセスはRangeもしくはString.Indexでの部分文字列への参照のみ受け付けます。内部は複雑そうです。

しかたがないので、文字の配列に変換します。

let S = Array(readLine()!)

 
2. Setで型宣言をすると、配列を初期化するようにSetを初期化できます。ただの豆知識です。

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

別解:

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

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.count == 0 {
        print("YES")
    } else {
        print("NO")
    }
}

main()

ポイント

  • while let構文
A.first(where: { S.hasSuffix($0) })

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

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

while let a = optionalA {

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

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

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

ついでですが、

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

A.first(where: S.hasSuffix)

こうできます。

ABC086C - Traveling

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

func readInt() -> [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 = readInt()
        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()

ポイント

  • パターン代入

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

var (x_, y_, t_) = (0, 0, 0)
(x_, y_, t_) = (x, y, t)
conf8o
🐍, 🐦, λ, ☕
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした