LoginSignup
30
25

More than 3 years have passed since last update.

@conf8o(conf8o)

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

Last updated at Posted at 2020-04-06

元記事 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)ので

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

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

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

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

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

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

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関数は以下のような定義になっています。

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

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

print(a, b)

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

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

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

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

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

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

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 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

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

main()

ポイント

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

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

"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)

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://qiita.com/_ha1f/items/bf12a761cd5e48b6f14d

ABC081B - Shift only

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

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

// 波かっこの見分けが付かない！
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. 範囲の末尾を含める場合はs...e、含めない場合はs..<eです。

ABC083B - Some Sums

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

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となります。

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のあるほうは、任意の比較方法でソートすることが可能です。
readInts().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 $

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

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

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

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という型によるアクセスを受け付けます。おそらく文字のバイトサイズが関係してそうです。

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

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.isEmpty {
        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 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()

ポイント

  • パターン代入

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

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

(x_, y_, t_) = (x, y, t)
30
25
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
30
25