[AtCoder]Swiftでも競プロがしたい！

普段はiOS/Androidのアプリ開発をしている自分ですが、ここ最近競技プログラミングの人気が爆上がりしている¹ という噂は聞いており、やろうかなと思っていた所...
AtCoderでSwift5.2が使える様になった との情報を耳にしたのでこの機に競技プログラミングを初めてみました！

そうです！Swiftはできる子なんだってところを競技プログラミング界に知らしめてやりましょう！

この記事では、　AtCoderをSwiftで初めてみた体験記 と、 Swiftを使っている方々が競技プログラミングを始めやすいように解説 の二つを兼ねて、AtCoder&競技プログラミングの導入から Swiftを使ってコンテストに参加する までを紹介していきます！

本記事では、AtCoderホームページのスクリーンショットの掲載や問題文の引用を行っています。それらはこの記事の著者の著作物ではなく、一切の権利はAtCoderに帰属します。

• AtCoderへの登録
• 練習用コンテストでコンテストの流れを体験する
• Swiftで「AtCoder Beginners Selection」を解く
  • Xcodeでのコーディング・テスト環境を整える
  • Swiftでの標準入力などの操作の確認
  • 問題を解く
• コンテストに参加する
• 過去問を解く

AtCoderへの登録

公式サイトにアクセスして、右上の「新規登録」からアカウントを登録します

• 公式サイト: https://atcoder.jp/

コンテストの流れを体験する

さて、登録ができたところで
AtCoderに用意されている、練習用コンテストからコンテストの流れを確認してみましょう
今後のコンテストや過去問を解く場合と同じ手順になっています。

• 練習用コンテスト: https://atcoder.jp/contests/practice

「参加登録」ボタンをクリックすると、上のタブに「問題」が追加されるのでクリックします。

クリックすると、問題が表示されます。
この様に、コンテストに参加し、コンテストが開始されると問題が表示されます。

補足:
コンテストではコンテスト時間内に問題を解いていくことになるのですが
練習用ページなのでコンテスト時間は 2012-06-25(月) 00:00 ~ 2038-01-19(火) 12:14 と、実質無制限になっています。

この練習ページでは問題が2つ用意されているようです。

• A: Welcome to AtCoder
• B: Interactive Sorting

どうやらB問題は初心者向けではないらしいので、A問題だけ解いてみます。

A: Welcome to AtCoder

問題文
高橋君はデータの加工が行いたいです。
整数 $a, b, c$と、文字列 $s$ が与えられます。
$a + b + c$ の計算結果と、文字列 $s$ を並べて表示しなさい。

制約
$1 ≤ a, b, c ≤ 1,000$
$1 ≤ | s | ≤ 100$

入力
$a$
$b$ $c$
$s$

出力
$a + b + c$ と $s$ を空白区切りで 1行に出力せよ。

AtCoderWebサイトより引用

解答

問題ではこの様に 問題, 制約, 入力, 出力が与えられます。
また、いつくかの入力例とそれに対する出力例も記載されています。

ページを下にスクロールすると、解答提出欄が出てくるので
言語でSwiftを選択します。

ここにプログラムを記述し、提出することで問題に解答します。

いろいろな言語が使えるようですね。
また、この問題は練習用なのでいくつかの言語の解答例が乗っています。
(残念ながらSwiftはありません )

とりあえず流れの確認ということなので、パパッと解いてしまいましょう。
こんな感じになります。

// 標準入力からIntを読み込む
let a = Int(readLine()!)!

// 標準入力からInt配列を読み込む
let bc = readLine()!.split(separator: " ").map { Int(String($0))! }

// 標準入力から文字列を読み込む
let s = readLine()!

// bcは配列なので、bc[0]にb bc[1]にcが入っている
let sum = a + bc[0] + bc[1]

// スペース区切りで出力
print(sum, s)

これでOK！提出！

と行きたいことろですが...少し心配ですね...
タイプミスをしていてコンパイルエラーになっているかもしれませんし、そもそも間違った解答をしているかもしれません...

そんな時は！ページの上のタブから「コードテスト」を開き、テストをしてみましょう。

ソースコードに書いたコードを貼り付け
標準入力に問題のページのサンプル入力をコピーして貼り付け、実行しましょう。

サンプル出力と同じ出力が出てきたら成功です。

補足:
実際の提出では、サンプル入力以外にも複数個(10~200程度)の入力でテストされ、全てに正解しなければいけないため、サンプル入力に正解できたからと言って提出が正解になるとは限りませんので注意してください

確認もできたので、提出をしましょう。
提出ボタンを押すと、提出結果画面に切り替わるので結果が出るのを待ちます。

補足:
なお、もし提出した回答が不正解になっても、何度でも再提出できます。
ペナルティと言う物があるのですが、これは(おそらく)レーティングやパフォーマンスに関係する物なので、最初はあまり気にしなくてもいいかもしれません。

「AC」と結果が出ました！これは「正解」という意味です。

補足:
「AC」は Accepted の略で、「解答がテストをパスし、正解と判定された」ということらしいです。
その他の結果は以下を参照してください。

• 用語集: https://atcoder.jp/contests/abc074/glossary

これで問題を1つ解くことができました！
この「問題文を読む→コーディングをする→(テストをする)→解答する」が問題を解く一つの流れとなっています。
本当のコンテスト、例えば初心者向けのABC(AtCoder Begginer Contest)では100分で6問出題されるので時間内にどんどん問題を解き進めていくことになります！

AtCoder Beginners Selection を解く

さて、コンテストの流れもわかったので早速コンテスト！

と、いきたいところですが...まだ少しどんな問題が出るか心配ですし
コンテストは主に土日の21時からやっていることが多いようで、いつでも参加できるわけではないようです。

そこで、AtCoder Beginners Selection という初心者用の問題集があるらしいのでやってみましょう！

準備をする

と、その前に...

先ほどはコンテストページで直接コーディングし、テストもしましたが
SwiftだったらXcodeでコーディングしたいし、テストもXcodeでやっちゃいたいです。
なので、コーディング環境の準備をしてから問題に臨みましょう。

コーディング&テスト環境の準備

Xcodeを開き、Create a new Xcode Project から macOS の Command Line Tool を選択します

補足:
最初、Playgroundでやろうと試して見たのですが、Playgroundでは標準入力が行えないようなので、普通のProjectでやることにしました。

言語がSwiftになっていることを確認し、作成します。
名前と場所はお好みで。

作成ができたらいつも見慣れた画面になると思います。

これでコーディングとテストはXcode上で快適に行えるようになりました。
ここでコーディング・テストをしたらAtCoderの提出欄にコピペし、提出すれば良いわけです。

また、標準入力/出力は右下のウィンドウで確認できます。
実行してもウィンドウが表示されない場合は右上のボタンをクリックしましょう。
標準入力の受付が始まっても何も表示されないので、「動いてるのかな？」と思っちゃいますが、動いてます。大丈夫です。ウィンドウに入力をしてEnterを押せば動きます。

こんな感じでXcodeの準備は完了です！

なお、2020/07/26現在AtCoderのSwiftのバージョンは 5.2.1 であり、これはXcode11.4に対応します²
つまり、Xcode11.4.1以上のバージョンのXcodeを使っている方は提出環境とSwiftのバージョンが異なるため
(メジャーバージョンが変わらない限りほとんどないとは思いますが)
「Xcodeでは実行できたのに提出したらコンパイルエラーになった」なんてこともあり得ます。
心配な方は、練習コンテストでやったようにAtCoderのコードテストページを利用するか、AtCoder用にXcode11.4をダウンロードして利用しましょう。

私はMacの容量がカツカツなので心配な時はAtCoderのコードテストページを使うことにします...

• 公式ダウンロード: https://developer.apple.com/download/more/

また、どうやらAtCoderではLinux上でSwiftを動かしているためか(?)使えるライブラリには限りがあります。
Foundation(NS系のクラスやsqrt()など)は動作を確認したのですが、AppKit(UIKitのmacOS版)などはコンパイルエラーになりました。
おそらく、Foundationくらいしか使う機会がないと思うので大丈夫だとは思います...。

操作の確認

練習用コンテストではプログラムについてはサラッと流してしまったので
ちょっとだけ競プロに使う基本的な操作を確認しておきましょう。

標準入力

標準入力(String)

let line = readLine()!

readLine()は一行をString?型で読み込みます。
オプショナルになっているのでアンラップしましょう。

むむ...強制アンラップ...guardしなきゃ...という気持ちは抑えてください。
プログラムが落ちた場合は「問題文の入力形式を読み間違えている」という Logic failure³です

また、Int型などで扱いたい場合はキャストし、
複数の値が入ってくる場合は配列で取得しましょう。

標準入力(Int)

let number = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }

補足:
数列の入力はreadLine()!.split(separator: " ").map { Int($0)! }のようにStringを挟まずに取得可能ですが
2021/07/19現在のAtCoderのSwiftのバージョンである5.2.1ではこのコードは遅く
解答が TLE(実行時間超過) になってしまう場合があるので、一度Stringへの変換を挟む必要があります。
詳しくは以下の記事を参照してください。

• 競プロerはSwiftでSubstringを直接Intに変換してはいけない
  https://zenn.dev/koher/articles/swift-kyopro-substring-to-int

この辺りの処理はメソッド化して、コピペできる様にしておくと便利です
一行に2値入ってくる場合、一々numbers[0], numbers[1]と指定するのが面倒なのでタプルで取得できるメソッドも追加しちゃいましょう。

AtCoderでは複数の値の場合、形式はスペース区切りで統一されているようなので、split(separator: " ")でベタ書きしちゃいます。

標準入力のテンプレートメソッドたち

func readInt() -> Int {
    return Int(readLine()!)!
}

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

func readTwoInts() -> (a: Int, b: Int) {
    let ints = readLine()!.split(separator: " ").map { Int(String($0))! }
    return (a: ints[0], b: ints[1])
}

let number = readInt()
let numbers = readInts()
let (x, y) = readTwoInts()

標準出力

標準出力

let n = 10

print("YES") // >YES\n
print(n, "YES") // >10 YES \n

// 引数は何個でも指定可能
print(n, "YES", "NO") // >10 YES NO\n

文字列展開を使ってprint("\(n) YES")と書きそうになりましたが...
AtCoderではスペース区切りで出力する形式が多いっぽいので、自動で半角スペースを入れてくれる複数引数の方法が重宝しそうです。

ループ

いろいろなループ

let numbers = readInts()

var sum = 0
for i in 0..<numbers.count {
    sum += numbers[i]
}
for number in numbers {
    sum += number
}
numbers.forEach { number in
    sum += number
}
// 引数名省略
numbers.forEach { sum += $0 }

お好きなのをお使いください。

ただ、.forEachなどの高階関数系はbreak, continue等のハンドリングができなかったりしたり、インデックスによる細かい処理がしにくかったりするため
.forEachなどの高階関数系は簡単なループを行う場面で使い、それ以外では普通のforを使うのが良いかと思います。

ちなみに.forEachでインデックスを使いたい場合は.enumrated()を使います

numbers.enumrated().forEach { (index, element) in
    ...
}

問題を解く

さて...準備が整ったところでいよいよ問題を解いていきましょう。

以下、解答が乗っているので自分の力で解きたい方は閲覧注意です。

第1問: ABC 086 A - Product

問題文
シカのAtCoDeerくんは二つの正整数 $a, b$ を見つけました。$a$ と $b$の積が偶数か奇数か判定してください。

制約
$1 ≤ a, b, c ≤ 1,000$
$a,b$ は整数

入力
$a$ $b$

出力
積が奇数なら 'Odd' と、 偶数なら 'Even'と出力せよ。

AtCoderWebサイトより引用

解答

この問題は「A問題」と言われている簡単な部類の問題で、if, switch等の条件分岐ができれば解ける問題になっているそうです。(ループを使わなくても解ける問題になっているらしい)

ABC(AtCoder Beginner Contest) という初心者用のコンテストでは「A, B, C, D, E, F」の6問構成となり、後ろに行くほど難しい問題になる(ことが多い)という構成になっているようで、
配点も「100, 200, 300, 400, 500, 600」となっている(ことが多い)ようです。
問題のID(?)からも ABC086'A' と、どのレベルの問題なのかがわかります。

今回は、二整数の積の偶奇を判定するだけなので、愚直に実装します。

func main1() {
    let (a, b) = readTwoInts()
    let result = a * b
    print(result.isMultiple(of: 2) ? "Even" : "Odd")
}

main1()

準備で作成したreadTwoInts()メソッドを活用していきます。
偶数の判定をresult % 2 == 0ではなくisMultiple(of: 2)といった感じで記述できるのは可読性の高い思想を持ったSwiftの良さですね。

余談ですが、個人的にSwiftのメソッドの引数のラベルと外部引数名のシステムがとても気に入っていて、
外部引数名をラベルとして利用できることによってメソッド名を冗長にすることなく、表現力の高いメソッドを記述することができ、結果として可読性の高いプログラムを書くことができるためです。
今回の例では、result.isMultiple(of: 2)はresult is multiple of 2と、自然な英文のようにメソッドをの処理を読むことができます。

補足:
Swiftはトップレベルでコードを記述できますが
処理の途中でreturnを使って一気に処理を終了させたりした場合があるので
「問題ごとにメソッドを定義し、メソッド内に処理を記述してトップレベルでメソッドを実行する」という形でやっていきます。
提出欄にコピペする際に、main1()をコピペし忘れると何も実行されずに終わって不正解になってしまうので注意してください！

第2問: ABC081A - Placing Marbles

問題文

すぬけ君は $1, 2, 3$の番号がついた $3$ つのマスからなるマス目を持っています。 各マスには '0' か '1' が書かれており、マス $i$ には $s_i$が書かれています。

すぬけ君は $1$ が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。

制約
$s_1s_2s_3$は'1' あるいは '0'

入力
$s_1s_2s_3$

出力
答えを出力せよ。

AtCoderWebサイトより引用

解答

「ビー玉」や「マス」などの単語は出てきていますが、結局のところ 「入力の3つの数字の中に1はいくつありますか」 という問題です。
また、数字が0or1のため、各桁の数字の和を取ってしまえば答えになります。

func main2() {
    let string = readLine()!

    let count = string.reduce(0) { (sum, part) in sum + Int(String(part))! }
    print(count)
}

main2()

今回はスペース区切りではなく、'1' or '0'が3つ連続して入ってくるためString型で受け取り、処理します。
愚直にfor文を用いて記述してもよかったのですが、せっかくなのでreduceを使って「1文字を取得→Intにキャスト→加算」という方法で実装して見ました。

補足:
String型はSeaquenceプロトコルに準拠しているため、map, filter, reduce等を用いて1文字づつ処理ができます。

第3問: ABC081B - Shift only

問題文
黒板に $N$ 個の正の整数 $A_1,...,A_N$ が書かれています．

すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．

黒板に書かれている整数すべてを，$2$ で割ったものに置き換える. すぬけ君は最大で何回操作を行うことができるかを求めてください．

制約
$1 ≤ N ≤ 200$
$1 ≤ A_i ≤ 10^9$

入力
$N$
$A_1$ $A_2$ $...$ $A_N$

出力
すぬけ君は最大で何回操作を行うことができるかを出力せよ．

AtCoderWebサイトより引用

解答

これはB問題です。
A問題よりかは少し複雑になってはいますが、B問題は 普段アプリケーション開発等のプログラミングをしていれば、競技プログラミングの知識・対策ゼロでも解けるレベル くらいなんじゃないかなと思っています。
また、アプリケーション開発等をしたことがない方にとっても、プログラミング言語自体を学ぶ上でいずれは通るレベル (プログラミング言語の入門書や学習サイトの演習問題に乗っていてもおかしくないような問題)だと思います。

今回の問題は、基本的には問題文通りに 「『入力の配列要素が全て偶数であれば全ての配列要素を2で割る』という動作を繰り返し、何回行えたかを数える」 という処理を書いていけばいけます。

func main3() {
    let N = readInt()
    var numbers = readInts()

    var count = 0
    while numbers.allSatisfy({ $0.isMultiple(of: 2) }) {
        count += 1
        numbers = numbers.map { $0 / 2 }
    }

    print(count)
}

main3()

SwiftのSeaquenceにはallSatisfy()という「全ての要素が引数のクロージャーの条件を満たすかどうか」を調べる便利なメソッドがあるので、利用します。
$0と言うのはクロージャーでの引数名を定義せず番号で指定する方法です。
全ての配列要素を2で割る処理も、map()を利用します。

かなり綺麗に記述できているんじゃないかと思います。やっぱりSwiftは最高だぜ！
競技プログラミングにおいては、プログラミングではなくアルゴリズムに集中したいので、余分な記述が少なく、可読性が高い言語を使うのは結構理に適ったことなんじゃないかなと思います。

第4問: ABC087B - Coins

問題文
あなたは、 $500$ 円玉を $A$ 枚、$100$ 円玉を $B$ 枚、$50$ 円玉を $C$ 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど $X$ 円にする方法は何通りありますか。

同じ種類の硬貨どうしは区別できません。$2$ 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約
$0 ≤ A, B, C ≤ 50$
$A + B + C ≥ 1$
$50 ≤ X ≤ 20,000$
$A, B, C$は整数である
$X$は$50$の倍数である

入力
$A$
$B$
$C$
$X$

出力
硬貨を選ぶ方法の個数を出力せよ。

AtCoderWebサイトより引用

解答

ちょっと条件とかが複雑になってきましたね...

どう解けばいいんだ...?賢い解き方があるのか...?と考えていたのですが
これは深読みし過ぎず、普通に全探索で**「ありうる全てのA, B, Cの組み合わせを試し、合計金額がX円になる組み合わせがいくつあるか数え上げる」**という方法で良いようです。
愚直に3重for文を書きました。

func main4() {
    let A = readInt()
    let B = readInt()
    let C = readInt()
    let X = readInt()

    var count = 0
    for i in 0...A {
        for j in 0...B {
            for k in 0...C {
                if X == (500 * i) + (100 * j) + (50 * k) {
                    count += 1
                }
            }
        }
    }

    print(count)
}

main4()

第5問: ABC083B - Some Sums

問題文
$1$ 以上 $N$ 以下の整数のうち、$10$ 進法での各桁の和が $A$ 以上 $B$ 以下であるものの総和を求めてください。

制約
$1 ≤ N ≤ 10^4$
$1 ≤ A ≤ B ≤ 36$
入力は全て整数である

入力
$N$ $A$ $B$

出力
$1$ 以上 $N$ 以下の整数のうち、$10$ 進法での各桁の和が $A$ 以上 $B$ 以下であるものの総和を出力せよ。

AtCoderWebサイトより引用

解答

こちらも問題文通りに愚直に実装します。

func readThreeInts() -> (a: Int, b: Int, c: Int) {
    let ints = readLine()!.split(separator: " ").map { Int(String($0))! }
    return (a: ints[0], b: ints[1], c: ints[2])
}

func main5() {
    let (N, A, B) = readThreeInts()

    var sum = 0
    for i in 1...N {
        let result = String(i).reduce(0) { (sum, part) in sum + Int(String(part))! }
        if A <= result, result <= B {
            sum += i
        }
    }

    print(sum)
}

main5()

3変数の入力が出てきたのでreadThreeInts()を追加です。

第2問で出てきたStringのreduce処理がまた出てきました。
「各桁の和を算出する」はよくある処理なのでしょうか...?

余談ですが...SwiftのifでANDは,と&&のどちらでも良く、個人的にはタイピングが楽なので,の方が好きなのですが、&&の方が「アンド」という意味をそのまま表現しているし、「,」じゃ知らない人にとっては意味が曖昧なのでif-letでもない普通の条件文で用いるのは可読性的にはグレーかもしれませんね...

第6問: ABC088B - Card Game for Two

問題文
$N$ 枚のカードがあります. $i$ 枚目のカードには, $a_i$ という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に $1$ 枚ずつカードを取っていきます. Alice が先にカードを取ります.
$2$ 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. $2$ 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

制約
Nは$1$以上$100$以下の整数
$a_i$($1 ≤ i ≤ 100$)は$1$以上$100$以下の整数

入力
$N$
$a_1$ $a_2$ $...$ $a_N$

出力
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.

AtCoderWebサイトより引用

解答

「両者が最適な戦略を取った時」というのがキーワードです。
まずAliceが一番目に値が大きいカードを取り、Bobが二番目に値が大きいカードをとり、Aliceが三番目に値が大きいカードを取り...と行動するので

カードをカードの値で降順ソートをしてしまえば
Aliceはインデックス0, 2, 4, 6...
Bobはインデックス1, 3, 5, 7...
と取っていくことになります。

つまり、「入力の配列を降順にソートして、偶数番目のインデックスの値をAliceの得点, 奇数番目のインデックスの値をBobの得点とする」 という処理を書けばいいわけです。

func main6() {
    let N = readInt()
    let numbers = readInts()

    var alice = 0
    var bob = 0

    numbers
        .sorted(by: >)
        .enumerated()
        .forEach { (index, element) in
            if index.isMultiple(of: 2) {
                alice += element
            } else {
                bob += element
            }
        }

    print(alice - bob)
}
main6()

sorted()はデフォルトだと昇順ソートなので、sorted(by: >)で降順ソートします。配列の先頭の方が大きくなるように...という意味で>を引数に指定します
for文を使ってもよかったのですが、sorted()の勢いで高階関数を使って書いてしまいましょう。
インデックスを使いたいのでenumrated()をしてからforEach()します。

ここのif文とか良いですね。
*if index is multiple of 2 ... else ...*と、自然に読めてしまいます。
今考えると、Swiftのif, whileなどの条件に()が必要ないのは、「if文自体をより自然な英文のように読みやすくするため」という意味もあるんじゃないかなと思いました。

第7問: ABC085B - Kagami Mochi

問題文
$X$ 段重ねの鏡餅 $(X ≥ 1)$ とは、$X$ 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 $10$、$8$、$6$センチメートルの餅をこの順に下から積み重ねると $3$ 段重ねの鏡餅になり、餅を一枚だけ置くと $1$ 段重ねの鏡餅になります。

ダックスフンドのルンルンは $N$ 枚の円形の餅を持っていて、そのうち $i$ 枚目の餅の直径は $d_i$ センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約
$1 ≤ N ≤ 100$
$1 ≤ d_i ≤ 100$
入力値は全て整数である。

入力
$N$
$d_1$
$.$
$.$
$d_N$

出力
作ることのできる鏡餅の最大の段数を出力せよ。

AtCoderWebサイトより引用

解答

一見難しそうだったのですが...サンプル入力&出力を見ていると
「あれ？これって結局はダブっていない要素の数を数え上げるだけかな...？」
と思いつき、やって見たら正解でした。

func main7() {
    let N = readInt()
    let numbers = (0..<N).map { _ in readInt() }

    print(Set(numbers).count)
}
main7()

今までと違う点で言えば一行に1文字づつ入力されてくる点でしょうか。
こう言う場合、個人的には(0..<N).map { _ in readInt() }という書き方が簡潔かつ入力配列をletにできるので気に入って使っています。

ダブっていない(=ユニークな)要素を数える方法は、愚直に「記録用の配列を作って新しい要素が来たら追加」という方法でもよかったのですが
ちょうどユニークな要素だけを保持するSetがあるのでこれを使いましょう。
Setを入力のnumbers配列で初期化し、countで要素数を数えるだけでOKです。

Dictionaryでも実装できます。「ユニークな要素」と聞いた時に、Setより先にDictionaryが思い浮かんだ方も多いんじゃないでしょうか。(私はそうでした)

func main7() {
    let N = readInt()

    var dictionary: [Int: String] = [:]
    (0..<N).forEach { _ in
        let number = readInt()
        dictionary[number] = "found!"
    }
    print(dictionary.count)
}
main7()

第8問: ABC085C - Otoshidama

問題文
日本でよく使われる紙幣は、$10000$ 円札、$5000$ 円札、$1000$ 円札です。以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が $N$ 枚入っていて、合計で $Y$ 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約
$1 ≤ N ≤ 2000$
$1000 ≤ Y ≤ 2×10^7$
$N$は整数である。
$Y$は$1000$の倍数である。

入力
$N$ $Y$

出力
$N$ 枚のお札の合計金額が $Y$ 円となることがありえない場合は、'-1 -1 -1' と出力せよ。

$N$ 枚のお札の合計金額が $Y$ 円となることがありうる場合は、そのような $N$ 枚のお札の組み合わせの一例を「$10000$ 円札 $x$ 枚、$5000$ 円札 $y$ 枚、$1000$ 円札 $z$ 枚」として、$x$、$y$、$z$ を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

AtCoderWebサイトより引用

解答

C問題です。C問題は 愚直には解けず、問題の読み替えや少しの慣れとテクニックが必要なレベル だと感じています。
C問題からは愚直に解くと計算時間やメモリの使用量を制限を超過し、不正解となる可能性が出てくるので、プログラムのアルゴリズムを工夫する必要が出てきます。

今回の問題を愚直に解こうとすると、第4問のように全探索で 「$i + j + k = N$となる全ての$i$, $j$, $k$の組み合わせを試し、合計金額がY円となる組み合わせを見つける」 となりますが、
実はこれではTLE(実行時間制限超過)で不正解になってしまいます。

3重ループを行おうとすると以下のような記述になり、制約を見ると$1 ≤ N ≤ 2000$とあることから、全ての組み合わせの判定を行うためには

$2,001$通り $×$ $2,001$通り $×$ $2,001$通り = $8,012,006,001$通り $≒$ $8 × 10^9$通り

の判定が必要となります。
一般的な計算機が1秒間に実行できる計算量は大体$10^8$程度であり、$8 × 10^9$通りの判定は桁が一つ大きいので間に合いません。

for i in 0...N {
    for j in 0...N {
        for k in 0...N {
            // 判定処理
        }
    }
}

補足:
計算量を考える場合に用いられるオーダー($O$)という物があります。
「この処理の計算量は$O(n)$」のような形で用いられ、**「nに比例する時間以内で終了する計算量」という意味です。
今回の例で言えば、愚直に解くと3重ループとなるので、$O(n^3)$となり、$n=2000$となります。
$n^3$ > $10^8$ であることがわかるので、「$O(n^3)$=(nについての3重ループ)ではこの問題は解けない、$O(n^2)$=(nについての2重ループ)で解かなくては...」**と考えるわけです。

が...計算量の概念はとても重要だとは思いますが、少し慣れるのに時間がかかる(と思うので)、個人的には最初は「3重ループで解けそう！あ...実行時間制限超過が出た...2重ループに修正しよう！」とトライ&エラーをしていくうちに計算量のことも考えられるようになればいいのではないか、と思っています
...という自分の勉強方針でした(まる

長々とお話をしてしまいましたが、解答はこんな感じです。

func main8() {
    let (N, Y) = readTwoInts()

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

    print(-1, -1, -1)
}
main8()

$i + j + k = N$から、$i$, $j$を決めた時点で$k$の値は$k = N - i - j$と一意に決まるので、kについてループする必要はありません。これで計算量を$O(n^2)$に減らすことができました。
後は$i$, $j$, $k$を用いて判定を行えば良いのですが、kが負になる場合を弾くのと、答えが1つ見つかったらプログラムを終了させるのだけ忘れないようにします。

また、func main8()とメソッド化しているおかげで多重ループからの離脱もreturnで楽にできるようになっています。

[追記] @Miya49_p0 さんよりコメントで補足をいただきました。
jのループにおいて、$k = N - i - j$ が最初に負になった後、jは増え続けるので、残りの$j$のループを回しても$k$はずっと負です。つまり、毎回if k >= 0の処理で弾かれ、無駄なループとなります。このことを考え、元々kが負にならない様にループを組めば無駄の無いアルゴリズムになるようです。
確かにそうですね...。
$k = N - i - j ≥ 0$より、$N - i ≥ j$つまり、$j$は$N - 1$ までのループさせれば良いっぽいです。

@Miya49_p0 さんより提供

func main8() {
    let (N, Y) = readTwoInts()

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

    print(-1, -1, -1)
}
main8()

第9問: ABC049C - 白昼夢

問題文
英小文字からなる文字列 $S$ が与えられます。 $T$ が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで $S = T$ とすることができるか判定してください。

• $T$ の末尾に 'dream' 'dreamer' 'erase' 'eraser' のいずれかを追加する。

制約
$1 ≤ |S| ≤ 10^5$
Sは英小文字からなる。

入力
$S$

出力
$S = T$ とすることができる場合 'YES' を、そうでない場合 'NO' を出力せよ。

AtCoderWebサイトより引用

解答

うーん...悩みましたが初見では解けませんでした。
**「文字列Sは先頭から読むと一意に定まらないが、後ろから読むと一意に定まる」**というヒントを聞いてやっと解くことができました。

C問題以上では発想力も求められそうですね...
まあでも、こういう手法をテクニックとして消化し、引き出しを増やしていけば簡単に気付けるようになるのかもしれません。

func main9() {
    let words = ["dream", "dreamer", "erase", "eraser"]
    var S = readLine()!

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

    print(S.isEmpty ? "YES" : "NO")
}
main9()

while-let, first(), hasSuffix()を用いて
「『wordsのどれかに後方一致したら一致した部分を削除する』という操作を可能な限り繰り返し、繰り返しが終わった時点で全ての文字列が削除できていたらYES」
というアプローチです。

補足:
本当はもう少し長いコードだったのですが、綺麗な解答をQiitaの記事で見つけたので参考にさせていただきました。

先人様:
https://qiita.com/conf8o/items/8f2130510a9deaffa312#abc049c---%E7%99%BD%E6%98%BC%E5%A4%A2

今回は計算量は大丈夫でしたが、一点今後注意すべき点があります。
それは、SwiftにおけるStringの扱いです。

SwiftのCollectionにはcountというコレクションの長さを取得する変数があります。
そこで問題なのが、Stringのcountは $O(1)$ではなく$O(n)$の計算量がかかります
k番目の文字の取得にもO(k)の計算量がかかります

ドキュメントには以下のような記述があります。

O(1) if the collection conforms to RandomAccessCollection; otherwise, O(n), where n is the length of the collection.

Collection count公式ドキュメント:
https://developer.apple.com/documentation/swift/collection/3017670-count

コレクションがRandomAccessCollectionに準拠している場合は$O(1)$, そうでない場合は$O(n)$となるようです。
次に、RandomAccessCollectionのドキュメントを見てみると...

• RandomAccessCollection 公式ドキュメント:　https://developer.apple.com/documentation/swift/randomaccesscollection

な、なんとConforming TypesにStringが無いではありませんか...！！
つまり、Stringのcount()は$O(n)$かかるということを意味します。

C言語, C++, Java, Pythonなどを触ってきた自分は「String=Charの配列」であることが当たり前かのように考えていたのですが、Swiftではそうでは無いようです...。⁴

例えば、for文ループの中でcountや特定の文字取得をしなければいけなく
for文 * count = $O(n^2)$ * $O(n)$ = $O(n^3)$になってしまう...
なんて場合の解決策としては、 NSStringを使うもしくは、[Character]にキャストして扱う ことです。
(ただし、NSString, [Character]の変換にコピーが走るので$O(n)$かかります。)
ループの外でNSStringもしくは[Character]へ変換をしておくことで、
変換 + for文 * count = $O(n)$ + $O(n^2)$ * $O(1)$ = $O(n^2)$ とすることができます。
実際にそんなストライクな問題が出題されるかは謎ではありますが...

let string = "0123456789"

string.count // O(n)

let nsString = NSString(string) // キャストでO(n)
nsString.length // O(1)

let arrayOfChar: [Character] = Array(string) // キャストでO(n)
arrayOfChar.count // O(1)

また、Stringのk番目の文字を取得する際もstring[k]とはできず、String.Indexを用いてstring[string.index(string.startIndex, offsetBy: k)]と書かなくてはいけません。
競技プログラミングでこれをするのはちょっと面倒な気はしますね...

補足:
subscript(string[k]とかの指定方法)でIntを使って簡単にできないようにしているのは、
あえて複雑な処理にしておくことで高コストな処理であることを意識してもらうため ⁵ だそうです。
確かにそう言われると、string.index(string.startIndex, offsetBy: k)という表現から
インデックスの先頭(string.startIndex)からk番ずらした(offsetBy)インデックスを取得して...と、「$O(k)$かかってる感」が出てる気がします(???)

これだけ書いておいてなんですが、今回の例のようにhasSuffix()やremoveLast()などのメソッドで事足りる場合も多いと思うので、[Character]への変換などは本当に迫られた時だけにしようと思いました。
「Stringの扱いには少し注意が必要」と言う程度に覚えておくことにします。

本題からかなりそれてしまいましたが...
おかげでSwiftのStringの仕様を少しだけ理解できたような気がします！
計算量について知れたのはとても良かったです。

第10問: ABC086C - Traveling

問題文
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 $0$ に 点 $(0, 0)$ を出発し、 $1$ 以上 $N$ 以下の各 $i$ に対し、時刻 $t_i$ に 点 $(x_i, y_i)$ を訪れる予定です。

AtCoDeerくんが時刻 $t$ に 点 $(x, y)$ にいる時、 時刻 $t + 1$ には 点 $(x + 1, y), (x − 1, y), (x, y + 1), (x, y − 1)$ のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約
$1 ≤ N ≤ 10^5$
$0 ≤ x_i ≤ 10^5$
$0 ≤ y_i ≤ 10^5$
$1 ≤ t_i ≤ 10^5$
$t_i ≤ t_{i+1}(1≤i≤N - 1)$
入力は全て整数

入力
$N$
$t_1$ $x_1$ $y_1$
$t_2$ $x_2$ $y_2$
$.$
$.$
$t_N$ $x_N$ $y_N$

出力
旅行プランが実行可能ならYesを、不可能ならNoを出力してください。

AtCoderWebサイトより引用

解答

最後の問題です。
まず、問題を小さく分割します。

**「プランの時刻$t_i$から時刻$t_{i+1}$までについて可能かどうかを判別する」**を最初から最後まで計N-1回行えば良いとわかるので、時刻$t_i$から時刻$t_{i+1}$までのことのみを考え、あとはループさせれば良いことがわかります。

次に、分割した問題について考えます。
プランの時刻$t_i$から時刻$t_{i+1}$までについて

• 距離が時間より大きい場合はたどり着けない: $|x_i - x_{i+1}| + |y_i - y_{i+1}|$ $>$ $t_{i+1} - t_i$
• 偶数時間は「どこか隣の位置に移動し、戻ってくる」という移動を繰り返すことで消費することができる(偶数時間は結果的に位置を変えずに潰すことができる)
• 目標の点までの移動の仕方で残り時間の偶奇が変わることはない(なんとなく直感的にわかるとは思います)

という点から、**「時間以内に(最短距離で)たどり着くことができ、また辿り着いた後、残り時間が偶数時間であれば良い」**ということがわかります。

計算量についても、プランの時刻$t_i$から時刻$t_{i+1}$までの判定については$O(1)$で解けるので、それをループした$O(N)$で済みそうです。$N≤10^5$なので計算時間は余裕ですね。

よって以下のように実装できます。

typealias Plan = (t: Int, x: Int, y: Int)
func main10() {
    let N = readInt()
    let plans: [Plan] = (0..<N).map { _ in readThreeInts() }

    var previous = Plan(t: 0, x: 0, y: 0)

    for plan in plans {
        let time = plan.t - previous.t
        let distance = abs(previous.x - plan.x) + abs(previous.y - plan.y)

        // 最短距離で目標地点まで移動した場合の残り時間=時間-距離
        let remain = time - distance

        // 残り時間が負 かつ 偶数 だったらOK
        if remain < 0 || !remain.isMultiple(of: 2) {
            print("No")
            return
        }

        previous = plan
    }

    print("Yes")
}
main10()

$(t, x. y)$のペアの保持はタプルを使い、可読性向上のためtypealiasを使ってPlanとして定義しています。
プランはPlan型配列として受け取り、その配列の$i$番目と$i+1$番目について判定を行います。

プログラム的にはそこまで難しくないと思います。
競技プログラミングは(発想力と)アルゴリズム力を競う物らしいので、問題が難しくなってもプログラム自体はそこまで難しくならない、と言った感じなのでしょうか...。

あと、問9, 10をみてわかるかと思いますが、YES/NO問題は問題によって'Yes'だったり'YES'だったりします...。問題文を良く読まないと変なところではまる場合があるので注意しましょう(経験談)(戒め)

最初、タプルではなくstructを用いて実装を行っていました。
競技プログラミングにおいてstruct(やクラスなど)は問題を解く上で一般的に使われているのでしょうか...?
「Swiftで可読性の低いプログラムを書きたくない」と言う気持ちがあるので、構造化できる物があったら構造化したくなってしまいます...

struct Plan {
    let time: Int
    let x: Int
    let y: Int

    func diff(to plan: Plan) -> (time: Int, distance: Int) {
        return (plan.time - time, abs(x - plan.x) + abs(y - plan.y))
    }
}

func main() {
    let N = readInt()

    let plans = (0..<N).map { _ -> Plan in
        let tuple = readThreeInts()
        return Plan(time: tuple.a, x: tuple.b, y: tuple.c)
    }

    var previous = Plan(time: 0, x: 0, y: 0)

    for plan in plans {
        let diff = previous.diff(to: plan)

        let remain = diff.time - diff.distance
        if remain < 0 || !remain.isMultiple(of: 2) {
            print("No")
            return
        }

        previous = plan
    }
    print("Yes")
}

これで10問解けました！
問題から題意を読み解く点, 解法が閃いたときの嬉しさなど、数学に似ている気がしますね...。
後半はもっぱらキーボードではなくiPadのメモ帳と向き合いながら考えていたので、プログラミングと言うより数学をしている感覚でした。

これまでの解答をまとめたサンプルコード: https://github.com/kntkymt/AtCoderBeginnersSelection_Swift

コンテストに参加する

よし！！初心者向け問題集も解いた！！さぁコンテストだ！！
以下のページから開催予定のコンテストを確認してみましょう！

• AtCoderホーム: https://atcoder.jp/home

基本的にまずは初心者向けのコンテストである ABC(AtCoder Begginer Contest) に参加すれば良いと思います。
ABCは土または日の21時ごろから始まる場合が多く、また、開催周期は不定期のようです。

こちらも下の記事が詳しいと思います。

• AtCoder コンテストについての tips: https://qiita.com/drken/items/8a6f139158cde8a61dce

過去問を解く

コンテストがあった場合もなかった場合も、空いた時間は過去問を解くと良いと思います！
私は下の AtCoderProblems と言う過去問へのリンクが乗っているサイトを利用しています。

• AtCoderProblems: https://kenkoooo.com/atcoder/#/table/

「過去のC問題を一通り解いてみる」みたいな使い方ができたり、
レーティングに沿って問題の難易度が色分けされているので、「今自分がどの程度の難易度(レーティング)の問題まで解けるのが」などが分かったりして便利です。

まとめ・感想

今回、AtCoderをSwiftで初めてみた体験記と、Swiftを使っている方々が競技プログラミングを始めやすいように解説を兼ねて記事を書きました。
いかがだったでしょうか？Swiftや競技プログラミングに興味を持っていただけたでしょうか？

普段メインでは扱わないアルゴリズムを、普段使っているSwiftで書くことによって**余分な記述が少なく、可読性が高くて描きやすいSwiftの良さを再確認できたと同時に、今まで見えていなかったSwiftの世界が見えた気がします。**また、新しく得た知見は普段Swiftをアプリケーション開発で書く場合にも十分に役に立つと思うのでとても得をした気分です。
せっかく始めたので、これからも地道に競技プログラミングを続けていこうと思っています。

本当は、もう少し競技プログラミング・AtCoderについて学んでから記事を書こうと思っていたのですが、Swiftで競技プログラミングをやる仲間を増やしたい&早い方がいいだろう、と言うのと初心者なりに得た情報をアウトプットすることで勉強になると思ったので書くことにしました。
しかし、「でもやっぱり私も1ヶ月前くらいに競技プログラミングを始めたばかりで人に解説できるほど競技プログラミングを知らないからな...」と言う気持ちと「Swiftを使っている方々で競技プログラミングに興味のある方の参考になる記事を書きたいな」と言う気持ちが鬩ぎ合って, 結果説明口調になったり感想になったりと、解説なのか体験記なのか良くわからないどっちつかずの記事になってしまいました...

もしここまで読んでくださった方がいらっしゃったら、本当にありがとうございます。
だいぶ長い記事になってしまったので、ここら辺で終わりにしたいと思います。

それでは、良き競技プログラミング, Swiftライフを。
次はコンテストでお会いしましょう！

1. 【ニュースリリース】日本最大のプログラミングコンテストサイトAtCoder登録者数が20万人を突破！ https://twitter.com/atcoder/status/1269882731313258496?s=20 ↩

2. XcodeとSwiftのバージョン対応表: https://qiita.com/uhooi/items/b16c0959aa6e3caf5426 ↩

3. Swiftのエラー4分類が素晴らしすぎるのでみんなに知ってほしい
   https://qiita.com/koher/items/a7a12e7e18d2bb7d8c77#logic-failure ↩

4. なぜSwiftの文字列APIは難しいのか https://postd.cc/why-is-swifts-string-api-so-hard/ ↩

5. Swift 3のStringのViewに対して、Intでsubscript出来ない理由 https://medium.com/swift-column/swift-string-7147f3f496b1 ↩