競プロ用のメモ

競プロ用のメモ。物置部屋的な記事。

• を で割るとき
  • 切り捨て : a / b
  • 切り上げ : (a + b - 1) / b
• 区間 内の の倍数のうち、最小と最大
  • 最小 :
  • 最大 :
• vector を set に、set を vector に

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> v = { 1, 1, 2, 2, 3, 4, 5, 5 };
  set<int> s(v.begin(), v.end());
  for (auto i : s) cout << i << " ";  // 1 2 3 4 5

  vector<int> v2(s.begin(), s.end());
  for (auto i : v2) cout << i << " ";  // 1 2 3 4 5
}

• multiset
  • 要素の重複を許す
  • find でイテレータを返す

#include <bits/stdc++.h>
using namespace std;

int main() {
  multiset<int> S = { 1, 2, 2, 3, 3, 3 };
  cout << S.size() << endl;  // 6
  S.erase(3);
  cout << S.size() << endl;  // 3 (3 全部消えた)
  S.erase(S.find(2));
  cout << S.size() << endl;  // 2 (2 ひとつ消えた)
}

• map
  • key が昇順にソートされている (value ではない)

#include <bits/stdc++.h>
using namespace std;

int main() {
  map<int, int> M;
  M[2] = 500;
  M[0] = 300;
  M[1] = 100;
  for (auto p : M) cout << p.first << " " << p.second << endl;
  // 0 300
  // 1 100
  // 2 500
}

• ダイクストラ法

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// N := 頂点の数
// G[i][j] := 隣接リスト表現。i から j.first へ向かう辺の重みが j.second
// d[i] := s から i への最短距離
vector<ll> dijkstra(int N, vector<vector<pair<int, ll>>> &G, int s) {
  priority_queue<pair<ll, int>> pq;
  const ll INF = 1LL << 60;
  vector<ll> d(N, INF);
  d.at(s) = 0;
  pq.push(make_pair(0, s));
  while (!pq.empty()) {
    auto p = pq.top();
    pq.pop();
    int u = p.second;
    ll dist = -p.first;
    if (dist > d.at(u)) continue;
    for (auto e : G.at(u)) {
      if (d.at(e.first) > d.at(u) + e.second) {
        d.at(e.first) = d.at(u) + e.second;
        pq.push(make_pair(-d.at(e.first), e.first));
      }
    }
  }
  return d;
}

• エラトステネスのふるいを利用した高速な素因数分解

#include <bits/stdc++.h>
using namespace std;

struct Sieve {
  vector<int> table, primes;
  // table[i] := i をふるいにかけた素数 (i の最小の素因数)

  Sieve(int N = 1) {
    table.resize(N+1);
    table.at(0) = table.at(1) = -1;
    for (long long i = 2; i <= N; i++) {
      if (table.at(i) > 0) continue;
      primes.push_back(i);
      table.at(i) = i;
      for (long long j = i*i; j <= N; j += i) {
        if (table.at(j) == 0) table.at(j) = i;
      }
    }
  }

  bool isPrime(int x) { return table.at(x) == x; }

  vector<pair<int, int>> prime_factorize(int x) {
    vector<int> factors;
    while (x != 1) {
      factors.push_back(table.at(x));
      x /= table.at(x);
    }
    if (factors.size() == 0) return {};
    // 列挙した素因数を (素因数, 個数) に整理
    vector<pair<int, int>> res;  // first: 素因数, second: 個数
    res.push_back(make_pair(factors.at(0), 0));  // ダミー
    for (int prime : factors) {
      if (res.back().first == prime) res.back().second++;
      else res.push_back(make_pair(prime, 1));
    }
    return res;
  }
};