競プロ 勉強記録#1

「問題解決力を鍛える!アルゴリズムとデータ構造」という本を購入したので、その勉強記録 #1。以下についてアウトプットしようと思う。

  • C++ での入出力インタフェースについて
  • 計算量について
  • 全探索について

C++ での入出力インタフェースについて

本の内容とは離れるが、C++ソース内にて、#include <iostream>と using namespace std;を記述する事で、cinとcoutを用いて簡単にターミナルに入出力を行える。個人的にPythonの使用が多いので、C++の備忘録の意味も込めて入出力例とソースを記載する。

例 1

整数 \(N\) が与えられます。 \(N\) を出力してください。

ソース

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    cout << N << endl;
}

入力例

7

出力例

7

また #include <vector>を記載することで、ソース内で動的な配列の宣言が可能となる。

例 2

\(N\) 個の足場があります。 足場には \(1,2,…,N\) と番号が振られています。各 \(i (1 \leq i \leq N)\) について、足場 \(i\) の高さは \(h_i\) です。 … 高さの総和 \(C\) を出力してください。

ソース

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

int main() {
    int N;
    cin >> N;

    vector<long long> h(N);
    for (int i = 0; i < N; ++i) cin >> h[i];

    int C = 0;
    for (int i = 0; i < N; ++i) {
        C += h[i];
    }

    cout << C << endl;    
}

入力例

4
10 30 40 20

出力例

100

Pythonでは.split()を用いて2つの変数に分けて代入するのを、C++ではcin >> A >> B;のように記載できる。他にも色々なパターンで入出力を問われると思うので早く慣れたい。(よく見るrep()が気になる。)

計算量について

アルゴリズムの良さを示す一つの指標として計算量があげられる。例えば、数当てクイズをする。この時、0から順に判定するのか(線形探索法)、ある数をもとに大小を判定して年齢を絞っていくのか(二分探索法)のアルゴリズムが考えられる。

この時、当てる数を \(N\)とする。条件として \(0 \leq N \leq 65536\) とした時、線形探索方と二分探索法の2通りの質問回数を比較する。

  1. 線形探索法の場合、 \(N = 65536\) としたら65536回質問しなければならない。 この計算量をオーダー記法で表すと \(O(N)\) である。
  2. 二分探索法の場合、もととする数を \(N/2\)とすると16回の質問で数を特定できる。この計算量をオーダー記法で表すと \(O(\log_2 N)\) である。

コンピュータが1秒間に計算できるステップの回数(計算量)は \(10^{9} = 1,000,000,000\) ほどである。そのため、なるべく計算量の小さいアルゴリズム設計が重要である。

全探索について

全探索とは解きたいタスクに対して、すべてのパターンを調べあげる手法である。中でも、以下のような具体的手法がある。

  • 線形探索法
    • 1つ1つの要素を順に調べていく。
    • \(N\)個の要素を持つ配列であれば、以下のイメージ。
for (int i = 0; i < N; ++i) {
    //　配列A[i]を判定
}
  • ペアの全探索
    • 2つの配列の要素同士のペアを調べていく。
    • \(N\)個の要素を持つ2つの配列であれば、以下のイメージ。
for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
        //　配列A[i]と配列B[j]のペアを判定
    }
}
  • 組み合わせの全探索
    • 1つの配列内での要素の組み合わせを調べていく。
    • \(N\)個の要素を持つ配列であれば、2進表現とビット演算を用いて調べ上げていくイメージ。
for (int bit = 0; bit < (1 << N); ++bit) {
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) {
            //　配列A[i]が部分集合に含まれている場合を判定
        }
    }
}

感想

問題をどう実装に落とし込むかが未だ慣れない。制約からアルゴリズムの方向性を決められるかどうかが重要な気がする。(e.g. \(0 < N < 200\)のとき\(N\)の範囲の全探索であればできるみたいな…) あとは問題数をこなしていきたい。

参考

  • 大槻兼資 著 秋葉拓哉 監修 (2020)．問題解決力を鍛える!アルゴリズムとデータ構造 講談社 Amazon Link