全探索

読了目安 約3分

候補を漏れなく調べる線形探索と 2 重ループの全列挙。競プロの第一歩。

問題を前にしたら、まず「候補を全部調べたら間に合うか」を考えます。 候補を漏れなく調べて答えを見つける方法を全探索と呼びます。 単純ですが、競プロの解法はここから出発します。

線形探索

配列の端から順に 1 つずつ調べる全探索を線形探索と呼びます。 まずは「目当ての値があるか」を調べてみます。

let a = [31, 41, 59, 26, 53]
let target = 26

var found = false
for x in a {
    if x == target {
        found = true
    }
}
print(found ? "ある" : "ない")

試してみよう: target を 99 に変えて、「ない」と出力されることを確かめてください。

個数と最大値

同じ形のループで、「条件を満たす個数」と「最大値」も求められます。 ループの外に結果を入れる変数を用意し、1 周ごとに更新するのが型です。

let scores = [62, 85, 47, 90, 73]

var count = 0
var best = scores[0]
for s in scores {
    if s >= 60 {
        count += 1
    }
    if s > best {
        best = s
    }
}
print("60 点以上は \(count) 人")
print("最高点は \(best) 点")

2 重ループで全列挙

「2 つ選ぶ」候補は、ループを重ねるとすべて列挙できます。 内側のループを i + 1 から始めると、同じ組を 2 回数えません。

let a = [2, 5, 4, 9, 3]

var pairCount = 0
for i in 0..<a.count {
    for j in (i + 1)..<a.count {
        if a[i] + a[j] == 7 {
            print("a[\(i)] + a[\(j)] = 7")
            pairCount += 1
        }
    }
}
print("全部で \(pairCount) 組")

計算量

要素数を N とすると、線形探索は最大 N 回の比較で終わるので O(N) です。 2 重ループは調べる組がおよそ N² / 2 個なので O(N²) です。

コンピュータが 1 秒間に実行できる単純な計算は、およそ 1 億回です。 O(N) なら N が 1 億、O(N²) なら N が 1 万くらいまでが目安です。

まず全探索が間に合うか見積もり、間に合うならそのまま書きます。 間に合わないときに初めて、次章からの工夫を持ち出します。

学びどころ

演習

1 行目に整数 N と K、2 行目に N 個の整数 A_1 … A_N が空白区切りで入力されます。 A から 2 つを選んで、和がちょうど K になる選び方が何組あるか出力してください。 同じ値でも、位置が違えば別の選び方と数えます。

制約: 2 ≤ N ≤ 100、整数はすべて 1 ≤ 値 ≤ 1000000000。

入力例:
4 5
1 2 3 4

出力例:
2

1 + 4 と 2 + 3 の 2 組です。

let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let n = firstLine[0]
let k = firstLine[1]
let a = readLine()!.split(separator: " ").map { Int($0)! }

var count = 0
for i in 0..<n {
    for j in (i + 1)..<n {
        if a[i] + a[j] == k {
            count += 1
        }
    }
}
print(count)