競技プログラミング講習/全探索

概要

今回は、全探索について解説していきます。
ABCにおいて、「可能性のあるものを全て列挙して当てはまる物を調べる」といった問題はよく出題されます。
一見数学的な問題で難しそうに見えて、実は全探索であったということもあります。
コンピュータの計算が早いことを生かして探索していきましょう。

重要語

全探索

ありうるものを全て列挙して判定すること

必要語

今回の必要語はありません。

全探索

競プロにおいて基本である全探索です。ありうるものを全て列挙して判定します。
全探索をするとforやwhileなどがネストしてTLEしやすいため、時間計算量に注意してください。

基本

N個の整数A0, A1, ... An-1と、整数Kが与えられて、Ai×Aj≥Kとなる(i,j)の組の数を出力します。 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] * a[j] >= k) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
ありうるiとjを全て列挙してkより大きいか判定しています。 j = i + 1としていますが、これはi<jとすることで(1,2)と(2,1)といったiとjの重複を避けるためです。 if (i >= j) continue;でも可能です。
また、a[i] * a[j]のオーバーフローに注意してください。
この時間計算量は、二重forの影響でO(N2)です。 そのため、2≤N≤103が限度でしょう。 もし2≤N≤105となっていたらこの解法ではTLEしてしまうため、別の解法を考える必要があります (Aをあらかじめソートしておいてk/a[i]を二分探索(後章)すればO(N log N)で可能です)。

工夫する全探索

「x2+y2=Nとなる非負整数(x,y)の組の数を出力せよ」 という問題で、制約が0≤N≤103であればxとyを0≤x,y≤Nの範囲で二重forを回すO(N2)で解けますが、 制約が0≤N≤105であればO(N2)ではTLEです。
そこでこの問題をよく考えてみると、x,yのどちらかが√Nを上回ったらx2+y2はNを超えます。そのため、0≤x,y≤√Nで十分です。 この時の時間計算量はO(√N2)すなわちO(N)です。 
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int x = 0; x * x <= n; x++) {
        for (int y = x + 1; y * y <= n; y++) {
            if (x * x + y * y == n) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
for文の終了条件がx * x <= nと、少し見慣れない形式かもしれませんが、 これはx <= sqrt(n)とほぼ同義です。「ほぼ」というのは、sqrt関数は返り値がdouble型であり、誤差が生じてしまいます。 例えば5≤√25は真ですが、もしsqrt(25)で誤差が生じて4.9999999999となってしまったら偽になってしまいます(実際に誤った判定をするのはnがもっと大きいときです)。 しかし、5*5≤25と判定すれば誤差は生じません。 そのため、このコードではx * x <= nを採用しています。