Home

基本テンプレート

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){

    return 0;
}

素数表生成

vector<int> getPrime(int maxValue){
    vector<int> primes;
    vector<int> lpf(maxValue + 1, 0);
    for (int i = 2; i<= maxValue; i++){
        if (lpf[i] == 0){
            lpf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes){
            int mul = p * i;
            if (mul > maxValue || p > lpf[i]) break;
            lpf[mul] = p;
        }
    }
    return primes;
}

BFS

スタート地点からゴールまでの最短距離検索
計算量：O(N + M)
頂点数N, 辺数M, スタート頂点s

vector<vector<int>> Graph(N);
/* Graph[i].push_back(j); --- i→j の接続保存 */
vector<int> dist(N, -1); // sからの各頂点への最短距離が格納
queue<int> que;
dist[0] = 0;
que.push(s);

while(!que.empty()){
    int v = que.front();
    que.pop();

    for (int nv: Graph[v]){
        if (dist[nv] != -1) continue;
        dist[nv] = dist[v] + 1;
        que.push(nv);
    }
}

ランレングス圧縮

void RLE(string s, vector<pair<char, int>> &vec)
{
  int cnt = 1;
  for(int i = 1; i < (int)s.size(); i++){
    if(s[i] != s[i-1]){
      vec.push_back({s[i-1], cnt});
      cnt = 0;
    }
    cnt++;
  }
  vec.push_back({s.back(), cnt});
}

vector<pair<char, int>> svec;
RLE("abbbcc", svec);

出力形態指定

• 表示形式 (ex: ゼロ埋めでvalueを右側に合計2文字で。)

cout << setfill('0') << right << setw(2) << value;

• 出力桁数

cout << fixed;
cout << setprecision(10) << X;

コミット取り消し

$ git reset --soft HEAD^