LoginSignup
269
267

More than 3 years have passed since last update.

@drken(けんちょん (Otsuki))in株式会社NTTデータ数理システム

線形探索を極める！ 〜 for 文で色んなことができることを知る 〜

Last updated at Posted at 2018-02-10

競技プログラミングサイト AtCoder へ参加するためのチュートリアル記事

の補足資料ですが、この記事単体でも読めるようになっています。

はじめに

for 文を 1 回回してできる処理は、しばしば線形探索といった名前で呼ばれていて、応用情報技術者試験などで頻出のテーマでもあります。本記事を読めば、応用情報に出題される線形探索の問題たちをスラスラと解けるようになると思います。

線形探索は最も基本的なアルゴリズムの 1 つですが、すべての基礎となる極めて重要なアルゴリズムです。世の中の多くの問題はとりあえず「全探索」すれば解が得られることが多いですが、全探索テクニックの最も基本的なものが「線形探索」です。まずは線形探索に習熟することが、アルゴリズム学習の第一歩と言えるでしょう。

それでは、線形探索によって実現できる処理たちを特集して行きます。

線形探索とは

仰々しい名前ですが、やりたいことは

  • なにかたくさんのものがあって、その中に探したいものがある
  • 1 個 1 個調べて、探したいものを探す

というだけのことです。例えば 54 枚 (ジョーカー含む) のトランプが裏になって並べられていて、その中からジョーカーを探したい問題は線形探索の一種と言えます。とても身近なアルゴリズムであることがわかると思います。

97f8cf653a0b8331f973bd8b104233c1.jpg
(リニアサーチ（線形探索法） ~『楽しく学ぶ　アルゴリズムとプログラミングの図鑑』よりより引用)

条件を満たすものを探す

まずは「線形探索」という言葉のイメージそのままな問題を考えてみましょう。

問題 1:　0 を探す

n 個の数値 a[0], a[1], ..., a[n-1] が与えられます。この n 個の数値の中に 0 が含まれるかどうかを判定してください。

【制約】

  • 1 <= n <= 10,000
  • -10,000,000 <= a[i] <= 10,000,000

【数値例】
1)
　n = 3
　a = (7, -6, 9)
　答え: "No"

7, -6, 9 の中に 0 はないので "No" と出力します。

2)
　n = 1
　a = (0)
　答え: "Yes"

たった 1 個の数値しかありませんが 0 があるので "Yes" と出力します。

早速ですが、これを実行できるコードを見てみましょう。

#include <iostream>
using namespace std;

int n;
int a[11000];           // 最大 10000 個なので余裕を持って 11000 に

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    bool res = false;   // 初期値は false に
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) res = true;   // 0 だったら true に (フラグを立てる)
    }

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

for 文を回している間、res という bool 変数に常に「今までに 0 があったか」を保持するようにして、0 が来たら res を true にする感じですね。初期値を false にしておくことがポイントです。

これは、フラグ管理においても共通の考え方になっています。
if (a[i] == 0) res = true;
の処理は、フラグを立てる操作に対応しています。

なお、以下のように 0 が見つかったらすぐに break するという考え方もあるでしょう。その方が条件を満たすものが見つかったときには計算実行が早く終了するメリットがあります。

// 見つかったら break するバージョン
#include <iostream>
using namespace std;

int n;
int a[11000];           // 最大 10000 個なので余裕を持って 11000 に

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    bool res = false;   // 初期値は false に
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            res = true;  // 見つかったら
            break;       // break
        }
    }

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

しかしながら、この工夫を施しても、計算量オーダーという意味でのアルゴリズムの良さは特に変わりません。計算量オーダーという概念は基本的には最悪ケース (0 が最後にあるか、0 がまったくないか) について考えることが多いのですが、break 処理を入れる前と後では、最悪ケースの実行速度は特に変わらないからです。

条件を満たすものがどこにあるのかも一緒に知る

条件を満たすものが見つかったかどうかだけでなく、どこにあったのかを一緒に知ることも実用上とても大切です。それはほんの少しプログラムを修正するだけでできます。

findID に見つかった場所を格納するのですが、注意点として、

findID = -1

と初期値を「ありえない値」に設定しておくことにより、この findID 自体が「条件を満たすものがあったかどうか」を表すフラグ変数の役割を果たすことができます！

なお注意点として、下のコードで求まる findID は 0-index (先頭の要素が 0 番目になる) です。先頭の要素を 1 番目にしたいときには findID に 1 を足します。

#include <iostream>
using namespace std;

int n;
int a[11000];           // 最大 10000 個なので余裕を持って 11000 に

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    int findID = -1;    // ここに見つかった場所を格納します (実はこれ自体がフラグの役割を果たします)
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) { // 見つかったら、
            findID = i;  // 場所を記録して、
            break;       // break
        }
    }

    if (findID != -1) cout << findID << endl;
    else cout << "No" << endl;
}

また、条件を満たすものをすべて拾い出したいときには、std::vector を用いると便利です。Python だと list ですね。

#include <iostream>
#include <vector>       // vector をインクルードします！
using namespace std;

int n;
int a[11000];           // 最大 10000 個なので余裕を持って 11000 に

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<int> findIDs;   // 0 の場所を格納
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) { // 見つかったら、
            findIDs.push_back(i);  // 場所を記録して、今度は break しない！！！ (すべて求めたいため)
        }
    }

    // 結果出力
    cout << "nums of zeros: " << findIDs.size() << endl; // 何個あったか
    for (int i = 0; i < (int)findIDs.size(); ++i) {
        cout << findIDs[i] << " th" << endl;
    }
}

条件を満たすものを数え上げる

今度は条件を満たすものを探すだけでなく、何個あるのかを数え上げてみましょう。
この処理は、先ほどの std::vector を用いて「条件を満たすものをすべて求める」処理の下位互換ではありますが、条件を満たすものを数え上げるだけであれば、std::vector を持ち出す必要はないです。

問題 2:　0 を数え上げる

n 個の数値 a[0], a[1], ..., a[n-1] が与えられます。この n 個の数値のうち 0 は何個あるかを出力してください。

【制約】

  • 1 <= n <= 10,000
  • -10,000,000 <= a[i] <= 10,000,000

【数値例】
1)
　n = 5
　a = (2, 0, 9, 0, -5)
　答え: 2　(2 個あります)

2)
　n = 2
　a = (-7, 9)
　答え: 0　(0 はないです)

早速ですがコードを見てみましょう。

#include <iostream>
using namespace std;

int n;
int a[11000];           // 最大 10000 個なので余裕を持って 11000 に

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    int res = 0;        // 初期値は 0 に
    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) ++res;   // 0 だったらカウントする
    }

    cout << res << endl;
}

今度は for 文を回している間、res という変数に常に「今までに何個 0 があったか」を保持するようにして、0 が来たら res をインクリメントしていく感じですね。変数 res に最後に入っている値が答えになります。

最小値を求める

ここまではザ・探索という感じでしたが、他にも色々なことができます。次のような問題を考えてみましょう。

問題 3:　最小値を求める

n 個の数値 a[0], a[1], ..., a[n-1] が与えられます。この n 個の数値のうち最も小さいものを出力してください。

【制約】

  • 1 <= n <= 10,000
  • -10,000,000 <= a[i] <= 10,000,000

【数値例】
1)
　n = 3
　a = (7, -6, 9)
　答え: -6

2)
　n = 1
　a = (-7)
　答え: -7　(数字が 1 個だけの場合もあります)

これを実現するコードを見てみましょう 

#include <iostream>
using namespace std;

const int INF = 10000000;   // 十分大きな値に

int n;
int a[11000];  // 最大 10000 個なので余裕を持って 11000 に

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    int res = INF;           // 十分大きな数に設定します
    for (int i = 0; i < n; ++i) {
        if (res > a[i]) res = a[i];
    }

    cout << res << endl;
}

for 文を回している間、res という変数に常に「今までで一番小さい値」を保持するようにして、res よりも小さな値 a[i] が来たら res を更新していく感じですね。最後に入っている値が答えになります。

res の初期値をどうするかが悩むところですが、問題に応じて適切に∞を表す定数 INF の値を定めてあげることになります。INF の値には気を使います。もし今回例えば

  • n = 3
  • a = (1964352, 114514, 6443455)

という入力だったときに

  • INF = 100000

と設定していたとしたら、答えは本当は 114514 なのに、出力は res = 100000 になってしまいます (考えてみて下さい)。

なお、今回の場合は初期値を以下のように設定してあげることもできます:

  • res = a[0]

こうすれば INF の値の決め方に悩む必要はなくなります。しかしながら INF を用いた処理というのは今後多数出て来ますので、INF の値をどの程度にしたらよいかを見積もることに慣れて行くことは重要です。これを読んで INT_MAX にすればいいじゃないかと思った方も多いと思いますが、

  • そもそも INT_MAX を超える可能性もある (その場合、そもそも int 型で処理してはいけません)
  • より複雑なアルゴリズムでは、INF 値の入った変数に値を加算したい場合がある (その場合、INT_MAX を用いているとオーバーフローしてしまいます)

という理由により、何も考えずに INT_MAX にするのは危険だと言えるでしょう。やはり INF の値をどの程度にしたらいいかを見積もる習慣をつけることが重要です。今回の用途であれば、INT_MAX を用いるのがむしろスタンダードだと思います。

最大値を求める

最小値ができたならば、最大値も簡単にできます。さっきと同じ入力で今度は最大値を求めてみましょう。次のようにすればよいです。

#include <iostream>
using namespace std;

const int INF = 10000000;   // 十分大きな値に

int n;
int a[11000];           // 最大 10000 個なので余裕を持って 11000 に

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];

    int res = -INF;                     // ここをマイナス INF に
    for (int i = 0; i < n; ++i) {
        if (res < a[i]) res = a[i]; // さっきと不等号の向きが反対に
    }

    cout << res << endl;
}

これだけで ABC B 問題のいくつかが解ける

ここまで出て来た話はあまりにも簡単だと思うかもしれませんが、これだけでも ABC の B 問題のいくつかが解けます！

ABC 081 B - Shift only

問題

黒板に $N$ 個の正の整数 $A_1, \dots, A_N$ が書かれています。
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます。

  • 黒板に書かれている整数すべてを，$2$ で割ったものに置き換える。

すぬけ君は最大で何回操作を行うことができるかを求めてください。

【制約】

  • $1 \le N \le 200$
  • $1 \le A_i \le 10^9$

【数値例】
1)
　$N = 3$
　$A = (16, 12, 24)$
　答え: $2$

1 回操作を行うと (8, 6, 12) になります。2 回操作を行うと (4, 3, 6) になります。2 個目の 3 が奇数なため 3 回目の操作は行えません。

実際に操作ができなくなるまで操作を繰り返してみましょう！！！
ここで、フラグの考え方が役に立ちます。すなわち、A の中に奇数が混じっているかどうかを判定します。

#include <iostream>
using namespace std;

int N;
int A[210];         // 最大 200 個なので余裕を持って 210 に

int main() {
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> A[i];

    int res = 0;

    // 操作が行える限り操作を繰り返す
    while (true) {
        bool exist_odd = false;
        for (int i = 0; i < N; ++i) {
            if (A[i] % 2 != 0) exist_odd = true;
        }

        if (exist_odd) break;  // 奇数があったら break

        // 操作を行えるなら操作を実際に行う
        for (int i = 0; i < N; ++i) {
            A[i] /= 2;
        }
        ++res;  // 操作回数をインクリメント
    }

    cout << res << endl;
}

なお、今回は実際に操作をシミュレーションすることによって解きましたが、以下のように考えることもできます。

N 個の A のうち、2 で割れる回数が最も小さいものがボトルネックになる。よって N 個の A それぞれについて 2 で割れるだけ割れる回数を求め、その最小値を求めればよい

この発想に基づくコードは以下になります。

#include <iostream>
using namespace std;

const int INF = 10000000;   // 十分大きな値に

int N;
int A[210];         // 最大 200 個なので余裕を持って 210 に

int main() {
  cin >> N;
  for (int i = 0; i < N; ++i) cin >> A[i];

  int res = INF;

  for (int i = 0; i < N; ++i) {
    int count = 0;  // 何回 2 で割れるか

    while (A[i] % 2 == 0) {
      A[i] /= 2;
      ++count;
    }

    // 最小値を更新
    if (res > count) res = count;
  }

  cout << res << endl;
}
269
267
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
269
267