「競プロでのSwift Algorithms系、正直どうなん？」
この記事は Swift Advent Calendar 2023 の 20日目の記事です。
概略
まだまだ出番は少ないものの、Swift Algorithms と Collection のおかげでコード量が減った場面は確かにあり、今後の活躍が期待されます。
背景
Swiftでも競技プログラミングコンテストに参加できるというのは、すでに多くの方が知るところになっているかと思います。
実際にSwiftをサポートしているコンテストサイトはまだまだ少ないですが、AtCoderでは以前からSwift言語でコードの提出が可能でした。
ただ問題だった点として、C++やPythonに比べると、外部ライブラリを import 経由で利用できなかったため、都度ライブラリのソースコードまるごとコピー＆ペーストして使う必要があり、ある程度不便を強いられる状況でした。
そんな中、AtCoderにおける2023年度の言語アップデートにおいて、Swift Algorithms および Swift Collections がソースコード中から利用できるようになりました。
本当に便利？
Swift Algorithms も Swift Collections も複雑なアルゴリズムを実装する上で便利なのは確かですが、とはいえそれ自体は特段競技プログラミング向けのライブラリというわけではないため、これらを利用することがどれほどのアドバンテージになるのかという疑問が出るのはもっともです。
そもそも本当に競プロにおいて利点を生み出しているのでしょうか？
実際にこれらのライブラリが使えるようになったのは今年の8月以降のため、そうした疑問を考察するにはまだまだサンプルが不足している状況ですが、概ねどれくらい便利になったかを、少し主観を交えつつではありますが、振り返っていこうと思います。
（ただし、筆者のスキルの都合上D問題以下の問題しか登場しません）
活躍があった例
AdjacentPairs
コレクションの中の、隣接する要素のタプルを次々と返してくれます。
コンテストに参加していると、配列の隣り合う要素を繰り返し利用するケースは意外にも多く遭遇します。
for i in 1..<N {
f(A[i] - A[i - 1])
}
みたいな実装を結構することになるのですが、 AdjacentPairs を使うとこの部分のコストが削減できます。
A問題のような比較的簡単な問題で登場することが多い印象ですが、難しい問題でも階差数列が必要なケースなどでは普通に活躍しそうではありますね。
使用例
Permutations
コレクションの要素、またはそれらの要素のサブセットの順列を計算できます。
おもに全探索が必要となったときよく使われます。
C++では std の下に next_permutation があるので、これが大変便利でした。
これまでのSwift(5.2.1)はそんなものがなかったので泣きながら実装するしかありませんでしたが、もうその必要はありません。
使用例
Product
2つのコレクションの要素に対して全組み合わせを取得してくれます。
これも全探索ではよく登場します。
２重ループ処理を実装したほうがわかり易い場合も多いと思いますが、全探索ではネストが深くなりがちなので[1]、これを使って書き換えることができればある程度コードの見通しが良くなります。
今後の活躍が期待される例
Windows
コレクションから連続する部分列を頭から順番に生成します。
実際に挙動を確認するほうがわかりやすいかもしれません。
for subSeq in Array(1...10).windows(ofCount: 5) {
print(subSeq)
}
[1, 2, 3, 4, 5]
[2, 3, 4, 5, 6]
[3, 4, 5, 6, 7]
[4, 5, 6, 7, 8]
[5, 6, 7, 8, 9]
[6, 7, 8, 9, 10]
このような部分列を得る操作はたまに見かけるので、今後活躍の場面があるかもしれないですね。
SortedSet
Swift の Set は順序が一定ではないため、C++のコードを参考に書くときに std::set をそのまま Set で書き換えてしまって事故るというのは多分誰もが通る道です。
ユニークかつ順序付けられたコレクションを高速に操作できると便利なケースが時々あるので、正式にリリースされれば、そういう問題で活躍しそうです。
（経験上、この３年間のうち、これがないせいでコンテスト中にC++に乗り換えたことが数度あった記憶があるので、多分そのうち活躍します...きっと...。）
その他
Deque
（ごめん、なんかいつも ArraySlice で代用してたけど今度から使います...）
補足事項
ライブラリが利用できるようになった代償として、提出したコードのビルドに1分ほど追加で時間がかかるようになりました。
（画像には10sと出ていますが、実際はその前にかなり待たされます...）
コードをそのまま提出しているなら問題ないですが、ローカルで1回実行してから提出する場合はその延長時間がもれなく降りかかります。
これの何が問題かというと、たとえばA問題を提出するのに少なくとも1分追加でかかるようになるということです。
ABCは時に早解き競争になりがちなので、1分というオーバーヘッドはちょっと看過できないレベルではあります。
一応、キャッシュが効く環境ならコンテスト開始前にビルドを走らせておくと回避はできます。
（結構な頻度で忘れますが...）
今から挑戦する方は記憶に留めておくと良いかと思います。
まとめ
Swiftで競技プログラミングコンテストに参加できるようになったとはいえども、Swiftをサポートしているコンテストサイトは依然少数派です。
アルゴリズム実装の視点で見ても、機動性に関しては依然としてC++やPythonとは大きく水を開けられている状態ですし、競プロ頻出のアルゴリズムを実装するためには別途 swift-atcoder-support のような便利なライブラリが欠かせません。
とはいえ、AtCoder で Swift Algorithms と Swift Collection が使えるようになったのは大きな前進だと思っています。
ある程度見通しの良いコードは書けるようになったのはもちろんですが、やはり外部のライブラリを読み込める道が整備されたのは大きいのではないでしょうか。
Swiftの競技プログラミングにおける可能性が今後も広がりそうで、今から楽しみですね！
宣伝
Swift Developers Japan コミュニティにはAtCoderや競技プログラミングに関するチャンネル(#atcoder)がありますので、よろしければお越しください。
-
一応
for a in A { for b in B { print(a,b)}}のようなまとめた書き方はできますが、linterがもとに戻しちゃうし、あと中括弧がなんかダサいのであんまり書かないですね...C++みたいに省略できないし...。 ↩︎
Discussion