部内勉強会（２） - octoの勉強記録

第２回　全探索とSTL

全探索

全てのアルゴリズムの基本

アルゴリズムは全探索と貪欲法に大きく分けることができて，全探索は必ず答えを出すことができる．貪欲法は答えを出せるかわからないので証明が必要．

今回はA~B問題レベルの全探索をやってみよう．

普通に解いてもいいけど全探索の方が楽

STLのコンテナクラス

vector

可変長配列、push_backが便利

  #include <bits/stdc++.h>
  using namespace std;
  int main()
  {
      int n = 100;
      vector<int> v(n, 0); //サイズn、全要素を0で初期化
      for (int i = 0; i < 100; i++)
      {
          v[i] = i;
      }
      v.push_back(10);                                //末尾に10を挿入
      cout << v.size() << endl;                       //要素数
      reverse(v.begin(), v.end());                    //逆順
      sort(v.begin(), v.end(), greater<int>());       // 降順ソート
      sort(v.begin(), v.end());                       //　昇順ソート
      auto low = lower_bound(v.begin(), v.end(), 20); //二分探索 値以上の最小値を探索
      cout << *low << endl;
      auto up = upper_bound(v.begin(), v.end(), 20); //二分探索　値より大きい最小値を探索
      cout << *up << endl;
  }

set

集合を管理する．中の実装は二分探索木

挿入，探索，削除がすべてO(log N)

unordered_setはO(１)だが，内部がソート済みにならないので嬉しくない

multisetは重複を許可する

  #include <bits/stdc++.h>
  using namespace std;
  int main()
  {
      set<int> s;
      s.insert(10);             //挿入
      s.erase(10);              //削除
      cout << s.size() << endl; //集合のサイズ
      for (int i = 0; i < 100; i++)
      {
          s.insert(i);
      }
      if (s.find(10) != s.end()) //値の探索　見つからないなら末尾を返す　
          cout << *s.find(10) << endl;
      auto low = s.lower_bound(30); //値の探索　引数以上の値の最小値へのポインタを返す
      cout << *low << endl;
      auto up = s.upper_bound(30); //値の探索　引数より大きい値の最小値へのポインタを返す
      cout << *up << endl;
      for (auto it : s) //拡張for文　内容を前から走査
      {
          cout << it << ' ';
      }
  }

map

辞書、中はpairの二分探索木、アクセスはO(log N)

pairがsetで管理されていると思うと良い

unordered_mapはハッシュで管理される

  #include <bits/stdc++.h>
  using namespace std;
  int main()
  {
      map<string, int> m; //キーがstring 値がint
      m["ghi"] = 3;       //値の挿入
      m["def"] = 2;
      m["abc"] = 1;
      cout << m["def"] << endl;
      for (auto it : m) //拡張for、中身はペア、キーの昇順
      {
          cout << it.first << ' ' << it.second << endl;
      }
  }

priority_queue

ヒープ，集合の最小値 or 最大値を得たいときに有効

挿入O(log N)，最小値(最大値)の参照O(１)，最小値(最大値)の削除O(log N)

  #include <bits/stdc++.h>
  using namespace std;
  int main()
  {
      priority_queue<int> que;                             //最大値から出るヒープ
      priority_queue<int, vector<int>, greater<int>> que2; //最小値から出るヒープ
      vector<int> v = {10, 5, 1, 7, 21, 13};
      for (auto it : v)
      {
          que.push(it); //挿入
          que2.push(it);
      }
      while (!que.empty()) //空かどうか判定
      {
          int x = que.top(); //参照
          que.pop(); //　削除
          cout << x << ' ';
      }
      cout << endl;
      while (!que2.empty())
      {
          int x = que2.top();
          que2.pop();
          cout << x << ' ';
      }
      cout << endl;
  }

pair

値のペア，ペアで値を管理したい時がある

３つ以上はタプルを使うか，自分で構造体を作る方が便利

  #include <bits/stdc++.h>
  using namespace std;
  typedef pair<int,int> P;
  int main(){
      P p = P(1,2);
      cout << p.first << ' ' << p.second << endl;
  }

例題

map

set