C++でアルゴリズム入門Part.2

さてさて、待望の第二回でございます。

今日からちょっと方針を変えて、猛スピードで進めていこうと思っています。

次回は二分探索とか言い残して終わったみたいなので、まぁそこから行ってみたいと思います。

二分探索とはその名のとおり、パターンを二つに分割していって探索していく手法です。
例えば与えられた配列から数字を取り出しては戻すことを四回繰り返し、その合計がある値になるものを探し出すといったようなコードを書くとします。

するとループ部分は次のようになります。

for (int a = 0; a < n; a++) {
  for (int b = 0; b < n; b++) {
    for (int c = 0; c < n; c++) {
      for (int d = 0; d < n; d++) {
        if (k[a] + k[b] + k[c] + k[d] == m) {
          f = true;
        }
      }
    }
  }
}

これは前回の内容を踏まえるとO(n^4)時間かかってることになります。

これを短縮する方法を考えます。一番内側の処理は、
ka+kb+kc+kd=mとなるdがあるか調べている
ので、式を移行して
kd=m-ka-kb-kcとなるdがあるか調べている
と考えます。

すると、このkdを二分探索することで時間が短縮できるようになります。
二分探索にはまず配列をソートし、m-ka-kb-kcが含まれるほうを残していく方法で実現できます。

どの位早いかというと、ソートにO(n log n)時間、ループにO(n^3 log n)時間で、このような際のプログラム全体の実行時間は足し算ではなく多い方を数えるので結局O(n^3 log n)時間のコードがかけます。（このlogは2を底にします。つまりO(log n)の時間は2^x=nを満たすO(x)ぐらいです。）

ここでコード例をだしてもいいのですが、これはもっと時間短縮できるのでそちらを載せようと思います。

さて、さらなる時間短縮にはループの一番内側ではなく、内側の二個のループに着目します。
発想は一つの時と同じで、
kc+kd=m-ka-kbとなるc,dがあるか調べている
と考えます。

するとソートはO(n^2 log n)時間と増えてしまいますが、ループにO(n^2 log n)時間しかかからないので結局全体の実行時間もO(n^2 log n)時間となります。

ではこのコードを見てみましょう。

#include <iostream>
#include <algorithm>
using namespace std;

const int MAX_N = 50;

int kk[MAX_N*MAX_N];
bool (int x) {
  // xの存在し得る範囲はkk[l], kk[l+1], ... , kk[r-1]
  int l = 0, r = n*n;

  // 範囲に何も含まれなくなるまで繰り返す。
  while (r - l >= 1) {
    int i = (l+r) / 2;
    if (kk[i] == x) return true; // 見つけた
    else if (kk[i] < x) l = i+1;
    else r = i;
  }

  return false; // 見つけられなかった
}
int main() {
  // 入力
  int n, m, k[MAX_N];
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> k[i];
  }

  // k[c]+k[d]の取り得る数を列挙
  for (int c = 0; c < n; c++) {
    for (int d = 0; d < n; d++) {
      kk[c * n + d] = k[c] + k[d];
    }
  }

  // 二分探索のためのソート
  sort(kk, kk + n * n);

  bool f = false;
  for (int a = 0; a < n; a++) {
    for (int b = 0; b < n; b++) {
      // 内側のループの代わりに二分探索
      if (binary_search(m - k[a] - k[b])) {
        f = true;
        break;
      }
    }
  }

  if (f) cout << "Yes" << endl;
  else cout << "No" << endl;
}

ライブラリとか自信ないわ…。

さてさて、このように最善のアルゴリズムを探し出すことがプログラミングコンテストの主目的になるわけです。
もっとも基礎的なことを学んだところで、アルゴリズムの基本に入っていきましょう。

とりあえず今回は基本の用語解説。

再帰関数

さて、すべての基本は全探索なわけですが、これの基本となる関数の手法が再帰関数です。

完結にいってしまうと関数の中でその関数自身をよびだすことを言います。
そしてこれには配列に保存していくことでさらに高速化することがあります。これはのちのちにやるの動的計画法やメモ探索という考え方の基本となります。

ではとりあえずフィボナッチ数列で例を見てみましょう。

int memo[MAX_N + 1];

int fib(int n) {
  if (n <= 1) return n;  // 再帰関数の特性上これをしないとプログラムが暴走する
  if (memo[n] != 0) return memo[n];
  return memo[n] = fib(n - 1) + fib(n - 2);
}

もしかしたらjavaではうまく動かないかも…？

スタック

スタックとはデータ構造の一種で、pushという操作でスタックの一番上にデータを積み、popという操作でスタックの一番上からデータを取り出します。
この操作は一般にLIFO(Last In First Out)と呼びます。

　　　　push　　　　push　データ３ pop pop
　　　 → データ２ → 　データ２ → データ２ →
データ１データ１データ１　　　データ１データ１

粗雑ですが雰囲気だけでもつかんでください(笑)

というかコード例で見たほうが早いかもですね。C++やJavaでは標準ライブラリとして提供されているので簡単にできます。

#include <iostream>
#include <stack>

using namespace std;

int main() {
  stack<int> s;            // int型をデータとするスタックの用意
  s.push(1);               // {}  -> {1}
  s.push(2);               // {1} -> {1,2}
  s.push(3);               // {1,2} -> {1,2,3}
  cout << s.top() << endl; // 3
  s.pop();                 // {1,2,3}-> {1,2}
  cout << s.top() << endl; // 2
  s.pop();                 // {1,2} -> {1}
  cout << s.top() << endl; // 1
  s.pop();
  return 0;
}

まぁこんな感じ。それぞれの関数はコメントで察してください。Javaメイン言語のくせにJavaのスタックは知らないので省略。

キュー

スタックと同じようにデータ構造の一種です。スタックと違ってpopが一番下からデータを取り出すことになります。
これはLIFOに対しFIFO(First In First Out)と呼ばれます。

これもスタックと同じように標準ライブラリで提供されます。

#include <iostream>
#include <queue>

using namespace std;

int main() {
  queue<int> que;                  // int型をデータとするキューを用意
  que.push(1);                     // pushはスタックと同様
  que.push(2);
  que.push(3);
  cout << que.front() << endl;     // 1
  que.pop();                       // {1,2,3} -> {2,3}
  cout << que.front() << endl;     // 2
  que.pop();                       // {2,3}   -> {3}
  cout << que.front() << endl;     // 3
  que.pop();                       // {3} -> {}
  return 0;                        
}