多重ループ

読了目安 約3分

2 重ループで全ペアを列挙する。break が効く範囲とラベル付き break。

ループの中にもう 1 つループを入れた形を、2 重ループと呼びます。 考えられる候補をすべて調べる解き方を全探索と呼び、2 重ループは「すべての組み合わせ」の全探索に使う基本の道具です。

2 重ループの動き

外側が 1 回進むごとに、内側のループが最初から最後まで回ります。

for i in 0..<3 {
    for j in 0..<3 {
        print("i = \(i), j = \(j)")
    }
}

全部で 3 × 3 = 9 行が出力されます。

試してみよう: 内側を 0..<5 に変えて、出力が 15 行になることを確かめてください。

全ペアの列挙

配列から 2 つ選ぶ組み合わせは、内側の j を i + 1 から始めると重複なく列挙できます。

let a = [2, 5, 4, 3]
for i in 0..<a.count {
    for j in i + 1..<a.count {
        print("\(a[i]) と \(a[j])")
    }
}

内側も 0..<a.count にすると、自分自身とのペアや順番違いの重複が混ざります。 i + 1 始まりが「2 つ選ぶ」の定石です。

break と continue は内側だけに効く

break と continue が効くのは、それを囲む一番内側のループだけです。

for i in 0..<3 {
    for j in 0..<3 {
        if j == 1 {
            break  // 内側の for だけを抜ける
        }
        print("i = \(i), j = \(j)")
    }
}

内側で break しても、外側の i のループは続いています。

ラベル付き break

外側のループごと抜けたいときは、ループに名前を付けて break 名前 と書きます。 この名前をラベルと呼びます。

outer: for i in 0..<3 {
    for j in 0..<3 {
        if i + j == 3 {
            break outer  // 外側の for ごと抜ける
        }
        print("i = \(i), j = \(j)")
    }
}

計算回数を意識する

2 重ループの実行回数はおよそ N × N 回です。 N = 1,000 なら 100 万回ですが、N = 100,000 なら 100 億回になり、現実的な時間で終わりません。 この見積もり方は 計算量 で扱います。

学びどころ

演習

果物屋さんに N 個の果物が並んでいて、それぞれに値段が付いています。 ちょうど 2 個買って、合計をぴったり S 円にします。 買い方が何通りあるかを出力してください。

同じ値段でも、別の果物なら別の買い方として数えます。 1 行目に N と S、2 行目に N 個の値段が空白区切りで入力されます。 入力例では 2 円と 5 円の組だけが 7 円になるので、答えは 1 です。

制約: 2 ≤ N ≤ 50、値段は 1 以上 1000 以下、1 ≤ S ≤ 2000

入力例:
3 7
2 5 4

出力例:
1

let firstLine = readLine()!.split(separator: " ").map { Int($0)! }
let n = firstLine[0]
let s = 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] == s {
            count += 1
        }
    }
}
print(count)