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

概要

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

重要語

全探索

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

必要語

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

全探索

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

基本

要素数Nの数列AとKが与えられて、Ai×Aj≥Kとなる(i,j)の組の数を出力します。
#include <bits/stdc++.h>
int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::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++;
            }
        }
    }
    std::cout << ans << std::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>
int main() {
    int n;
    std::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++;
            }
        }
    }
    std::cout << ans << std::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を採用しています。

BFS

BFS(breadth first search, 幅優先探索)を用いると、迷路のスタートからゴールまでの最短距離を求めることなどができます。
BFSにはqueueというデータ構造を用いるとうまくいきます。queueは「キュー」と読み、先入れ先出し(First In First Out, FIFO)の構造になっています。
先入れ先出しとはどのようなものかというと、queueが英語で「順番を待つ人などの列」を表すとおり、そのイメージは「行列」です。
例えば、もし後から並ぶ人がいればその人はその列の最後尾に並び(先入れ)、もし席が空いたら案内されるのは列の先頭にいる人です(先出し)。

探索する迷路

ここでは、例として図のような迷路の探索を考えてみましょう。 白いマスが通行可能な空きます,黒いマスが通行不可能な壁マス,sがスタート,gがゴールを表しています。 通行可能なマスからは、上下左右に隣接する通行可能なマスに移動することができます。 迷路の外に移動することや、壁マスへ移動すること、斜めに移動することはできません。 最短何手でスタートからゴールまでたどり着けるかを求めてましょう。

Step1

まず、スタート地点のマスは当然スタート地点から手数0で到達可能なので、このマスは距離0で確定させます。

Step2

次に、上下左右を見て距離確定済みや範囲外,壁のマスでなければ手数1(=0+1)で到達できるマスとして距離1を書きます。 図の場合、上と左のマスが範囲外ですが下と右のマスは未確定ですので、下と右のマスを距離1で確定させます。

Step3

Step2で距離1を書いたマスから上下左右を見て、距離確定済みや範囲外,壁のマスでなければ手数2(=1+1)で到達できるマスとして距離2を書きます。 図の場合、スタート地点からみて右下のマスが距離2で確定されます。 下と右のどちらの1のマスから見るかによって2が確定する順番が違いますが、どちらも正しく距離2が書かれます (左上4マスをスタート地点から時計回りにA,B,C,DとするとB,Dが1のマスになりますが、 Bから上下左右に見てCを2と確定させたのちDから上下左右に見てCが埋まっていても、 Dから上下左右に見てCを2と確定させたのちBから上下左右に見てCが埋まっていても関係ありません)。

Step4

この操作を繰り返していきます(距離2を書いたマスから上下左右を見て距離3で確定させて、距離3を書いたマスから上下左右を見て距離4で確定させて...)。 このように7を書くまで繰り返したときが図の状態です。

終了条件

一見、「壁以外のすべてマスに距離が書かれたら」に見えますが、例えば到達することのできない孤立地帯があった場合などに無限ループしてしまいます。 より汎用的な終了条件は、「探索しても新たにマスが見つからなかったとき」でしょう。図の状態は、7のマスから上下左右に見ていますが、新たにマスを見つけることはできません。 このような状況の時、ループを抜けて探索を終了しましょう。

実装例

それでは、実装例を見ていきます。queueの使い方に注意してください。 左上(0,0)をスタート地点として、縦Hマス横WマスのH×Wマスからなる迷路を探索し、各マスについてスタート地点からの距離を求めます。 入力の形式は、1行目にH,Wが与えられ、2行目からのH行には迷路の各マスの情報が#は壁で.は道として与えられることを想定しています。
BFS
  #include <bits/stdc++.h>
  void BFS(int h, int w, int sx, int sy, std::vector<std::vector<int>> &d, std::vector<std::string> &s) {
      // x,yの上下左右移動を配列で持つ
      int vx[4] = {0, 1, 0, -1};
      int vy[4] = {1, 0, -1, 0};
      // スタート地点はスタート地点から距離0で到達可能
      d[sy][sx] = 0;
      // queueで訪問するべきマスを持つ
      std::queue<std::pair<int, int>> q;
      // 最初はスタート地点をqueueにqush
      q.push(std::make_pair(sx, sy));
      // queueが空になるまで(訪問するべきマスが無くなるまで)
      while (!q.empty()) {
          // queueの先頭が現在のマス
          std::pair<int, int> n = q.front();
          // 現在のマスはこれから見るのでpop
          q.pop();
          // 現在のマスから上下左右を見る
          for (int i = 0; i < 4; i++) {
              // nx,nyが現在のマスから見ているマスの座標
              int nx = n.first + vx[i];
              int ny = n.second + vy[i];
              // 範囲外アクセスをしないようにそのマスが迷路の外だったらcontinue
              if (nx < 0 || w <= nx || ny < 0 || h <= ny) continue;
              // そのマスが未訪問でかつ道のマスなら
              if (d[ny][nx] == -1 && s[ny][nx] == '.') {
                  // そのマスの距離は現在のマスから+1で到達可能なので更新
                  d[ny][nx] = d[n.second][n.first] + 1;
                  // そのマスを訪問するべきマスとしてqueueにpush
                  q.push(std::make_pair(nx, ny));
              }
          }
      }
      return;
  }
  int main() {
      // 縦と横を入力
      int h, w;
      std::cin >> h >> w;
      // 迷路を入力
      std::vector<std::string> s(h);
      for (int i = 0; i < h; i++) std::cin >> s[i];
      // スタート地点から各マスの最短距離(全てのマスを未訪問(-1)で初期化する)
      std::vector<std::vector<int>> d(h, std::vector<int>(w, -1));
      // BFSを行う
      BFS(h, w, 0, 0, d, s);
      // 結果を出力
      for (int i = 0; i < h; i++) {
          for (int j = 0; j < w; j++) {
              printf("%2d%s", d[i][j], j < w - 1 ? " " : "\n");
          }
      }
      return 0;
  }

計算量

では、BFSの計算量はどうなるでしょうか。BFSにおいて、queueにpushされるマスの数は高々H×W個です。そのため、計算量はO(HW)になります。