Swift で AtCoder に取り組むためのサポートライブラリです。標準ライブラリや Foundation に不足しているアルゴリズムやデータ構造等が実装されています。
Swift Package 形式になっていますが、 AtCoder で利用する際には必要なものをコピペして利用して下さい。 Swift Package を採用しているのはテストの実行が容易なためです。
コピペを前提としているため、すべての API は public でなく無印の internal として実装されています。また、本パッケージ内も含めて極力他の API に依存なく、関数や extension 単体でコピペできるようにしています。
| アルゴリズム・データ構造 | API | 利用例 |
|---|---|---|
| 二次元配列 | Array2D |
ABC 182 E - Akari |
| 三次元配列 | Array3D |
ABC 184 D - increment of coins |
| N次元配列 | ArrayND |
ABC 184 D - increment of coins |
| 順列 | permutations() |
ABC 145 C - Average Length |
| nCr | NCR |
ABC 151 E - Max-Min Sums |
| 二分探索 | values(_:_:) |
ABC 077 C - Snuke Festival |
| 深さ優先探索 | dfs(edges:startedAt:_:) |
ABC 138 D - Ki |
| 幅優先探索 | bfs(edges:startedAt:,_:) |
ABC 190 E - Magical Ornament |
| 素数判定 | isPrime |
ABC 149 C - Next Prime |
| ベルマン–フォード法 | bellmanFord(graph:startedAt) |
ABC 061 D - Score Attack |
| ダイクストラ法 | dijkstra(graph:startedAt:) |
ABC 035 D - トレジャーハント |
| ワーシャル–フロイド法 | warshallFloyd(graph:) |
ABC 143 E - Travel by Car |
| 巡回セールスマン問題 | tsp(distances:startedAt:) |
ABC 180 E - Traveling Salesman among Aerial Cities |
| Union-Find | UnionFind |
ARC 032 B - 道路工事 |
| mod | ModInt |
ARC 107 A - Simple Math |
| mod | %+, %*, %+= 等 |
ABC 151 E - Max-Min Sums |
| 範囲の和 | ClosedRange.sum(modulus:) |
ARC 107 A - Simple Math |
| 安全な範囲演算子 | ..<?, ...? |
ABC 192 D - Base n |
| オーバーフロー安全な算術演算子 | +?, -?, *? |
ABC 192 D - Base n |
通常の Swift Package 同様 swift test でテストを実行できますが、パフォーマンステストなど最適化を必要とする場合は次のようなオプションが必要になります。これは、 internal な API をテストするために @testable import を利用しているため、通常の swift test -c release ではテストを実行できないからです。
swift test -c release -Xswiftc -enable-testing
-Ounchecked で実行するには次のようにします。
swift test -c release -Xswiftc -enable-testing -Xswiftc -Ounchecked
コード中に precondition が含まる場合がありますが、 AtCoder では -Ounchecked でコンパイルされるため実行時にはすべて取り除かれます。そのため、 precondition のオーバーヘッドを気にする必要はありません。
ローカル環境で実行する際には、最適化オプションなしで実行することでコードの事前条件違反を素早く検出することができます。
// main.swift
func dfs(edges: [[Int]], startedAt start: Int, _ body: (Int) -> Void) {
precondition(edges.indices.contains(start), "`start` index is out of bounds: \(start)")
// 省略
}
dfs(edges: [[1, 2], [], []], startedAt: -1) { _ in }$ swift main.swift
Precondition failed: `start` index is out of bounds: -1
CC0