競プロで使えるアルゴリズム関数一覧(Swift)

私はSwiftにおける競プロの記事をいくつか投稿しています。

• 競プロで使える標準入力の便利メソッド一覧
• 競プロで使える標準エラーの出力方法
• 競プロで使える便利なエクステンション一覧
• 競プロで使えるアルゴリズム関数一覧 ←イマココ

自分で武器を増やしていくのが競プロの面白さのひとつだと思っているので、まずは自分で考えるのがオススメです。
どうしてもわからないときに、私の記事が参考になると嬉しいです

はじめに

本記事は Swift/Kotlin愛好会 Advent Calendar 2020 の6日目の記事です。
競プロで使えるアルゴリズムの関数を紹介します。

注意

• 本記事で紹介している関数および計算量が正しいかは保証できていません。
• さらに計算量が小さいプログラムが存在する可能性があります。
• 本記事は随時更新予定です。

環境

• OS：macOS Big Sur 11.0.1
• Xcode：12.2 (12B45b)
• Swift：5.3.1
  5.2.1（2020/12/06現在のAtCoder）でも動作する

競プロで使えるアルゴリズム関数一覧

順列全探索

説明

TBD

ソースコード

private func permutations<T>(of values: [T]) -> [[T]] {
    if values.count <= 1 {
        return [values]
    }
    var results: [[T]] = []
    for i in values.indices {
        let baseValue = values[i]
        var excludingBaseValue = values
        excludingBaseValue.remove(at: i)
        results += permutations(of: excludingBaseValue).map { [baseValue] + $0 }
    }
    return results
}

出力例

[1, 3] -> [[1, 3], [3, 1]]
[1, 2, 4] -> [[1, 2, 4], [1, 4, 2], [2, 1, 4], [2, 4, 1], [4, 1, 2], [4, 2, 1]]
[1, 2, 3, 5] -> [[1, 2, 3, 5], [1, 2, 5, 3], [1, 3, 2, 5], [1, 3, 5, 2], [1, 5, 2, 3], [1, 5, 3, 2], [2, 1, 3, 5], [2, 1, 5, 3], [2, 3, 1, 5], [2, 3, 5, 1], [2, 5, 1, 3], [2, 5, 3, 1], [3, 1, 2, 5], [3, 1, 5, 2], [3, 2, 1, 5], [3, 2, 5, 1], [3, 5, 1, 2], [3, 5, 2, 1], [5, 1, 2, 3], [5, 1, 3, 2], [5, 2, 1, 3], [5, 2, 3, 1], [5, 3, 1, 2], [5, 3, 2, 1]]

計算量

TBD

参考リンク

TBD

階乗

説明

$n!$ を返します。

まだAtCoderでは使ったことがありません。

ソースコード

private func factorial(of value: Int) -> Int {
    precondition(value >= 0)
    if value == 0 {
        return 1
    }
    return (1...value).reduce(1, *)
}

出力例

0 -> 1
1 -> 1
2 -> 2
3 -> 6
9 -> 362880

計算量

$O(N)$

参考リンク

• 階乗 - Wikipedia

組み合わせ

説明

$_nC_r$ を返します。

ソースコード

private func combination(n: Int, r: Int) -> Int {
    precondition(n > 0 && r >= 0)
    if r == 0 {
        return 1
    }
    if r > n {
        return 0
    }
    var result = 1
    for i in 1...r {
        result *= n - (i - 1)
        result /= i
    }
    return result
}

$\frac{_nP_r}{r!}$ の分子から計算すると（ $n$ や $r$ の大きさによっては）64 bit 整数型ではオーバーフローするため、掛けて割ってを繰り返しています。
割る数値を $1, 2, \ldots, r$ と1から昇順に増やすことで、 result は常に整数となります。

出力例

(n: 1, r: 0) -> 1
(n: 1, r: 1) -> 1
(n: 1, r: 2) -> 0
(n: 2, r: 1) -> 2
(n: 11, r: 11) -> 1
(n: 12, r: 11) -> 12
(n: 13, r: 11) -> 78
(n: 16, r: 11) -> 4368
(n: 199, r: 11) -> 366461620334848584

計算量

$O(r)$

参考リンク

• 組合せ (数学) - Wikipedia
• 解説 - AtCoder Beginner Contest 185
• 提出 #18756467 - AtCoder Beginner Contest 185
• 提出 #18768157 - AtCoder Beginner Contest 185

約数列挙

説明

与えられた数値の約数をすべて求め、昇順に整列した配列で返します。
整列する必要がない場合、返却時の sorted() を外してください。

ソースコード

import Foundation

private func divisors(of value: Int) -> [Int] {
    precondition(value > 0)
    var divisors: Set<Int> = []
    for i in 1...(Int(floor(sqrt(Double(value))))) where value % i == 0 {
        divisors.insert(i)
        divisors.insert(value / i)
    }
    return divisors.sorted()
}

divisors 変数を通常の配列でなく Set<Int> 型で定義している理由は、数値が平方数（例: 25）の場合に約数が重複するのを防ぐためです。
通常の配列は重複を許すため 25 -> [1, 5, 5, 25] となりますが、 Set<Int> は重複を許さないので 25 -> [1, 5, 25] となります。

出力例

1 -> [1]
2 -> [1, 2]
3 -> [1, 3]
4 -> [1, 2, 4]
5 -> [1, 5]
6 -> [1, 2, 3, 6]
7 -> [1, 7]
8 -> [1, 2, 4, 8]
9 -> [1, 3, 9]
10 -> [1, 2, 5, 10]
11 -> [1, 11]
12 -> [1, 2, 3, 4, 6, 12]
13 -> [1, 13]
14 -> [1, 2, 7, 14]
15 -> [1, 3, 5, 15]
16 -> [1, 2, 4, 8, 16]
17 -> [1, 17]
18 -> [1, 2, 3, 6, 9, 18]
19 -> [1, 19]
20 -> [1, 2, 4, 5, 10, 20]
21 -> [1, 3, 7, 21]
22 -> [1, 2, 11, 22]
23 -> [1, 23]
24 -> [1, 2, 3, 4, 6, 8, 12, 24]
25 -> [1, 5, 25]
26 -> [1, 2, 13, 26]
27 -> [1, 3, 9, 27]
28 -> [1, 2, 4, 7, 14, 28]
29 -> [1, 29]
30 -> [1, 2, 3, 5, 6, 10, 15, 30]

計算量

$O(\sqrt{N})$

参考リンク

• 提出 #173650 | アルゴ式

素因数分解

説明

与えられた数値を素因数分解し、昇順に整列した配列で返します。

ソースコード

import Foundation

private func primeFactorizations(of value: Int) -> [Int] {
    precondition(value > 0)
    if (1...3).contains(value) {
        return [value]
    }

    var copiedValue = value
    var primeFactorizations: [Int] = []
    for i in 2...Int(floor(Double(n) / 2)) {
        while copiedValue % i == 0 {
            copiedValue /= i
            primeFactorizations.append(i)
        }
        if primeFactorizations.reduce(1, *) == value {
            break
        }
    }
    if primeFactorizations.isEmpty {
        primeFactorizations.append(value)
    }
    return primeFactorizations
}

出力例

1 -> [1]
2 -> [2]
3 -> [3]
4 -> [2, 2]
5 -> [5]
6 -> [2, 3]
7 -> [7]
8 -> [2, 2, 2]
9 -> [3, 3]
10 -> [2, 5]
11 -> [11]
12 -> [2, 2, 3]
13 -> [13]
14 -> [2, 7]
15 -> [3, 5]
16 -> [2, 2, 2, 2]
17 -> [17]
18 -> [2, 3, 3]
19 -> [19]
20 -> [2, 2, 5]
21 -> [3, 7]
22 -> [2, 11]
23 -> [23]
24 -> [2, 2, 2, 3]
25 -> [5, 5]
26 -> [2, 13]
27 -> [3, 3, 3]
28 -> [2, 2, 7]
29 -> [29]
30 -> [2, 3, 5]

計算量

TBD

参考リンク

TBD

最大公約数

説明

$1$ 以上の整数 $a$ と $b$ の最大公約数を返します。

ソースコード

private func gcd(_ a: Int, _ b: Int) -> Int {
    precondition(a > 0 && b >= 0)
    return b == 0 ? a : gcd(b, a % b)
}

出力例

gcd(2, 3) -> 1
gcd(6, 3) -> 3
gcd(24, 36) -> 12

計算量

$O(\log{N})$

$N$ は $a$ と $b$ のうち小さいほうの数値

参考リンク

• ユークリッドの互除法 - Wikipedia
• 提出 #162252 | アルゴ式

最小公倍数

TBD

おわりに

以上、 Swift/Kotlin愛好会 Advent Calendar 2020 の6日目の記事でした。
明日も @uhooi の記事です。

参考リンク

• uhooi/Programming-Swift-Solving: Solve competition programming using Swift.
• Swift版 競プロ用チートシート(初心者向け) - Qiita
  まずは自力で解きたいため、こちらの記事はまだほとんど参考にしていない