More than 3 years have passed since last update.

[競技プログラミング] C++ チートシート灰〜茶まで

Last updated at 2021-09-27Posted at 2021-02-19

まえがき

作成日 2021年2月19日

競技プログラミング初心者が作ったチートシートです
AtCoderBeginnerContestのA、B、C問まではカバーできる様更新を続けていきます。

快適にするために

サンプルテストを自動化
 提出結果をポップアップ通知

#テンプレート

内容

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

template<typename T> using v = vector<T>;
template<typename T> using vv = vector<vector<T>>;
template<typename T> using vvv = vector<vector<vector<T>>>;
template<typename T> inline void errv(T& v) { for (auto x: v) cerr << x << " "; cerr << endl; }
inline void errv(vector<bool>& v) { for (auto x: v) cerr << (x ? 1 : 0) << " "; cerr << endl; }
template<typename T> inline void dbgn(string n, T x) { cerr << n << ": " << x << endl; }
template<typename T> inline void dbgn(string n, vector<T>& v) { cerr << n << ": "; errv(v); }
template<typename T> inline void dbgn(string n, vector<vector<T>>& m) { cerr << n << ":" << endl; for (auto& v: m) errv(v); }

#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repp(i, c, n) for (ll i = c; i < (n); ++i)
#define repa(i, a) for (auto i: a)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define so(v) sort((v).begin(), (v).end())
#define rso(v) sort((v).rbegin(), (v).rend())
#define len(x) ll((x).size())

//p(出力) d(デバッグ *多次元配列も可能*)
#define p(x) cout << x << endl;
#define d(x) dbgn(#x, x);

const ll INF = 1LL << 60;  //無限大
const ll MOD = 1000000007; //10^9 + 7

int main(){

  return 0;
}

**include "bits/stdc++.h"**が使えない場合
以下を記載しておけば基本includeでのエラーは無くなる。(と思う)

#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

#コード

##基本コード復習

内容

1 秒間で処理できる for 文ループの回数は、

10^8=100,000,000 回程度

計算量オーダーの求め方を総整理！〜どこから log が出て来るか〜

int にはいる最大桁数は

±2.15×10^9 = 10 桁程度

longlong 8×10^18

なので目安として「8桁」あたりからlonglongを使うようにする。

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

int main() {
  // 文字(シングルクォーテーション)
  char c = 'a';
  // 文字列(ダブルクォーテーション)
  string s = "abc";
  int num = 0;
  long long lnum = 0;
  double dou = 1.0;

  // 入力
  cin >> s;
  // 出力(<<endl;をつけると改行)
  cout << s << endl;

  if (true){
  } else{
  }

  // orは||  andは&&
  if (true && true){
  } else if (true || true){
  }

  for (int i = 0; i < 5; i++){
  }

  // 文字列出力
  for (auto c : "abc"){
    cout << c << ", "; // a, b, c, ,
  }
  cout << endl;

  // 配列出力
  for (int it : {8, 10, 18}){
    cout << it << ", "; // 8, 10, 18
  }
  cout << endl;

  while (true){
    break;
  }


  // 1でもtrueの意味を持つ
  bool frip = true;
  frip = not frip;
  cout << frip << endl; // 0
  cout << boolalpha << frip << endl; // false

  bool ok = true;
  cout << (ok?"Yes":"No") << endl; // "Yes"
}

数値操作

数値の桁数, 数値切り抜き, 数値から文字へ

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

int main() {
  int num = 1234;

  // 数値の桁数
  cout << int(log10(num)+1) << endl; // 4

  // 数値切り抜き
  cout << num % 10 << endl;         // 4
  cout << (num / 10) % 10 << endl;  // 3
  cout << (num / 100) % 10 << endl; // 2
  cout << num / 1000 << endl;       // 1

  // 数値から文字へ
  string str = to_string(num);
  cout << str << endl; // 1234
}

少数桁を切り上げ, 切り捨て

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

int main() {
  double dou = 1.234;
  
  // 少数桁を切り上げ
  cout << ceil(dou) << endl; // 2
  cout << int(dou + 0.99999) << endl; // 2

  // 少数桁を切り捨て
  cout << int(dou) << endl; // 1
}

割り算の切り上げ, 四捨五入

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

int main() {
  int a = 10, b = 3;
  // 切り上げ
  cout << (a + (b - 1)) / b << endl; // 4
  
  // 四捨五入
  cout << (a + (b / 2)) / b << endl; // 3
}

##文字列操作

追加と削除

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

int main() {
  // 追加
  string s;
  s = "abcd";
  s.insert(0, "A");
  cout << s << endl; // "Aabcd"

  // 末尾に追加 char「''」 と　string「""」を気をつける
  s = "abcd";
  s.push_back('X');
  cout << s << endl; // "abcdX"

  // 削除
  s = "abcd";
  s.erase(2, 1); // erase(n, m) n文字目からm文字削除
  cout << s << endl; // "abd"
  s.erase(1); // erase(n) n文字目以降全削除
  cout << s << endl; // "a"

  // 末尾の文字削除
  s = "abcd";
  s.pop_back();
  cout << s << endl; // "abc"

  // 置換 n番目から数えてm個の文字列をXに置換したい場合replace(n, m, X)
  s = "abcd";
  s.replace(1, 1, "B");
  cout << s << endl; // "aBcd"
}

文字取得

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

int main() {
  string s = "abcd";

  // 文字取得
  cout << s[2] << endl;  // c
  cout << s.size() << endl; // 4

  // n番目以降の文字列をm文字だけ取り出す場合substr(n, m)
  cout << s.substr(1) << endl; // "bcd"
  cout << s.substr(1, 2) << endl; // "bc"

  // 文字列出力
  for (char c : "abcd"){
    cout << c << " "; // a b c d
  }
}

操作

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

int main() {

  // 文字列から数値へ
  cout << stoi("100") << endl;
  // 数値から文字列へ
  cout << to_string(100) << endl;
  // 同じ文字を繰り返す
  cout << string(5, 'a') << endl; // aaaaa

  // 文字列ソート
  string s = "cbad";
  sort(begin(s), end(s));
  cout << s << endl; // "abcd"

  sort(begin(s), end(s), greater<>());
  cout << s << endl; // "dcba"

  // 文字列を反転
  s = "abcd";
  reverse(s.begin(), s.end());
  cout << s << endl; // "dcba"

  // 文字からASCII番号へ
  char c = 'a';
  cout << int(c) << endl; // 97

  // ASCII番号から文字へ
  int num = 90;
  cout << char(num) << endl; // Z
}

文字	ASCII番号
0	48
A	65
Z	90
a	97
z	122

C++ の文字列操作まとめ

vector

入出力

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

int main() {
  // 宣言 (入力数をNとする)
  int N = 4;
  vector<int> v(N);

  // 入力
  for (int i = 0; i < N; ++i) cin >> v[i];

  // 出力
  for (int i = 0; i < v.size(); ++i) cout << v[i] << " "; // 1 2 3 4
  for (int it: v) cout << it << " "; // 1 2 3 4
}

追加、削除、要素数

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

int main() {
  // 末尾に追加
  vector<int> v = {1,2,3,4};
  v.push_back(5);
  for (int it: v) cout << it << " "; // 1 2 3 4 5

  // 末尾から削除
  v = {1,2,3,4};
  v.pop_back();
  for (int it: v) cout << it << " "; // 1 2 3

  // 要素数を取得
  v = {1,2,3,4};
  cout << v.size() << endl; // 4
}

操作

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

int main() {
  vector<int> v;

  // 配列を反転
  v = {1,2,3,4};
  reverse(begin(v), end(v));
  for (int it: v) cout << it << " "; // 4 3 2 1

  // nums[0:N] を小さい順にソート
  v = {3,1,2,4};
  sort(v.begin(), v.end());
  for (int it: v) cout << it << " "; // 1 2 3 4

  sort(v.begin(), v.end(), greater<int>());
  for (int it: v) cout << it << " "; // 4 3 2 1
}

多次元配列

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

int main() {
  vector<vector<int>> vv;
  vector<vector<vector<int>>> vvv;
  vv = {{1, 2}, {3}};
  cout << vv[0][1] << endl; // 2
}

vectorからsetへ

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

int main() {
  vector<int> v = {1,2,2,3,3,4};
  set<int> s;
  for (long unsigned int i = 0; i < v.size(); ++i) s.insert(v[i]);
  for(auto it: s) cout << it << " "; // 1 2 3 4
}

###配列検索

binary_search

二分探索をすることができる関数

配列の中にkeyがあるかどうかは分かる
しかし、どこにkeyがあるのか分からない
さらに、同じ値のkeyが複数あったとき、どのkeyを指しているのか分からない
という特徴を持つ

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

int main() {
  vector<int> nums = { 1, 4, 4, 7, 7, 8, 8, 11, 13, 19};
  sort(nums.begin(), nums.end());

  cout << boolalpha << binary_search(nums.begin(), nums.end(), 3) << endl; // False
  cout << boolalpha << binary_search(nums.begin(), nums.end(), 4) << endl; // True
  cout << boolalpha << binary_search(nums.begin(), nums.end(), 9) << endl; // False
}

lower_bound

二分探索をすることができる関数

lower_boundは、ソートされた配列内で、key以上の要素の内の一番左側のイテレータを返す[setでも使用可能]

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

int main() {
  vector<int> nums = { 1, 4, 4, 7, 7, 8, 8, 11, 13, 19};
  sort(nums.begin(), nums.end());

  // イテレーターを返す
  auto Iter1 = lower_bound(nums.begin(), nums.end(), 4);
  auto Iter2 = lower_bound(nums.begin(), nums.end(), 9);

  // keyと同じ以上の最も近い値を返す
  cout << *Iter1 << endl; // 4
  cout << *Iter2 << endl; // 11 (key:9 は nums[6]=8 と nums[7]=11 との間)

  // インデックス
  cout << Iter1 - nums.begin() << endl; // 1
  cout << Iter2 - nums.begin() << endl; // 7
}

他にもupper_boundってのもある

参考
lower_boundとupper_boundの使い方

set

重複と順番を自動に整理してくれる（重複なし）

追加、削除、要素数

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

int main() {
  set<int> s;

  // 追加
  s = {1, 2, 3, 4};
  s.insert(5);
  for(auto it: s) cout << it << " "; // 1, 2, 3, 4, 5

  // 削除
  s = {1, 2, 3, 4};
  s.erase(3);
  for(auto it: s) cout << it << " "; // 1, 2, 4

  // 要素数
  s = {1, 2, 3, 4};
  cout << s.size() << endl; // 4
}

setからvectorへ

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

int main() {
  set<int> s{1, 2, 3, 4};
  vector<int> v;

  for(auto it: s) v.push_back(it);
  for(auto it: v) cout << it << " "; // 1 2 3 4
}

###set検索

lower_bound

二分探索をすることができる関数

lower_boundは、ソートされた配列内で、key以上の要素の内の一番左側のイテレータを返す[vectorでも使用可能]

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

int main() {
  set<int> s;
  s = {1, 3, 6, 10};
  // 5 以上の要素のうち最小の要素のイテレータを取得
  auto it = s.lower_bound(5);
  // it の示す要素を出力
  cout << *it << endl;  // 6 を出力
  // it の1つ前のイテレータの示す要素を出力
  cout << *prev(it) << endl; // 3 を出力
}

他にもupper_boundってのもある

参考
lower_boundとupper_boundの使い方

map

平衡二分木
要素の要素数に対する対数オーダーでの高速な検索能力と
内部で要素がソート状態で保持されるという特徴を持つ。

辞書みたいな使い方が多い
2つの値について1対1対応をさせることが可能

追加、削除、要素数

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

int main() {
  // デフォルト初期化
  map<string, int> mp{};

  // 追加
  mp["Alice"] = 30;
  mp["Bob"] = 15;
  mp["Carol"] = 21;

  // 削除
  mp.erase("Carol"); // "Carol" を削除

  // 全削除
  mp.clear();

  // 要素数
  mp = {{"Alice", 30}, {"Bob", 15}, {"Carol", 21}};
  cout << mp.size() << endl; // 3
}

参照、検索

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

int main() {
  map<string, int>  mp;

  // 参照
  mp = {{"Alice", 30}, {"Bob", 15}, {"Carol", 21}};
  cout << mp["Alice"] << endl; // 30
  cout << mp.begin()->second << endl; // 30   (Aliceの値)
  cout << mp["Bob"] << endl; // 15
  cout << mp.rbegin()->second << endl; // 21   (Carolの値)

  // 検索
  mp = {{"Alice", 30}, {"Bob", 15}, {"Carol", 21}};
  cout << boolalpha << (mp.find("hoge") != mp.end()) << endl; // false
  cout << mp.count("hoge") << endl; // 0
}

使用例
abc206_c

参考
std::mapまとめ

pair

2つの異なる型を一つの変数で持つことができる「組」を表現できる型
3つの異なる型の場合はtupleがある

追加、取得

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

int main() {
  // 宣言
  pair<int, string> p;

  // 追加
  p.first = 30;
  p.second = "Alice";

  // 取得
  cout << p.first << endl; // 30
  cout << p.second << endl; // Alice
}

配列を使う

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

int main() {
  // 宣言
  vector<pair<int, string>> p;

  // 追加
  p.push_back({ 30, "Alice" });
  p.push_back({ 15, "Bob" });
  p.push_back({ 21, "Carol" });
  for (long unsigned int i = 0; i < p.size(); i++) cout << p[i].first << " " << p[i].second << " ";
  // 30 Alice 15 Bob 21 Carol

  // 追加2 (入力数をNとする)
  int N = 1;
  vector<pair<int, string>> vp(N);
  vp[0].first = 30;
  vp[0].second = "Alice";
  for (long unsigned int i = 0; i < vp.size(); i++) cout << vp[i].first << " " << vp[i].second << " ";
  // 30 Alice

  // ソート
  p = {{{30, "Alice"}, {15, "Bob"}, {21, "Carol"}}};
  sort(p.begin(), p.end());
  for (long unsigned int i = 0; i < p.size(); i++) cout << p[i].first << " " << p[i].second << " ";
  // 15 Bob 21 Carol 30 Alice

  sort(p.begin(), p.end(), greater<>());
  for (long unsigned int i = 0; i < p.size(); i++) cout << p[i].first << " " << p[i].second << " ";
  // 30 Alice 21 Carol 15 Bob
}

使用例
日本で2番目に高い山の名前を求める場合など。。。

参考
ペアの配列の初期化にC ++ 14で二重中括弧が必要なのはなぜですか？

##queue

上から入れて上から取り出す。

program.C++

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

int main() {
  queue<int> que; // que = {}

  // 追加
  que.push(1);    // que = {1}
  que.push(2);    // que = {1,2}
  que.push(3);    // que = {1,2,3}

  // 取得
  cout << que.front() << endl; // 1
  // 削除
  que.pop();      // que = {2,3}

  cout << que.front() << endl; // 2
  que.pop();      // que = {3}
}

priority_queue

優先度付きキュー
ソートの機能が付いたキュー

program.C++

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

int main() {
  priority_queue<int, vector<int>, greater<int>> Q;

  // 追加
  Q.push(116); // que = {116}
  Q.push(145); // que = {116, 145}
  Q.push(122); // que = {116, 122, 145}

  // 取得
  cout << Q.top() << endl; // 116
  // 削除
  Q.pop(); // que = {122, 145}
}

stack

上から入れて下から取り出す。

program.C++

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

int main() {
  stack<int> sta; //s = {}

  // 追加
  sta.push(1);    //s = {1}
  sta.push(2);    //s = {1,2}
  sta.push(3);    //s = {1,2,3}

  // 取得
  cout << sta.top() << endl;  // >>> 3
  // 削除
  sta.pop();      //s = {1,2}

  cout << sta.top() << endl;  // >>> 2
  sta.pop();      //s = {1}
}

next_permutation

次の順列を作成する関数

{1, 2, 3}
{1, 3, 2}
{2, 1, 3}
...

のような値が欲しい場合に使える

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

int main() {
  vector<int> v = {1, 2, 3};

  // 1回目
  for(auto it: v) cout << it << " "; // 1 2 3

  // 2回目
  next_permutation(v.begin(), v.end());
  for(auto it: v) cout << it << " "; // 1 3 2

  // 3回目
  next_permutation(v.begin(), v.end());
  for(auto it: v) cout << it << " "; // 2 1 3

  // 4回目
  next_permutation(v.begin(), v.end());
  for(auto it: v) cout << it << " "; // 2 3 1
}

他に使える標準ライブラリ

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

int main() {
  // 絶対値 abs(x);
  cout << abs(-100) << endl; // 100

  // 三角関数(弧度法を使用)
  double pi = 3.141592653589793238;
  cout << sin(pi/6) << endl; // 0.5
  cout << cos(0 / 180.0 * pi) << endl; // 1

  // 最大を求める max(a, b);
  cout << max(1, 20) << endl; // 20
  cout << max({1, 6, 10, 2}) << endl; // 10

  // 最小を求める min(a, b);
  cout << min(1, 20) << endl; // 1

  // 値を交換する
  int a = 1, b = 5;
  swap(a, b);
  cout << a << " " << b << endl; // 5 1

  // a, bの最大公約数 __gcd(a, b);
  cout << __gcd(2, 3) << endl; // 1

  // a, bの最小公倍数 a / __gcd(a, b) * b;
  cout << 2 / __gcd(2, 3) * 3 << endl; // 6

  // xの2乗 pow(x, 2);
  cout << pow(3, 2) << endl; // 9

  // ルートx sqrt(x);
  cout << sqrt(2) << endl; // 1.41421

  // 乱数
  cout << rand() << endl;
  // 1 以上 6 以下のランダムな整数を出力する場合
  cout << rand() % 6 + 1 << endl;
}

参考
厳選！C++ アルゴリズム実装に使える 25 の STL 機能

入出力

入力

"""
入力値 >>> A B
"""
string strA, strB;
cin >> strA >> strB;  


"""
入力値 >>> d1 d2 ... dN
&
入力値 >>> d1 
          d2 
          ...
          dN
"""
vector<int> v(N);
for (int i = 0; i < N; ++i) cin >> v[i];


"""
入力値 　>>> 3 4
          99 99 99
          99 0 99
          99 99 99
          99 99 99
"""
int H,W;
cin >> H >> W;
int box[H][W];
for(int i = 0; i < H; i++){
    for(int k = 0; k < W; k++){
    cin >> box[i][k];
    }
}


"""
入力値 >>> 10 12
          W........WW.
          .WWW.....WWW
          ....WW...WW.
          .........WW.
          .........W..
          ..W......W..
          .W.W.....WW.
          W.W.W.....W.
          .W.W......W.
          ..W.......W.
"""

// 入力
int N, M;
vector<string> field;

// 入力受け取り
cin >> N >> M;
field.resize(N + 1);
for (int n = 0; n < N; ++n) cin >> field[n];
// field[0] == "W........WW."


"""
入力値 >>> d1 d2 .. d? （入力数が不明）
"""
vector<int> v;
while(true){
  int x;
  cin >> x;
  if(cin.eof()) break;
  v.push_back(x);
}
/*
windowsは「Ctrl+Z」
Macは「Ctrl+D」
で標準入力終了(EOF)となる
*/

##出力

"""
桁数指定
"""
long double ans=1.111111111111111;
cout << fixed << setprecision(2) << ans << endl;
// 1.11 (小数点2桁)

"""
配列全出力
"""
for(auto it: v) cout << it << endl;

"""
セット全出力
"""
for(auto it: s) cout << it << endl;

"""
場合分け
"""
ok = true;
cout << (ok?"Yes":"No") << endl; // Yes

アルゴリズム

名前	使った(○)・使っていない(×)	重要度(高・中・低)
bit全探索	○	高
二分探索	○	高
累積和	○	高
約数全列挙	○	高
素因数分解	○	高
GCD・LCM	○	高
貪欲法	○	中
幅優先探索(BFS)	×	中
深さ優先探索(DFS)	×	中
imos法	×	低
動的計画法(DP)	×	低
優先度付きキュー	×	低
グラフアルゴリズム	×	低
ダブリング	×	低
Union-Find Tree	×	低

引用
【AtCoder】普通の人である私が緑になるまでにしたこと

bit全探索

内容

###基本コード

// シフト演算
// (1 << 0); // 0000 0000 0000 0001(2進数) => 1(10進数) 2^0
// (1 << 1); // 0000 0000 0000 0010(2)    => 2(10)     2^1
// (1 << 2); // 0000 0000 0000 0100(2)    => 4(10)     2^2
// (1 << 3); // 0000 0000 0000 1000(2)    => 8(10)     2^3
// (1 << 4); // 0000 0000 0001 0000(2)    => 16(10) つまり4個の並べ方の全通りは16(空の状態を含む)

for (int bit = 0; bit < (1<<N); ++bit) {

}

###例題1
bit 全探索についてから引用
N 個の正の整数 a0,a1,…,aN−1 と、正の整数 W とが与えられる。
a0,a1,…,aN−1 の中から何個か選んで総和を W とすることができるかどうかを判定せよ。

制約
1≤N≤20 （bit全探索では制約が小さいことが条件）

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

// int 型を vector 型に変換
// bit: 集合を表す整数
// N: 何個のものについて考えているか
vector<int> IntegerToVector(int bit, int N) {
    vector<int> S;
    for (int i = 0; i < N; ++i) {
        if (bit & (1 << i)) { // ビットフラグの判定 AND演算 互いに1のbitを1とする (11111111 & 10101010 は、10101010) true=1
            S.push_back(i);
        }
    }
    return S;
}

int main() {
    // 入力
    int N, W;
    cin >> N >> W;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // bit 全探索
    bool exist = false;
    for (int bit = 0; bit < (1 << N); ++bit) {
        // どれを選ぶか
        vector<int> S = IntegerToVector(bit, N); // 1回目S={0} 2回目S={1} 3回目S={0,1} 4回目S={2}....

        // 部分集合に対応する総和
        int sum = 0;
        for (int i : S) sum += a[i];

        // 判定
        if (sum == W) exist = true;
    }

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

###例題2
典型90問　002 - Encyclopedia of Parentheses（★3）
長さ N の正しいカッコ列をすべて、辞書順に出力してください。
ただし、正しいカッコ列とは以下のことを指すものとします。
・"()" は正しいカッコ列である
・S が正しいカッコ列であるとき、文字列 "(" + S + ")" は正しいカッコ列である
・S, T が正しいカッコ列であるとき、文字列 S+T は正しいカッコ列である
また、')' より '(' の方が辞書順で早いものとする。

制約
1≤N≤20 （bit全探索では制約が小さいことが条件）
Nは整数

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

bool hantei(string S) {
	int dep = 0;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == '(') dep += 1;
		if (S[i] == ')') dep -= 1;
		if (dep < 0) return false;
	}
	if (dep == 0) return true;
	return false;
}

int main() {
	int N;
	cin >> N;
	for (int i = 0; i < (1 << N); i++) {
		string Candidate = "";
		for (int j = N - 1; j >= 0; j--) {
			// メモ : (i & (1 << j)) = 0 というのは、i の j ビット目（2^j の位）が 0 であるための条件。
			// 　　　頻出なので知っておくようにしましょう。
			if ((i & (1 << j)) == 0) {
				Candidate += "(";
			}
			else {
				Candidate += ")";
			}
		}
		bool I = hantei(Candidate);
		if (I == true) cout << Candidate << endl;
	}
	return 0;
}

類題
ABC064 D - Insertion
ABC147 C - HonestOrUnkind2
ABC190 C - Bowls and Dishes
ABC197 C - ORXOR

二分探索法

内容

###基本コード
二分探索アルゴリズムを一般化〜めぐる式二分探索法のススメ〜より引用

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

vector<int> a = {1, 14, 32, 51, 51, 51, 243, 419, 750, 910};

// index が条件を満たすかどうか
bool isOK(int index, int key) {
    if (a[index] >= key) return true;
    else return false;
}

// 汎用的な二分探索のテンプレ
int binary_search(int key) {
    // 配列a の左端と右端を決定し、真ん中の値を取得。
    // 引数(今回はkey)が真ん中の値より大きければ left=mid　とし、再度左端と右端の真ん中の値を取得する。

    long long left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    long long right = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* どんな二分探索でもここの書き方を変えずにできる！ */
    while (right - left > 1) {
        long long mid = left + (right - left) / 2;

        if (isOK(mid, key)) right = mid;
        else left = mid;
    }

    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
    return right;
}

int main() {
    cout << binary_search(51) << endl; // a[3] = 51 (さっきは 4 を返したが今回は「最小の index」なので 3)
    cout << binary_search(1) << endl; // a[0] = 1
    cout << binary_search(910) << endl; // a[9] = 910

    cout << binary_search(52) << endl; // 6
    cout << binary_search(0) << endl; // 0
    cout << binary_search(911) << endl; // 10 (場外)
}

めぐる式ニ分探索は「けんちょん」さんの二分探索アルゴリズムを一般化〜めぐる式二分探索法のススメ〜をご覧ください
私が理解でき次第更新します。

###例題
典型90 001 - Yokan Party（★4）
左右の長さがL[cm] のようかんがあります。N個の切れ目が付けられており、左からi番目の切れ目は左からAi[cm] の位置にあります。
あなたはN個の切れ目のうちK個を選び、ようかんをK+1個のピースに分割したいです。そこで、以下の値をスコアとします。
K+1個のピースのうち、最も短いものの長さ（cm 単位）スコアが最大となるように分割する場合に得られるスコアを求めてください。

制約
1≤K≤N≤100000
0<A1<A2<...<AN<L≤10^9
入力はすべて整数

#include <iostream>
using namespace std;

long long N, K, L;
long long A[1 << 18];

bool solve(long long M) {
    long long cnt = 0, pre = 0;
    for (int i = 1; i <= N; i++) {
        if (A[i] - pre >= M && L - A[i] >= M) {
            cnt += 1;
            pre = A[i];
        }
    }
    if (cnt >= K) return true;
    return false;
}

int main() {
    // Step #1. 入力
    cin >> N >> L;
    cin >> K;
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }
    
    long long left = -1;
    long long right = L + 1;
    while (right - left > 1) {
        long long mid = left + (right - left) / 2;
        if (solve(mid) == false) right = mid;
        else left = mid;
    }
    cout << left << endl;
    return 0;
}

類題
ABC023 D - 射撃王

累積和

内容

累積和を何も考えずに書けるようにする！から引用

高校数学の「数列と数学的帰納法」を使用
制約は N=300,000(10^5) 程度

###基本コード

int N; cin >> N; // 配列サイズ
vector<int> a(N);
for (int i = 0; i < N; ++i) cin >> a[i]; // a の入力

// 累積和（前処理）
vector<int> s(N+1, 0); // s[0]からs[N]まで 0 で初期化
for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i]; // 累積和(a[0]からa[i]までの和)をsに追加

// 区間 [left, right) の総和を求める
int left, right;
cin >> left >> right;
cout << s[right] - s[left] << endl;

###例題
AOJ0516 - 最大の和
n 個の整数からなる数列 a1, a2, ..., an と正整数 k (1 ≤ k ≤ n) が与えられる.このとき, 連続して並ぶ k 個の整数の和 Si = ai + ai+1 + ... + ai+k-1 (1 ≤ i ≤ n - k + 1) の最大値を出力するプログラムを作りなさい.

制約
1≤K≤N≤100000
-10^4≤a[i]≤10^4

sample
N=5
K=3
a=(2,5,−4,10,3)
答え: 11 （5,−4,10 を選ぶのが最大）

#include <iostream>
#include <vector>
using namespace std;
const long long INF = 1LL<<60; // 仮想的な無限大の値

int main() {
    // 入力
    int N, K;
    while (cin >> N >> K) {
        if (N == 0) break;
        vector<long long> a(N);
        for (int i = 0; i < N; ++i) cin >> a[i];

        // 累積和を前計算
        vector<int> s(N+1, 0);
        for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i];

        // 答えを求める
        long long res = -INF; // 最初は無限小の値に初期化しておく
        for (int i = 0; i <= N-K; ++i) {
            long long val = s[K+i] - s[i];
            if (res < val) res = val;
        }
        cout << res << endl;
    }
}

類題
ABC084 D - 2017-like Number
ABC122 C - GeT AC
AGC023 A - Zero-Sum Ranges

二次元累積和
ABC005 D - おいしいたこ焼きの焼き方

しゃくとり法(尺取り法)

参考
しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ

DFS(深さ優先探索)

内容

###基本コード

有向グラフの時のグラフ入力受け取り

#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

int main() {
    // 頂点数と辺数
    int N, M; cin >> N >> M;

    // グラフ
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);

        // 無向グラフの場合は以下を追加
        // G[b].push_back(a);
    }
}

seen 全体を false に初期化して、todo を空にする
seen[s] = true として、todo に s を追加する
todo が空になるまで以下を繰り返す:
todo から一つ頂点を取り出して v とする
T(v) の各要素 w に対して、
seen[w] = true であったならば、何もしない
そうでなかったら、seen[w] = true として、todo に w を追加する

地点「s」から「t」まで行けるか

有向グラフ

入力
3 3 1 2 //(頂点の数)(辺の数)(スタート地点)(終了地点)
1 2     //(頂点「1」から頂点「2」への一方通行)
2 3     //(頂点「2」から頂点「3」への一方通行)
3 1     //(頂点「3」から頂点「1」への一方通行)

出力
Yes

#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;

// 深さ優先探索
vector<bool> seen;
void dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする

    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) { 
        if (seen[next_v]) continue; // next_v が探索済だったらスルー
        dfs(G, next_v); // 再帰的に探索
    }
}

int main() {
    // 頂点数と辺数、s と t
    int N, M, s, t; cin >> N >> M >> s >> t;

    // グラフ入力受取
    Graph G(N);
    for (int i = 0; i < M; ++i) {
        int a, b;
        cin >> a >> b;
        G[a].push_back(b);
        // 無向グラフの場合は以下を追加
        // G[b].push_back(a);
    }

    // 頂点 s をスタートとした探索
    seen.assign(N, false); // 全頂点を「未訪問」に初期化
    dfs(G, s);

    // t に辿り着けるかどうか
    if (seen[t]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

連結成分の個数

グリッドグラフの場合

問）点sから「.」を通って点gまでたどり着くことは可能か

入力

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

出力

Yes

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

// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

// 入力
int H, W;
vector<string> field;

// 探索
bool seen[510][510]; // seen[h][w] := マス (h, w) が検知済みかどうか
void dfs(int h, int w) {
    seen[h][w] = true;

    // 四方向を探索
    for (int dir = 0; dir < 4; ++dir) {
        int nh = h + dx[dir];
        int nw = w + dy[dir];

        // 場外アウトしたり、移動先が壁の場合はスルー
        if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
        if (field[nh][nw] == '#') continue;

        // 移動先が探索済みの場合
        if (seen[nh][nw]) continue;

        // 再帰的に探索
        dfs(nh, nw);
    }
}

int main() {
    // 入力受け取り
    cin >> H >> W;
    field.resize(H);
    for (int h = 0; h < H; ++h) cin >> field[h];

    // s と g のマスを特定する
    int sh, sw, gh, gw;
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            if (field[h][w] == 's') sh = h, sw = w;
            if (field[h][w] == 'g') gh = h, gw = w;
        }
    }

    // 探索開始
    memset(seen, 0, sizeof(seen)); // seen 配列全体を false に初期化
    dfs(sh, sw);

    // 結果
    if (seen[gh][gw]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

グリッドグラフ　島の個数

[AOJ 島はいくつある？](https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jp)

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

// 入力
int H, W;
vector<vector<int>> field;

// 探索
void dfs(int h, int w) {
    field[h][w] = 0;

    // 八方向を探索
    for (int dh = -1; dh <= 1; ++dh) {
        for (int dw = -1; dw <= 1; ++dw) {
            int nh = h + dh, nw = w + dw;

            // 場外アウトしたり、0 だったりはスルー
            if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
            if (field[nh][nw] == 0) continue;

            // 再帰的に探索
            dfs(nh, nw);
        }
    }
}

int main() {
    // 入力受け取り
    while (cin >> W >> H) {
        if (H == 0 || W == 0) break;
        field.assign(H, vector<int>(W, 0));
        for (int h = 0; h < H; ++h) for (int w = 0; w < W; ++w) cin >> field[h][w];

        // 探索開始
        int count = 0;
        for (int h = 0; h < H; ++h) {
            for (int w = 0; w < W; ++w) {
                if (field[h][w] == 0) continue; // 残島じゃなかったらスルー
                dfs(h, w);
                ++count;
            }
        }
        cout << count << endl;
    }
}

木の直径

典型90問　003 - Longest Circular Road（★4

1-2-3-4-5
      |
      6-7-8

このtreeの直径は6

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

// 入力
int N;
int A[1 << 18], B[1 << 18];

// グラフ
const int INF = (1 << 29);
vector<int> G[1 << 18];
int dist[1 << 18];

void getdist(int start) {
	// 幅優先探索（BFS）により、最短距離を計算
	for (int i = 1; i <= N; i++) dist[i] = INF;

	queue<int> Q;
	Q.push(start);
	dist[start] = 0;

	while (!Q.empty()) {
		int pos = Q.front(); Q.pop();
		for (int to : G[pos]) {
			if (dist[to] == INF) {
				dist[to] = dist[pos] + 1;
				Q.push(to);
			}
		}
	}
}

int main() {
	// Step #1. 入力
	cin >> N;
	for (int i = 1; i <= N - 1; i++) {
		cin >> A[i] >> B[i];
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}

	// Step #2. 頂点 1 からの最短距離を求める
	// maxid1: 頂点 1 から最も離れている（最短距離が長い）頂点
	getdist(1);
	int maxn1 = -1, maxid1 = -1;
	for (int i = 1; i <= N; i++) {
		if (maxn1 < dist[i]) {
			maxn1 = dist[i];
			maxid1 = i;
		}
	}

	// Step #3. 頂点 maxid1 からの最短距離を求める
	// maxn2: 木の直径（最短距離の最大値）
	getdist(maxid1);
	int maxn2 = -1;
	for (int i = 1; i <= N; i++) {
		maxn2 = max(maxn2, dist[i]);
	}

	// Step #4. 出力
	cout << maxn2 + 1 << endl;
	return 0;
}

DFS (深さ優先探索) 超入門！から引用

類題
ATC A - 深さ優先探索
 ABC014 D - Black and White Tree
ABC019 D - 高橋くんと木の直径
 ABC204 C - Tour

DPを併用した解き方も頻出
ABC211 D - Number of Shortest paths

BFS(幅優先探索)

内容

引用
drkenさん BFS (幅優先探索) 超入門！

練習問題

DP(動的計画法)

内容

** DP実装の順序 **

Step1. DP 配列全体を「DP の種類に応じた初期値」で初期化
Step2. 初期条件を入力
Step3. ループを回す
Step4. テーブルから解を得て出力

// 無限大の値
const long long INF = 1LL << 60;

// DP テーブル
long long dp[100010];

// DP テーブル全体を初期化 (最小化問題なので INF に初期化)
for (int i = 0; i < 100010; ++i) dp[i] = INF;

// 初期条件
dp[0] = 0;

// ループ
for (int i = 0; i < N; ++i) {
    chmin(dp[なにか], dp[なにか] + なにか);
    ...
}

// 解を得て出力
cout << dp[N-1] << endl;

問題の種類	初期化する値	備考
最小化問題	INF
最大化問題	-INF	テーブル全体で $0$ 以上の値しかとらないことがわかっていれば $-1$ でもいいですし、$0$ でもいい場合もあります
数え上げ問題	$0$
確率問題	$0$
Yes/No 判定問題	False

Frog 2

[AtCoder Frog 2](https://atcoder.jp/contests/dp/tasks/dp_ｂ)

// dp[i]=INF と比較後dp[i]へ
chmin(dp[i + 1], dp[i] + abs(h[i] - h[i + 1]));
// 上の計算で出たdp[i]と比較後dp[i]
chmin(dp[i + 2], dp[i] + abs(h[i] - h[i + 2]));
...
chmin(dp[i + K], dp[i] + abs(h[i] - h[i + K]));

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

const long long INF = 1LL << 60;

// 入力
int N;
long long h[110000];

// DP テーブル
long long dp[110000];

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

    // 初期化 (最小化問題なので INF に初期化)
    for (int i = 0; i < 110000; ++i) dp[i] = INF;

    // 初期条件
    dp[0] = 0;

    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 1; j <= K; ++j) {
            chmin(dp[i + j], dp[i] + abs(h[i] - h[i + j]));
        }
    }

    // 答え
    cout << dp[N-1] << endl;
}

Vacation

AtCoder Vacation

dp[ i ][ 0 ] から dp[ i + 1 ][ 1 ] への遷移
dp[ i ][ 0 ] から dp[ i + 1 ][ 2 ] への遷移
dp[ i ][ 1 ] から dp[ i + 1 ][ 0 ] への遷移
dp[ i ][ 1 ] から dp[ i + 1 ][ 2 ] への遷移
dp[ i ][ 2 ] から dp[ i + 1 ][ 0 ] への遷移
dp[ i ][ 2 ] から dp[ i + 1 ][ 1 ] への遷移
これらから最大値を求める

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

// 入力
int N;
long long a[100010][3]; // a[i], b[i], c[i] をそれぞれまとめて a[i][0], a[i][1], a[i][2] にしてしまう

// DP テーブル
long long dp[100010][3];

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

    // 初期化は既に 0 に初期化される
    // 初期条件も既に 0 で OK

    // ループ
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                if (j == k) continue;
                chmax(dp[i + 1][k], dp[i][j] + a[i][k]);
            }
        }
    }

    // 答え
    long long res = 0;
    for (int j = 0; j < 3; ++j) chmax(res, dp[N][j]);
    cout << res << endl;
}

Knapsack 1

AtCoder Knapsack 1

ナップサック問題だからといってDPだと決めつけてはいけない
制約で変化する

今回は

#include <iostream>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
const long long INF = 1LL<<60;

const int MAX_N = 110;
const int MAX_V = 100100;

// 入力
int N;
long long W, weight[MAX_N], value[MAX_N]; // 品物の個数は 100 個なので少し余裕持たせてサイズ 110 に

// DPテーブル
long long dp[MAX_N][MAX_V];

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

    // 初期化
    for (int i = 0; i < MAX_N; ++i) for (int j = 0; j < MAX_V; ++j) dp[i][j] = INF;

    // 初期条件
    dp[0][0] = 0;

    // DPループ
    for (int i = 0; i < N; ++i) {
        for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {

            // i 番目の品物を選ぶ場合
            if (sum_v - value[i] >= 0) chmin(dp[i+1][sum_v], dp[i][sum_v - value[i]] + weight[i]);

            // i 番目の品物を選ばない場合
            chmin(dp[i+1][sum_v], dp[i][sum_v]);
        }
    }

    // 最適値の出力
    long long res = 0;
    for (int sum_v = 0; sum_v < MAX_V; ++sum_v) {
        if (dp[N][sum_v] <= W) res = sum_v;
    }
    cout << res << endl;
}

引用
drkenさん動的計画法超入門！

#便利で愉快な関数達
##注意
自作関数はmain関数よりも上部に記述しなければいけません。

実行にかかる時間を計測

内容

program.C++

int main() {
    // 例 1: 実行にかかる時間を計測する
    int ti = clock();
    for (int i = 1; i <= 100000; i++) cout << i << endl;
    printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
    return 0;
}

##進数変換

内容

program.C++

//binary=2進数

// 10進数->2進数
long long binary(long long deci){
    long long ans = 0;
    for (int i = 0; deci>0 ; i++){
        ans = ans+(deci%2)*pow(10,i);
        deci = deci/2;
    }
    return ans;
}
// K 進法表記の S を、10 進法表記で表す関数
long long BaseNumber(string s, long long k){
    long long ans = 0;
    for(char x:s){
        ans *= k;
        ans += x - '0';
    }
    return ans;
}

##素数判定

内容

program.C++

//引数Nが素数であればtrueを返す
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

##約数列挙

内容

program.C++

//Nの約数を全て配列に入れて返す
vector<long long> enum_divisors(long long N) {
    vector<long long> res;
    for (long long i = 1; i * i <= N; ++i) {
        if (N % i == 0) {
            res.push_back(i);
            // 重複しないならば i の相方である N/i も push
            if (N / i != i) res.push_back(N / i);
        }
    }
    // 小さい順に並び替える
    sort(res.begin(), res.end());
    return res;
}

##最大公約数、最小公倍数

内容

program.C++

// a と b の最大公約数を返す
long long GCD(long long a, long long b) {
    if (b == 0) return a;
    else return GCD(b, a % b);
}
//最小公倍数は最大公約数を用いて求めることができる。
long long LCM(long long a, long long b) {
    return a / GCD(a, b) * b;
}

##素因数分解

内容

program.C++

//Nの素因数を配列の中にpairを入れて返す
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数
        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        // その結果を push
        res.push_back({a, ex});
    }
    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}
int main() {
    //出力方法
    const auto &res = prime_factorize(10);
    for (auto p: res) for (int i = 0; i < p.second; ++i) cout << " " << p.first;
}

##互いに素の個数

内容

program.C++

//0からNまでNと互いに素になる「「個数」」を返す
vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0;
        while (N % a == 0) {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}
int main() {
    //出力方法
    const auto &res = prime_factorize(10);
    for (auto p: res) cout << p.first;
}

##等差級数

内容

(最初の数＋最後の数)×(最後の数-最初の数＋1)/2

例 100から500までの整数全ての和

program.C++

ans = (100 + 500) * (500 - 100 + 1) / 2

//overflow対策(あってるか知らない)
ans = ((100 + 500) / 2) * ((500 - 100 + 1) / 2)

##等比数列

内容

例 [3,6,12,24,48,...] 初項3 公比2

a_n = 3×2^{n-1}

program.C++

ans = 3*pow(2,n-1)

##階乗、順列、組み合わせ

内容

階乗は制約が厳しい場合使えない **20!**(正確な数字しらない)程度ですぐoverflowする

program.C++

long long facctorialMethod(int k){ //階乗の計算
    long long sum=1;
    for (int i = 1; i <= k; ++i) sum *= i;
    return sum;
}

long long permutation(int capacity,int division_count){ //順列 「P」
    long long ans=0, sum=0;
    ans = facctorialMethod(capacity);
    ans /= facctorialMethod(capacity-division_count);
    return ans;
}

long long combination(int capacity,int division_count){ //組み合わせ 「C」
    long long ans=0, sum=0;
    ans = facctorialMethod(capacity);
    ans /= facctorialMethod(division_count)*facctorialMethod(capacity-division_count);
    return ans;
}

##配列内から2つ取り出した値の絶対値和

内容

N <= 200000
ABC186 D問題
手順
・a={1,2,5}の時
・配列をソート(絶対値の関係をなくす為)
・|5-2|+|5-1|は5*2-3と同値

program.C++

//ソート済
ll ans=0,s=0;
for (int i = 0; i < N; i++){
  ans += (ll)a[i] * i
  ans -= s
  s += a[j]
}

##素集合データ構造(Union-find)

内容

program.C++

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

##再帰関数

内容

関数が関数を呼び出す。例：フィナボッチ数列

program.C++

int fact(int n){
  if (n == 0) return 1;
  return n * fact(n - 1);
}

後日更新予定

##あとがき
今回の競技プログラミングの学習において「けんちょん」さん(@drken )の記事がすごく参考になりました。
ありがとうございました！

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

[競技プログラミング] C++ チートシート 灰〜茶まで

まえがき

快適にするために

数値操作

数値の桁数, 数値切り抜き, 数値から文字へ

少数桁を切り上げ, 切り捨て

割り算の切り上げ, 四捨五入

追加と削除

文字取得

操作

vector

入出力

追加、削除、要素数

操作

多次元配列

vectorからsetへ

set

追加、削除、要素数

setからvectorへ

map

追加、削除、要素数

参照、検索

pair

追加、取得

配列を使う

priority_queue

stack

next_permutation

他に使える標準ライブラリ

入出力

入力

アルゴリズム

bit全探索

二分探索法

累積和

しゃくとり法(尺取り法)

DFS(深さ優先探索)

BFS(幅優先探索)

DP(動的計画法)

実行にかかる時間を計測

[競技プログラミング] C++ チートシート灰〜茶まで