LoginSignup
5
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ham_chick(ハムちっく)

アルゴリズム設計力向上委員会

Last updated at Posted at 2023-11-17

はじめに

本記事はC++をターゲットにしています。
そしてかなり内向的です。

自分のアルゴリズム構築力を向上させるための取り組みの一環として執筆します。
目標と〇〇はあった方がいいということで、AtCoder水色を第一目標に定めます。

ルール

  • 何かを学んで理解したら、自分の言葉で記事に書くこと！

チェックリスト

必修の標準ライブラリ

※標準テンプレートライブラリ、STL（Standard Template Library）　ともいう

項目名 include 1回でもさらえば〇つける 理解できれば〇つける
abs 〇
sin/cos/tan
string 〇
min/max
swap
__gcd
rand
clock
reverse
sort algorithm 〇
vector vector 〇
stack
queue queue 〇
deque deque
priority_queue queue 〇
map map 〇
lower_bound 〇
set set 〇
pair
tuple
assert
count algorithm 〇
find
next_permutation algorithm 〇
__builtin_popcount
bitset bitset 〇

アルゴリズム（12 個）

項目名 1回でもさらえば〇つける 理解できれば〇つける
全探索（bit 全探索、順列全探索を含む）
二分探索 〇
深さ優先探索（DFS） 〇
幅優先探索（BFS） 〇
動的計画法（bitDP などを含む） △
ダイクストラ法（最短経路問題）
ワーシャルフロイド法（最短経路問題）
クラスカル法（最小全域木問題）
高速な素数判定法
べき乗を高速に計算するアルゴリズム
(繰り返し二乗法)
逆元を計算するアルゴリズム
累積和 〇

データ構造（3 個）

項目 1回でもさらえば〇つける 理解できれば〇つける
グラフ（グラフ理論）
木 〇
Union-Find 〇

その他

項目 1回でもさらえば〇つける 理解できれば〇つける
ベル数

テクニック的な話

厳密に「何をどこに書くか」をまだ定義できていませんが
「実装の形がある程度決まっているもの」をこの章に記載していきます。

ソート

N個の整数の配列Aをソートするとする。

まず、std::sort()を使うために#include <algorithm>する。

単純なソート

std::sort(a, a + N);

大きい順にソートしたいときは

std::sort(a, a + N, std::greater<int>());

クラスのソート

自作クラスのvector（や配列）をあるプロパティの値でソートしたい場合、以下の手順で行う。

  1. 自作クラスにソート用のoperator<を用意する（降順ソートしたい場合はoperator>を用意する）
  2. ソート実行

std::sortする時に（暗黙的に）呼ばれたstd::lessがoperator<を利用して比較を実行するらしい。

（例）

#include <iostream>
#include <vector>
#include <algorithm>

struct marchandice {
    long long T, D, T_out;
    bool operator<(const marchandice& another) const
    {
        return T < another.T; //Tをキーとしてソートする
    }
};

int main()
{
    int N;
    std::cin >> N;
    std::vector<marchandice> goods(N);
    long long max_time = 0;
    for (int i = 0; i < N; i++) {
        std::cin >> goods[i].T >> goods[i].D;
        goods[i].T_out = goods[i].T + goods[i].D;
        max_time = std::max(max_time, goods[i].T_out);
    }
    std::sort(goods.begin(), goods.end());
}

バケット法

入力配列の各要素がとりうる値の数だけの配列を用意し、それぞれの数をカウントしていく方法。

N個の整数の配列Aがあり、$1 \leqq N \leqq 1000$、$1　\leqq　A[i] \leqq 100$の場合。

int bucket[100] = {0}; //バケット
for(int i=0; i<N; i++){
    bucket[A[i]-1]++;
}

用意するバケットの個数と代入時のインデックスに注意
今回は1, 2, ・・・, 99, 100の100個の値を格納するのでバケットを１００個用意し、
０は出現しない想定なのでA[0]に1のカウントを格納するようにbucket[A[i]-1]++;とする。

例えば、$A={8, 10, 8, 6}$で与えられた時、bucket[5]=1, bucket[7]=2, bucket[9]=1となり、それ以外のbucket[x]の値は全て0になる。

連想配列（ハッシュともいう）

好きな名前を添字にできる配列。
（添字から中身を連想できるから連想配列、と一旦納得しておく）

連想配列で使われる添字は「キー」と呼ばれる。

ハッシュテーブルの考え方で連想配列を実現することができますが、連想配列を実現するためには必ずハッシュテーブルが必要なわけではありません。
必ずしも「連想配列＝ハッシュテーブル」ではありませんのでご注意ください。

std::set
std::map

二分探索

データが順番に並んでいるときに使える。
（例：データが昇順に並んでいる前提）

  1. (残っているデータの中から)中央のデータを取り出す
  2. 取り出したデータが目的のデータに合致するかを調べる。
    1. 取り出したデータが目的のデータよりも小さかったら、取り出したデータより小さいデータは以降無視する
    2. 取り出したデータが目的のデータよりも大きかったら、取り出したデータより大きいデータは以降無視する

を繰り返していく方法。

では実際にC++で実装する場合を見ていこう。

＜例題＞

#include <iostream>
#include <vector>
#include <algorithm>

//int main() {
//	int N, K;
//	std::cin >> N >> K;
//	std::vector<int> A(N);
//	for (int n = 0; n < N; n++) std::cin >> A[n];
//	auto itr = std::lower_bound(begin(A), end(A), K);
//	if (itr == end(A)) std::cout << -1 << std::endl;
//	else std::cout << (itr - begin(A)) << std::endl;
//}

int main() {
	int N, K;
	std::cin >> N >> K;
	std::vector<int> A(N);
	for (int n = 0; n < N; n++) std::cin >> A[n];
	
	//ギリギリあり得ない値を入れておく
	int lower = -1;
	int upper = N;
	while ((lower + 1) < upper) {
		int tmp = (lower + upper) / 2;
		if (A[tmp] < K) lower = tmp;
		else upper = tmp; //正解は「lowerより大きく」、「upper以下」となるように更新条件を設定することに注意！
	}
	std::cout << (upper < N ? upper : -1) << std::endl;
}

upperとlowerを用意し、その（ほぼ）真ん中が条件を満たすかどうかを判定していく。
答えが決定するまで両者をじりじり寄せていくイメージ。

単純な2分探索の際に使えるSTL

２分探索を行う標準ライブラリは複数あるので、どれを使うかは問題によって切り替える。

メソッド 特徴
std::binary_search()
std::lower_bound()
std::upper_bound()

データ探索

std::vector vの中に目的のデータがあるか探したいとする。
vがソートされているならstd::binary_search()も使えるし、
ソートされていなくてもstd::count()で戻り値retが$0 < ret$かを確認することで目的は達成できる。

深さ優先探索（DFS）

これ以上進めなくなるまで掘り進め、行き止まりになったら1つ戻って別の道を掘り進める。
（概念としては何となく分かるが、実装するとなると難しいイメージ。。）

再帰関数とスタック（FILO）をよく使って実装するらしい。

Wikipediaさんに疑似コードという形で載っていた。
実装方法は一般的に決まった形式があるのかな。。

再帰関数版

function 深さ優先探索(v)
   v に訪問済みの印を付ける
   v を処理する
   for each v に接続している頂点 i do
       if i が未訪問 then
           深さ優先探索(i)

スタック版

function 深さ優先探索(v)
   S ← 空のスタック
   v に訪問済みの印を付ける
   v を S に積む
   while S が空ではない do
       v ← S から取り出す
       v を処理する
       for each v に接続している頂点 i do
           if i が未訪問 then
               i に訪問済みの印を付ける
               i を S に積む

幅優先探索（BFS）

Wikipediaさんにも以下の記述があるということは、BFSの実装方法は一般的に決まった形式があるのかな。。

  1. 根ノードを空のキューに加える。

  2. ノードをキューの先頭から取り出し、以下の処理を行う。
    - ノードが探索対象であれば、探索をやめ結果を返す。
    - そうでない場合、ノードの子で未探索のものを全てキューに追加する。

  3. もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ"not found"と結果を返す。

  4. ②に戻る。

「ノードが探索対象であれば、探索をやめ結果を返す。」だけまだ意味わからん。。

幅優先探索の問題と自作コード。

問題はこちら

https://atcoder.jp/contests/abc325/tasks/abc325_c

#include <iostream>
#include <vector>
#include <math.h>
#include <tuple>
#include <queue>


int dx[3] = { -1, 0, 1 };
int dy[3] = { -1, 0, 1 };

int main() {
    int H, W;
    std::cin >> H >> W;
    std::vector < std::string> S(H);
    std::vector<std::vector<bool>> Checked(H, std::vector<bool>(W, false));

    for (int i = 0; i < H; i++) {
        std::cin >> S[i];
        //Checkedの初期化できてますよね？
    }

    int ret_count = 0;
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            if (S[h][w] != '#') {
                continue;
            }
            if (Checked[h][w] != false) {
                continue;
            }

            ret_count++;

            std::queue<std::pair<int, int>> q;
            q.push({ h, w });
            while (0 < q.size()) {
                std::pair<int, int> tmp = q.front();
                q.pop();

                int tmp_h, tmp_w;
                for (auto x : dx) {
                    for (auto y : dy) {
                        if ((x == 0) && (y == 0)) {
                            continue;
                        }
                        tmp_h = tmp.first + x;
                        tmp_w = tmp.second + y;
                        if ((tmp_h < 0) || (H <= tmp_h)) {
                            continue;
                        }
                        if ((tmp_w < 0) || (W <= tmp_w)) {
                            continue;
                        }
                        if ((S[tmp_h][tmp_w] == '#') && (Checked[tmp_h][tmp_w] == false)) {
                            Checked[tmp_h][tmp_w] = true;
                            q.push({ tmp_h, tmp_w });
                        }
                    }
                }
            }
        }
    }
    std::cout << ret_count << std::endl;
}

動的計画法（DP）

ある問題を一連の部分問題へと分解し、
それぞれの部分問題の解をメモ化しながら、
小さな部分問題からより大きな部分問題の解を順に求めていく手法を総称して「動的計画法」という。

偉い人曰く、
重要なのは"「ここまでの経路は違っても、ここから先は同じなもの」をまとめてあげることで計算を省略できる！"ということ

個人的には
「問題の途中地点（通過点、、？）に着目」して、「順番に」解いていく点がポイントかなと思った。

すごろく問題と動的計画法
問題はこちら https://algo-method.com/tasks/323 
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<int> D(M, 0);
    for (int m = 0; m < M; m++) std::cin >> D[m];
    std::sort(D.begin(), D.end());
    std::vector<bool> dp(N+1, false);
    dp[0] = true; //最初からマス０（=start）には居るので
    for (int n = 1; n <= N; n++) {
        for (int m = 0; m < M; m++) {
            if ((0 <= (n - D[m])) && ((n - D[m]) <= N) && (dp[n-D[m]] == true)) {
                dp[n] = true;
                break;
            }
            else {

            }
        }
    }
    if (dp[N] == true) {
        std::cout << "Yes" << std::endl;
    }
    else {
        std::cout << "No" << std::endl;
    }
}

DPの御三家（配るDP/貰うDP/メモ化再帰）
配るDP i番目に着目した時、i+n番目に更新をかけるdp
※nは１つとは限らない
貰うDP i番目に着目した時、i-n番目からデータを持ってきてi番目を計算するdp
※nは１つとは限らない
メモ化再帰 DPの結果をメモしながら再帰的に実施するdp
実装が面倒くさくなりがちだが、「DP の更新順序が自明でない」時には効果絶大！

下記の例題をそれぞれのDPで解いてみる。

#include <iostream>
#include <vector>

#define INF (1LL<<30)

//配るDP版
int main() {
	int N, K;
	std::cin >> N >> K;
	std::vector<int> H(N);
	for (int n = 0; n < N; n++) std::cin >> H[n];

	std::vector<long long> cost(N, INF);
	cost[0] = 0;
	for (int n = 0; n < N; n++) {
		for (int k = 1; k <= K; k++) {
			if ((n + k) < N) cost[n + k] = std::min(cost[n + k], cost[n] + abs(H[n + k] - H[n]));
		}
	}
	std::cout << cost[N - 1] << std::endl;
}

//貰うDP版
int main() {
	int N, K;
	std::cin >> N >> K;
	std::vector<int> H(N);
	for (int n = 0; n < N; n++) std::cin >> H[n];

	std::vector<long long> cost(N, INF);
	cost[0] = 0; //足場１には初めからいるのでノーコスト
	for (int n = 1; n < N; n++) {
		for (int k = 1; k <= K; k++) {
			if ((n - k) < 0) continue;
			cost[n] = std::min(cost[n], cost[n - k] + abs(H[n - k] - H[n]));
		}
	}
	std::cout << cost[N - 1] << std::endl;
}

//メモ化再帰版
int main() {
	int N, K;
	std::cin >> N >> K;
	std::vector<int> H(N);
	for (int n = 0; n < N; n++) std::cin >> H[n];

	std::vector<long long> cost(N, INF);

	auto recursive_func = [&](auto self, int n) -> long long {
		if (cost[n] != INF) return cost[n]; //既に DP の値が更新されていたらそのままリターン（同じ計算は2度以上しない）
		if (n == 0) return 0LL; //足場１には初めからいるのでノーコスト

		long long res = INF;
		for (int k = 1; k <= K; k++) {
			if (((n - k) < N) && (0 <= (n - k))) {
				res = std::min(res, self(self, n - k) + abs(H[n - k] - H[n]));
			}
		}
		return cost[n] = res; // DP の結果をcostにメモしながらリターン（鮮やか。。）
	};

	std::cout << recursive_func(recursive_func, N - 1) << std::endl;
}

第4の型 入れ替えDP

オブジェクトとswap関数を上手に使って、直前の状態を保持する。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <atcoder/all>
#include <unordered_set>

#define INF (1LL<<30)

int main() {
    int N, x, y;
    std::cin >> N >> x >> y;
    std::vector<int> A(N);
    for (int n = 0; n < N; n++) std::cin >> A[n];

    x -= A[0];//Xの1発目は正方向と決まっているので、x - A[0]をして調整しておく

    std::vector<int> Ax, Ay;
    for (int n = 1; n < N; n++) { //A[0]は無視することに注意！
        if (n % 2 == 0) Ax.push_back(A[n]);
        else Ay.push_back(A[n]);
    }

    //DPの関数。直前の状態が分かっていればそれまでの経路はどうでもよい。（重複を防ぐためにunorderd_setを使うのも合理的）
    auto f = [](int x, std::vector<int> a) -> bool {
        std::unordered_set<int> last;//Lastの値を次のループへ伝搬する
        last.insert(0);
        for (int i = 0; i < a.size(); i++) {
            std::unordered_set<int> tmp;
            std::swap(last, tmp); //ここでtmpにLastの値が入る
            for (int j : tmp) {
                last.insert(j + a[i]); //前回の値に足した場合の数を次のループへ伝番
                last.insert(j - a[i]); //前回の値から引いた場合の数を次のループへ伝番
            }

        }
        return last.count(x); //最終的にxにたどり着けるかどうかのBoolをreturnする（0：False、0以外：True）
    };

    bool isOkX = f(x, Ax); 
    bool isOkY = f(y, Ay);

    if (isOkX && isOkY) std::cout << "Yes" << std::endl;
    else std::cout << "No" << std::endl;

}

bitDP

bitDPを理解していくにあたって、有名な巡回セールスマン問題を取り上げます。
bitDPの解説もこの問題を例に記載しますので、問題に目を通してから読み進めてください。

ポイントはdpテーブルを使うということ。

dpテーブルなるものを使います。そういうものなんだ。黙って飲み込みなさい。

dpテーブルは2次元配列の形をしており、
各行（１つめの添え字）が、これまでに訪れた都市の集合
各列（２つめの添え字）が、これまでに訪れた都市のうち最後に訪れた都市
を表す。
image.png
「これまでに訪れた都市の集合」を表すために２進数表記（0と1のビット列）を使い、訪問済みかどうかの判断にビットシフトとビット演算を使う。

集合の表記

10進数 2進数（ビット列） 集合 集合の意味
0 000 {} どの都市にも訪れていない（？）
1 001 {0} 都市0のみ訪問済み（？）
2 010 {1} 都市1のみ訪問済み
3 011 {0, 1} 都市0,1のみ訪問済み
4 100 {2} 都市2のみ訪問済み
5 101 {0, 2} 都市0,2のみ訪問済み
6 110 {1, 2} 都市1,2のみ訪問済み
7 111 {0, 1, 2} 都市0,1,2のみ訪問済み

都市0は出発地点（セールスマンの拠点がある都市）

訪問済みかどうかの判定

都市iに訪問済みかどうかを判定するには集合sのi番目にビットが立っているかを判定すればOK
具体的にはsをiビット分だけ右シフトして1（=001）とのANDをとり、結果が1（=001）であれば訪問済み
（例）s=5={101}、i=1

s = 5;
i = 1;
if(((s >> i) & 1) == 1){
    //都市iに訪問済み
}
else{
    //都市iには未訪問
}

訪問後の集合の作成

1をiビット分だけ左シフトして集合sとのORをとると、集合sの状態から都市iに移動した後の集合が得られる
(例) s=3={011}、i=2

s = 3;
i = 2;
int s_after = (s | (1 << i));
上記巡回セールスマン問題の解答コードはこちら

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_2_A

//#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
#define INF (1LL << 30)

int main() {
    int V, E;
    std::cin >> V >> E;
    /*
    ある都市からある都市までの距離を格納するグリッド
    第一の添え字⇒出発地
    第二の添え字⇒目的地
    */
    std::vector<std::vector<int>> dist(V, std::vector<int>(V, INF)); //最短経路を求める問題なので(V, INF)として、通らない経路が答えにならないようにする。
    for (int e = 0; e < E; e++) {
        int s, t, d;
        std::cin >> s >> t >> d;
        dist[s][t] = d;
    }

    /*
    第一の添え字⇒訪れた都市の'集合'
    第二の添え字⇒最後に訪れた都市
    (例)dp[14][2]：都市1,2,3には既に訪問済みで、最も後に訪問したのは都市2である状態。
                   ※0d14＝0b1110
                    都市0にだけ訪れたことがある場合：{0}　→ 0001
                    都市1と3にだけ訪れたことがある場合：{1,3}　→ 1010
                    都市0,1,2,3にだけ訪れたことがある場合：{0,1,2,3} → 1111
    */
    std::vector<std::vector<int>> dp((1 << V), std::vector<int>(V, INF)); //〇〇なので(1 << V)。〇〇なので(V, INF)。
    dp[0][0] = 0; //〇〇のため。
    for (int i = 0; i < (1 << V); i++) { //iはn個の都市の部分集合を2進数で表現
        for (int j = 0; j < V; ++j) { //jは最後に訪れた都市
            if (((i & (1 << j)) == 0) && (i != 0)) { //jに訪れていなかったらスキップ
                continue;
            }
            for (int k = 0; k < V; ++k) { //kは
                // 集合i（今まで訪れた都市）のうち、kに訪れていない、かつjからkへの経路が存在するとき
                if (((i & (1 << k)) == 0) && (dist[j][k] < INF)) {
                    int v = (i | (1 << k)); //dp[集合iにkを追加した集合][k]の値を更新する準備
                    dp[v][k] = std::min(dp[v][k], dp[i][j] + dist[j][k]); //dp[集合i（今まで訪れた都市）][j]にjからkへの経路を足した値に更新する
                }
            }
        }
    }

    std::cout << ((dp[(1 << V) - 1][0] == INF) ? -1 : dp[(1 << V) - 1][0]) << std::endl;
}

とはいえ勉強中。まだまだ演習して慣れるべし。

これが基本形？

	vector<vector<int>> dp((1 << n), vector<int>(n, INF));
	dp[0][0] = 0;
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			if (((i & (1 << j)) == 0)&&(i != 0)) {
				continue;
			}
			for (int k = 0; k < n; ++k) {
				if ((i & (1 << k)) == 0) {
					int v = (i | (1 << k));
					dp[v][k] = min(dp[v][k], dp[i][j] + dist[j][k]);
				}
			}
		}
	}

部分列DP

LCS DP

1つ目の文字列のs番目の文字と、もう一つの文字列のt番目の文字まででできる部分列の長さの最大値をDPする
※LCS＝Longest Common Subsequence（最長共通部分列）
2つのインデックスを使う事と、DPの遷移の仕方（左から遷移するor上から遷移するor左上から遷移する）を考えるのが特徴。

例題

例題の解答はこちら
#include <iostream>
#include <vector>
#include <stack>

int main() {
	std::string S, T;
	std::cin >> S >> T;

	//Sのs番目の文字までとTのt番目の文字までで出来る部分列の長さの最大値をdpする
	std::vector<std::vector<int>> dp(S.size() + 1, std::vector<int>(T.size() + 1, 0));
	for (int s = 0; s < S.size(); s++) {
		for (int t = 0; t < T.size(); t++) {
			dp[s + 1][t + 1] = std::max(dp[s + 1][t + 1], dp[s][t + 1]); //文字列Sだけを１文字進めてdp[s+1][t+1]にたどりつくパターン
			dp[s + 1][t + 1] = std::max(dp[s + 1][t + 1], dp[s + 1][t]); //文字列Tだけを１文字進めてdp[s+1][t+1]にたどりつくパターン
			if (S[s] == T[t]) dp[s + 1][t + 1] = std::max(dp[s + 1][t + 1], dp[s][t] + 1); //文字列Sと文字列Tを１文字進めてdp[s+1][t+1]にたどりつくパターン
		}
	}
	
	/*
	* 余談だが、LCSの長さはこの段階で dp[S.size()][T.size()] に格納されている。
	* ※LCS＝Longest Common Subsequence（最長共通部分列）
	*/
	
	std::stack<char> ans;
	int s = S.size();
	int t = T.size();
	while ((0 < s) && (0 < t)) { // SとTのどちらかをたどり終わったら終了
		if (dp[s][t] == dp[s - 1][t]) s--; //(s-1,t)→(s,t)と更新されていたパターン。文字はマッチしてないのでDPを遡る処理のみ
		else if (dp[s][t] == dp[s][t - 1]) t--; //(s,t-1)→(s,t)と更新されていたパターン。文字はマッチしてないのでDPを遡る処理のみ
		else {
			//(s-1,t-1)→(s,t)と更新されていたパターン。文字を答えに追加し、DPを遡る
			ans.push(S[s - 1]);
			s--; t--;
		}
	}
	while (0 < ans.size()) {
		std::cout << ans.top(); 
		ans.pop();
	}
	std::cout << " " << std::endl;
}

桁DP

耳DP

実家DP

確率DP

コード
#include <iostream>
#include <vector>
#include <iomanip>

int main() {
	int N;
	std::cin >> N;
	std::vector<double> P(N);
	for (int n = 0; n < N; n++) std::cin >> P[n];

	//i番目までのコインのうち、n枚以上が表になる確率のdp。
	//i番目とそのうち表の枚数を状態としてもてばいける？

	//メモ化再帰版
	std::vector<std::vector<double>> dp(N, std::vector<double>(N + 1, -1));
	dp[0][0] = (1 - P[0]);
	dp[0][1] = P[0];
	auto recursive_func = [&](auto self, int n, int omote_cnt) -> double {
		if (dp[n][omote_cnt] != -1) return dp[n][omote_cnt];

		double res = 0;
		if (((omote_cnt - 1) <= n) && (0 <= (n - 1)) && (0 <= (omote_cnt - 1))) {
			res += self(self, n - 1, omote_cnt - 1) * P[n]; //表が出て、dp[n][omote_cnt]に来るとき
		}
		if (((omote_cnt - 1) <= n) && (0 <= (n - 1))) {
			res += self(self, n - 1, omote_cnt) * (1 - P[n]); //裏が出て、dp[n][omote_cnt]に来るとき
		}
		return dp[n][omote_cnt] = res;
	};
	double ans = 0;
	for (int omote_cnt = 0; omote_cnt <= N; omote_cnt++) {
		if (((N + 1) / 2) <= omote_cnt) {
			ans += recursive_func(recursive_func, N - 1, omote_cnt);
		}
	}
	std::cout << std::fixed << std::setprecision(10) << ans << std::endl;

	////貰うdp版
	//std::vector<std::vector<double>> dp(N, std::vector<double>(N + 1, 0));
	//dp[0][0] = (1 - P[0]);
	//dp[0][1] = P[0];
	//for (int n = 1; n < N; n++) {
	//	for (int omote_cnt = 0; omote_cnt < N; omote_cnt++) {
	//		if (n < (omote_cnt - 1)) continue;

	//		//表の時
	//		dp[n][omote_cnt + 1] += dp[n - 1][omote_cnt] * P[n];
	//		//裏の時
	//		dp[n][omote_cnt] += dp[n - 1][omote_cnt] * (1 - P[n]);
	//	}
	//}
	//double ans = 0.0;
	//for (int omote_cnt = 0; omote_cnt <= N; omote_cnt++) if (((N + 1) / 2) <= omote_cnt) ans += dp[N - 1][omote_cnt];
	//std::cout << std::fixed << std::setprecision(10) << ans << std::endl;
}

期待値DP

コード

ダイクストラ法（最短経路問題）

負の重み（辺）を含まない重み付きグラフの単一始点最短経路問題に対して使われる。
始点からの最短経路長が既に確定した点からの経路同士を比較し、
優先度付きキューを使って経路が最短の点を処理していく点がポイント。

  1. 優先度付きキュー（priority_queue）を用意し、始点の情報とそこへの最短経路をpushする。（この時、最短距離順で情報がソートされるようにすることに注意）
  2. キューが空になるまで、次の操作を繰り返す。
    1. キューの先頭要素（距離の一番小さいもの）を取り出す
    2. 取り出した最短経路長が、既に計算済みの最短経路長より長ければcontinue
    3. そこから移動できる頂点を走査し、最短経路長が更新できるものがあれば、距離を更新し、「その頂点への距離」「頂点の情報」をキューにpushする
例題

https://atcoder.jp/contests/abc340/tasks/abc340_d

#include <iostream>
#include <vector>
#include <queue>

#define INF (1LL<<60)

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b; 
		return true;
	}
	else return false;
}

struct Edge {
	int point_to;
	long long cost;

	bool operator<(const Edge& another) const 
	{
		return cost < another.cost;
	}
};

int main() {
	int N;
	std::cin >> N;
	std::vector<long long> A(N), B(N), X(N);
	std::vector<std::vector<Edge>> Graph(N);

	for (int n = 0; n < (N - 1); n++) {
		int a, b, x;
		std::cin >> a >> b >> x;
		x--;
		A[n] = a;
		B[n] = b;
		X[n] = x;

		Edge e_a, e_b;
		// 「Ai 秒掛けてステージ i をクリアする。ステージ i + 1 を遊べるようになる」
		e_a.point_to = n + 1; e_a.cost = a;
		Graph[n].push_back(e_a);
		//「Bi 秒掛けてステージ i をクリアする。ステージ Xi を遊べるようになる。」
		e_b.point_to = x; e_b.cost = b;
		Graph[n].push_back(e_b);
	}

	std::vector<long long> dp(N, INF); //始点から各頂点までの最短経路長を格納するテーブル
	std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> pq; //経路が短い順にソートしたいため、「first：距離、second：頂点」とする。
	dp[0] = 0; //始点から始点は距離ゼロ
	pq.push({ 0, 0 }); //始点から始点は距離ゼロ
	while (0 < pq.size()) {
		std::pair<long long, int> tmp = pq.top(); pq.pop();
		if (dp[tmp.second] < tmp.first) continue; //最短ではない経路でこの点にたどりついているので破棄
		for (auto edge : Graph[tmp.second]) {
			long long cost_new = dp[tmp.second] + edge.cost;
			if (chmin(dp[edge.point_to], cost_new) == true) {
				pq.push({ cost_new, edge.point_to });
			}
		}
	}

	std::cout << dp[N - 1] << std::endl;
}

ベルマンフォード法

重み付きグラフの単一始点最短経路問題に対して、おもに負の重み（辺）があるときに使われる。
T.B.D.

ワーシャルフロイド法

実装が非常に簡単。
T.B.D.

累積和

長さ$N$の数列$A（a_0,a_1,・・・,a_{n-1}）$に対して、$A$の累積和の数列$S（s_0,s_1,s_2,・・・,s_n　※s_{i+1}=s_i+a_i）$を計算しておく方法。
image.png
※$S$のサイズは$A$のサイズよりも1大きいことに注意！
（累積差とか累積積とか和じゃない問題にも応用できそうね！）

C++での実装の基本形は以下。

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] = 0 になる
for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i];

計算量についての考え方が根底にありそう。

累積和（＋ソート、二分探索）の問題

https://atcoder.jp/contests/abc334/tasks/abc334_d

#include <iostream>
#include <vector>
#include <algorithm>

// [初期アイデア]
// Rを小さい順にソート
// RRを合計値にする
// 例）　RR[0]＝R[0]、RR[1]＝RR[0]＋R[1]、RR[2]＝RR[1]＋R[2]
// RR[i]＜＝x＜RR[i+1]となるiをみつける　（二分探索）
// i+1が答え

int main()
{
    int N, Q;
    std::cin >> N >> Q;
    std::vector<long> R(N,0);
    std::vector<long> RR(N,0);
    for (int i = 0; i < N; i++) {
        std::cin >> R[i];
    }

    std::sort(R.begin(), R.end());

    for (int i = 0; i < N; i++) {
        RR[i] += R[i];
        if (0 < i) {
            RR[i] += RR[i - 1];
        }
    }

    long X;
    for (int i = 0; i < Q; i++) {
        std::cin >> X;
        auto Iter = std::upper_bound(RR.begin(), RR.end(), X);
        std::cout << (Iter - RR.begin()) << std::endl;
    }
}

多次元の累積和（T.B.D.）

尺取り法

長さ$n$の数列$a_0,a_1,・・・,a_{n-1}$において
条件を満たす区間（連続する部分列）を全て求めることが出来る方法。

以下のような問題への解法として活用できる。

  • 「条件」を満たす区間のうち、最小の長さを求めよ
  • 「条件」を満たす区間のうち、最大の長さを求めよ
  • 「条件」を満たす区間を数え上げよ

これらの問題は愚直に全探索すると$O(n^2)$の計算量が必要になる（$n(n+1)/2$個の区間が存在するため）が、
尺取り法だと$O(n)$で済む。

「条件」は何でもいいわけではなく、以下のいずれかの構造になっている場合に尺取り法を適用できる。

  • 区間[left,right)が「条件」を満たすなら、それに含まれる区間も「条件」を満たす
  • 区間[left,right)が「条件」を満たすなら、それを含む区間も「条件」を満たす

尺取り法に限らず、区間を考えるときは半開区間[i,j)で考えるようにする方がいい。
※世の中の「区間」を扱う標準ライブラリの多くは半開区間で設計されているため。
例）　長さ$n$の数列A（$a_0,a_1,・・・,a_{n-1}$）において、A[3,6)
　　　　⇒$a_3,a_4,a_5$を指し、$a_6$は含まない
例）　std::sort(A,A+n);は$A[0]～A[n-1]$をソートするが、$A[n]$はソートしない。
　　　　（そもそもA[n]は範囲外指定例外が飛びそうですよね）

実装の基本形

int right = 0;     
for (int left = 0; left < n; ++left) {
    while (right < n && (right を 1 個進めたときに条件を満たす)) {
        /* 実際に right を 1 進める */
        // ex: sum += a[right];
        ++right;
    }

    /* break した状態で right は条件を満たす最大なので、何かする */
    // ex: res += (right - left);

    /* left をインクリメントする準備 */
    // ex: if (right == left) ++right;
    // ex: else sum -= a[left];
}

尺取り法の概念（アイデア、イメージ）

TBD

imos法（いもすほう）

「加算する値を一番手前だけメモしておき、全部メモし終わってから一気に数え上げる」という手法。
もちろん、加算する値は負数でもOK。

木

グラフ理論でいう木とは

  • サイクルがない
  • 連結構造（＝途中で途切れない）
  • 葉と辺で構成される
  • 葉は次数が１（繋がっている辺が１本のみ）の成分のこと
  • 根
  • 根と頂点$v$とを結ぶパスの長さを、「頂点$v$の深さ」という
  • 「木の高さ」＝各頂点の深さの最大値

再帰関数を使って木を探索するアルゴリズムを作成した際に
再起関数が呼び出される順番⇒行きがけ順
再起関数から抜ける順番⇒帰りがけ順
となる（？、反例ありそう。未検証）

辺の情報を入力として受け取る場合
#include <iostream>
#include<vector>

struct TreeNode {
    std::vector<int> Children;
    bool IsVisited = false;
};

std::vector<TreeNode> _Tree;

int main()
{
    int N;
    std::cin >> N;
    _Tree.resize(N, TreeNode());
    for (int i = 0; i < (N-1); i++) { //N個の頂点を持つ木の辺の数はN-1個
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        _Tree[u].Children.push_back(v);
        _Tree[v].Children.push_back(u);
    }
}
頂点の情報を入力として受け取る場合
木と深さ優先探索の問題

問題はこちら

https://atcoder.jp/contests/abc333/tasks/abc333_d

#include <iostream>
#include<vector>

struct TreeNode {
    std::vector<int> Children;
    bool IsVisited = false;
};

std::vector<TreeNode> _Tree;

// あるノードを根とした部分木の大きさを返す。
int dfs(int node_index, int tmp_count) {
    _Tree[node_index].IsVisited = true;
    tmp_count++; // カウントアップ
    for (auto p : _Tree[node_index].Children) {
        if (p != 0) {
            if (_Tree[p].IsVisited == false) {
                tmp_count = dfs(p, tmp_count);
            }
        }
    }
    return tmp_count;
}

int main()
{
    int N;
    std::cin >> N;
    _Tree.resize(N, TreeNode());
    for (int i = 0; i < (N-1); i++) { //N個の頂点を持つ木の辺の数はN-1個
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        _Tree[u].Children.push_back(v);
        _Tree[v].Children.push_back(u);
    }

    /*
    問題のポイント
    頂点1を消すことが出来る＝頂点１に繋がっている部分木のうち、大きさが最大でないものを全部消した状態
    ⇒答え = 全頂点数 - 最大の部分木の大きさ
    */
    int max_subtree_size = 0;
    for (int i = 0; i < _Tree[0].Children.size(); i++) { //「頂点１」と繋がっている部分木に着目
        max_subtree_size = std::max(dfs(_Tree[0].Children[i], 0), max_subtree_size);
    }
    std::cout << (N - max_subtree_size) << std::endl;
}

Segment Tree

セグメント木の特徴。

  • セグメント木は基本的に「構築」「更新」「検索」の3段階からなることが多い。

基本的にAtCoder Library（ACL）のsegtreeを使って問題は解く。
事前準備 ①問題に合わせてopを定義
②問題とopに合わせて単位元eを定義
コンストラクタ segtree<型, op, e> S(A);
更新（$A[p]$にxを代入） S.set(p, x)
検索（$A[p]$の値を取得） S.get(p)
区間$[l,r)$に対してopを実行した時の結果を取得する（例：opがminを求める関数の場合は区間最小値が取得できる） S.prod(l, r)
全区間に対してopを実行した時の結果を取得する（例：opがminを求める関数の場合は区間最小値が取得できる） S.all_prod()
segtree上で二分探索をし、関数fが真となる最大のrを返す（？） S.max_right(l, f)
segtree上で二分探索をし、関数fが真となる最小のlを返す（？） S.min_left(r, f)

（例）
オペレータop、単位元e、int型の配列$A$を元にしたsegtree$S$を作りたいとき

segtree<int, op, e> S(A);

ACLは問題に集中するためのライブラリで、「その中身を詳しく知らなくても基本的な使い方を知ってれば扱える」ことを目指して作られたものらしい。

オープンソース？なので中身を見たければ見れるので、重要点だけさらったらOKということにしておく。

Segment Treeについてもっと詳しく知りたいときはこちら
/*
* セグメント木（0-indexed）について
* 横幅（＝最下段の個数）をN、自分のいるNodeのIndexをiとすると、
* 【セグメント木全体のサイズ（＝全Nodeの個数）】：(2^n)-1個
* 【「親⇒子」への移動】：i*2+1 と i*2+2
* 【「子⇒親」への移動】：(i-1)/2 ※少数切り捨て
*/
#include <vector>

// template <class S, S (*op)(S, S), S (*e)()> struct SegmentTree{
class  SegmentTree{
    int n; //最下段の長さ
    vector<int> node; //Tree用のノード

public:
    SegmentTree(vector<int> a, int initial_val){ //a：元の配列、initial_val：初期化するときの値
        int n_ = a.size();

        n=1;
        while(n<n_) n*=2;

        node.resize(2*n-1, initial_val); //セグメント木の初期化

        /*
        * 最下段に値を入れたあとに、下の段から順番に値を入れる
        * 値を入れるには、自分の子の 2 値を参照すれば良い
        */
        for(int i=0; i<n_; i++) node[n-1+i] = a[i]; //最下段をn-1からn回ループで埋めていく
        for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]); //次に、n-2から0まで、子を比較しながら上る
    }

    //比較用の関数(今回は例として、最小値を求めたい問題を解いているとする)
    int op(int a, int b) return std::min(a, b);

    //更新（元配列のidx番目の要素をvalに変更する）
    void update(int idx, int val){
        idx += (n-1); // node[n-1+idx]（＝最下段のidx番目）にvalを入れるため 
        node[idx] = val;

        while(0 < idx){
            idx = (idx-1)/2; //「子⇒親」へ移動
            node[i] = op(node[2*idx+1], node[2*idx+2]); //親から見て、子同士をopで比較する。
        }
    }

    //要求区間[a,b)中の結果を返す。※[l,r)を対称区間の左端と右端とする。
    //　※要求区間：クエリで与えられた区間 (実際に計算したい区間) 
    //　※対象区間：各ノードがカバーしている区間
    int find(int a, int b, int now=0, int l=0, int r=-1){
        // ?
        if(r < 0) r = n;

        //要求区間と対象区間が交わらない場合⇒⇒答えの邪魔にならない値を返す。
        if((b <= l)||(r <= a)) return XXX;

        //要求区間が対象区間を完全に被覆している場合⇒⇒
        if((a <= l)&&(r <= b)) return node[now];

        //要求区間が対象区間の一部を被覆している場合⇒⇒子を再帰的に探索する。
        int vl = find(a, b, 2*now+1, l, (l+r)/2); // 子(左)
        int vr = find(a, b, 2*now+2, (l+r)/2, r); // 子(右)

        return op(vl, vr);
    }
}

http://tsutaj.hatenablog.com/entry/2017/03/29/204841

https://scrapbox.io/pocala-kyopro/%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8

セグメント木の例題と回答

#include <iostream>
#include <vector>
#include <atcoder/segtree.hpp>

int op(int a, int b) { return std::max(a, b); };
int e() { return -1; }; //全てのaに対してop(a, e) = op(e, a) = aを満たすもの

int main() {
	int N, Q;
	std::cin >> N >> Q;
	std::vector<int> A(N, 0);
	for (int n = 0; n < N; n++) std::cin >> A[n];

	atcoder::segtree<int, op, e> seg(A);
	int t, in1, in2;
	auto f = [&](int x) {return x < in2; };
	
	for (int q = 0; q < Q; q++) {
		
		std::cin >> t >> in1 >> in2;
		switch (t) {
		case 1:
			in1--;
			seg.set(in1, in2);
			continue;
			//break;
		case 2:
			in1--; //今回の問題で求めたいはArを含めた最大値なので「in2--;」はしない
			std::cout << seg.prod(in1, in2) << std::endl;
			break;
		case 3:
			in1--;
			//int ans = N + 1;
			//for (int i = (N - 1); in1 <= i; i--) if (in2 <= seg.get(i)) ans = (i+1); 
			//segtree上で二分探索をする「max_right()かmax_left()」を使い、高速化する
			std::cout << seg.max_right(in1, f) + 1 << std::endl; //見つからなかった場合、max_right()はN-1を返す
			break;
		}
	}
}

Lazy Segment Tree（遅延セグ木）

メリットは「区間更新・区間取得のクエリが処理できる」ことらしい。
通常のセグメント木との違いは「二分木を2つ（dataとlazy）使って区間取得や2度目の区間更新のタイミングまで値の更新を遅延できる」らしい。

コンストラクタ（とういか事前準備）が肝になる。
ACLのLazy Segment Treeのコンストラクタは以下の2パターン。

lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> v);
コンストラクタ引数 意味
S data側の二分木の型。つまり各要素と区間取得結果の型。
op オペレータ。通常のセグ木と同じ。S op(S a, S b)の形になる。
e 二項演算opの単位元。全てのaに対してop(a, e) = op(e, a) = aを満たすものを指す
F lazy側（操作・写像を表す値）の二分木の型。
mapping 上位ノードのlazyと下位ノードのdata間に適用する操作。
S mapping(F f, S x)の形になる。
composition 上位ノードのlazyと下位ノードのlazy間に適用する操作。
F composition(F f, F g)の形になる。
id 操作を行う関数mappingにおける恒等写像。全てのaに対してmapping(id, a) = aとなるものを指す。

（例）「整数の数列に対する、区間加算操作と区間最小値取得」機能をもつ遅延セグメント木の場合

using S = int;
using F = int;
S op(S a, S b){ return std::min(a, b); }
S e(){ return int(1e9)+1; }
S mapping(F f, S x){ return x+f; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }

int main(){
    std::vector<int> v = {0, 1, 2, 3, 4};
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
}

ACLの遅延セグメント木の使い方は以下。
通常のセグメント木と共通する部分は多い。
事前準備 ①問題に合わせてS、op、F、mapping、compositionを定義
③問題とopに合わせてeを定義
④問題とmappingに合わせてidを定義
コンストラクタ lazy_segtree< S, op, e, F, mapping, composition, id> seg(int n);
lazy_segtree< S, op, e, F, mapping, composition, id> seg(vector v);
更新（$A[p]$にxを代入） seg.set(p, x)
検索（$A[p]$の値を取得） seg.get(p)
区間$[l,r)$に対してopを実行した時の結果を取得する（例：opがminを求める関数の場合は区間最小値が取得できる） seg.prod(l, r)
全区間に対してopを実行した時の結果を取得する（例：opがminを求める関数の場合は区間最小値が取得できる） seg.all_prod()
segtree上で二分探索をし、関数fが真となる最大のrを返す（？） seg.max_right(l, f)
segtree上で二分探索をし、関数fが真となる最小のlを返す（？） seg.min_left(r, f)
区間[l,r)に対して、作用素を作用させて(mapping,compositionを使って)値を更新する（？）
※遅延セグメント木のみ		 seg.apply(l, r, F)

Lazy Segment Treeについてもっと詳しく知りたいときはこちら（T.B.D.）

遅延セグメント木の例題と回答

#include <iostream>
#include <vector>
#include <atcoder/lazysegtree.hpp>

struct Node {
	long long cnt_0 = 0; //ノード内の0の個数
	long long cnt_1 = 0; //ノード内の1の個数
	long long inversion_cnt = 0; //ノード内の転倒数
};

using S = Node;
using F = bool;
S op(S a, S b) {
	S ret_node;
	ret_node.cnt_0 = a.cnt_0 + b.cnt_0; //親ノードに含まれる0の個数は子ノードに含まれる0の個数の和
	ret_node.cnt_1 = a.cnt_1 + b.cnt_1; //親ノードに含まれる1の個数は子ノードに含まれる1の個数の和
	ret_node.inversion_cnt = a.inversion_cnt + b.inversion_cnt + (a.cnt_1 * b.cnt_0); //親ノード内の転倒数＝「子ノードの転倒数の和」＋「左子ノードの1の個数×右子ノードの0の個数」
	return ret_node;
};
S e() {//全ての a に対して op(a, e) = op(e, a) = a を満たすもの
	return Node{0, 0, 0}; //0が0個、1が0個、転倒数が0のノードが単位元となる
};
S mapping(F f, S s) {
	if (f == true) {
		Node new_s;
		new_s.cnt_0 = s.cnt_1; //作用後の0の個数は作用前の1の個数
		new_s.cnt_1 = s.cnt_0; //作用後の1の個数は作用前の0の個数
		new_s.inversion_cnt = (s.cnt_1 * s.cnt_0) - s.inversion_cnt; //作用後の転倒数は「(作用後の1の個数×作用後の0の個数)-作用前の転倒数」となる。（0と1のペアの個数は作用前後で変わらないため）
		return new_s;
	}
	else return s;
};
F composition(F f, F g) //fが後の操作（上位の値）、gが前の操作（下位の値）
{
	if (f == true) g = !g; //fがtrue（つまり、反転操作を行う）の時、gのフラグを逆転させる
	return g;
};
F id() {//全ての a に対してmapping(id, a) = a となるもの
	return false; //falseが単位元となる
}; 

int main() {
	int N, Q;
	std::cin >> N >> Q;
	atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> l_seg(N);
	for (int n = 0; n < N; n++) {
		int a;
		std::cin >> a;
		if (a == 0) l_seg.set(n, Node{ 1, 0, 0 });
		else l_seg.set(n, Node{ 0, 1, 0 });
	}
	for (int q = 0; q < Q; q++) {
		int t, l, r;
		std::cin >> t >> l >> r;
		switch (t) {
		case 1:
			l--;
			l_seg.apply(l, r, true);
			break;
		case 2:
			l--;
			std::cout << l_seg.prod(l, r).inversion_cnt << std::endl;
			break;
		}
	}
}

遅延セグメント木を使うためにどのようにS,op,F,mapping,compositionを設計するかがカギ。
ここら辺は慣れていくor都度問題をしっかり理解して逆算的に設計できる力をつけるしかない、かな。

Union-Find

Union-Findはグループ分けを効率的に管理することができるデータ構造。
具体的には以下のクエリを高速に処理できる。

  1. 統合クエリ：要素uを含むグループと、要素vを含むグループを統合する
  2. 解答クエリ：要素uと要素vが同じグループにあるかを答える

Union-Findを自分で実装するとしたら以下のコードになるが、コンテスト時にはACLを使ったほうがいい。
（#include <atcoder/dsu.hpp>が必要）

Union-Findのコード
class UnionFind {
public:
    int par[100009];
    int siz[100009];

    void init(int N) {
        for (int i = 1; i <= N; i++) par[i] = -1;
        for (int i = 1; i <= N; i++) siz[i] = 1;   
    }

    int root(int x) {
        while (true) {
            if (par[x] == -1) break;
            x = par[x];
        }
        return x;
    }

    void unite(int u, int v) {
        int RootU = root(u);
        int RootV = root(v);
        if (RootU == RootV) return;
        if (siz[RootU] < siz[RootV]) {
            par[RootU] = RootV;
            siz[RootV] = siz[RootU] + siz[RootV];
        }
        else {
            par[RootV] = RootU;
            siz[RootU] = siz[RootU] + siz[RootV];
        }
    }

    bool same(int u, int v) {
        return (root(u) == root(v));
    }
};

境界値に気をつけろ！

自分、境界値についてやらかしがちなので、丁寧に！！
例えば$A$が$1 \leqq A \leqq 10^9$で与えられたら$A=1$と$A=10^9$でも通るか確認する事！！

「答えがとても大きくなる可能性があるので〇〇で割ったあまりを求めよ」的な問題に遭遇したら

計算途中で積極的に余りをとれ！
（アルゴリズム設計力とは無関係かなと思っているので本記事では割愛します。詳細は以下の記事を参照してください。）

足し算、引き算、掛け算については計算の著中で余りをとっても正しく計算できるが、割り算は注意すること！
割り算については以下の性質を利用する。

$M$を素数都市、$b$を$M$で割り切れない整数であるとする。このとき、$M$で割った余りを求める問題では「$÷b$」を「$×b^{(M-2)}$」に置き換えても計算結果は変わらない。

※Power関数は「繰り返し二乗法」を参照のこと。
※mは問題で与えられる。（「○○で割った余りを～」の○○のこと）

long long Division(long long a, long long b, long long m){
    return ((a*Power(b,m-2, m)) % m);
}

高速化に関する話

厳密に「何をどこに書くか」をまだ定義できていませんが
「テクニックの中でも特に高速化に関するもの」をこの章に記載していきます。

計算量について

今まで計算量（オーダー）について知っていはいたが理解できていなかった。
当たり前のように計算量を意識し、息をするのと同等に計算量が少なくなるようなプログラムを書けるようにならなければならない。（漸化式などを使って）

当たり前だが計算量は$N \times M$よりも$N + M$の方が少なく済むし、
$N^2$よりも$2N$の方が少なく済む。

例を挙げるとするなら、、

for (int a = 0; a < N; a++) {
    for (int b = 0; b < M; b++) {

    }
}

とするよりも以下のプログラムの方が早い。

for (int a = 0; a < N; a++) {
    
}
for (int b = 0; b < M; b++) {

}

累積和にも通ずる話だね。

極端に高速なアルゴリズムとして、問題のサイズ$n$に依存しない定数時間で終了する$O(1)$アルゴリズムという概念もあるらしい

変数を固定する

複数の変数が出現する問題において、各々を丁寧に探索していると時間がたりない場合に「変数を固定」して考えてみる。

例えばこの問題。

$x$と$y$それぞれについて探索したくなるが、$x$を固定して考えると

  • $D-x^2 \leqq 0$の場合は$y=0$
  • $0 < D-x^2 $の場合は$\sqrt{D-x^2}$に最も近い整数が$y$となる。
#include <iostream>
#include <math.h>

int main()
{
    long long D;
    std::cin >> D;
    long long ret = D;
    //for (long long x = 0; x <= D; x++) {
    for (long long x = 0; x <= 2000000; x++) {
        if (0 < D - (x * x)) {
            long long y = std::sqrt(D - (x * x));
            ret = std::min(ret, abs((x * x) + (y * y) - D));
            ret = std::min(ret, abs((x * x) + ((y + 1) * (y + 1)) - D));
        }
        else {
            ret = std::min(ret, ((x * x) - D));
        }
    }
    std::cout << ret << std::endl;
}

ここで衝撃の事実が発覚！
for (long long x = 0; x <= D; x++) {とするとプログラムの実行時間がオーバーするが、
for (long long x = 0; x <= 2000000; x++) {だと圧倒的に早くなり制限時間内に実行し終わる。
（C++さん、気持ちは分かる。分かるよ、分かるけど、それってどうなん？）

ターゲットの個数を予め数えておく

例えばこの問題。

#include <iostream>
#include <vector>
#include <algorithm>

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

    std::vector<std::string> S_rows(N);
    std::vector<std::string> S_cols;

    for (int i = 0; i < N; i++) {
        std::cin >> S_rows[i];
    }
    for (int c = 0; c < N; c++) {
        std::string tmp_col;
        for (int r = 0; r < N; r++) {
            tmp_col += S_rows[r][c];
        }
        S_cols.push_back(tmp_col);
    }

    //「同じ行内に含まれる'o'の数（自分は除く）」×「同じ列内に含まれる'o'の数（自分は除く）」　の合計
    long long ret = 0;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (S_rows[r][c] == 'o') {
                int row_count = std::count(S_rows[r].begin(), S_rows[r].end(), 'o') - 1;
                int col_count = std::count(S_cols[c].begin(), S_cols[c].end(), 'o') - 1;
                ret += (row_count * col_count);
            }
        }
    }

    std::cout << ret << std::endl;
}

みたいに書いてしまいがちだが、

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int N;
    std::cin >> N;
    
    std::vector<std::string> S(N);
    std::vector<long long> row_counts(N, 0), col_counts(N, 0);//カウント用のvector
    for (int r = 0; r < N; r++) {
        //std::string tmp_s;
        std::cin >> S[r];
        for (int c = 0; c < N; c++) {
            if (S[r][c] == 'o') {
                row_counts[r]++; //行　カウントアップ
                col_counts[c]++; //列　カウントアップ
            }
        }
    }

    //「同じ行内に含まれる'o'の数（自分は除く）」×「同じ列内に含まれる'o'の数（自分は除く）」　の合計
    long long ret = 0;
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (S[r][c] == 'o') {
                ret += ((row_counts[r] - 1) * (col_counts[c] - 1));
            }
        }
    }
    std::cout << ret << std::endl;
}

条件を満たすものを列挙しておいて比較する

ソートして比較する

概念（問題の捉え方、考え方）的な話

厳密に「何をどこに書くか」をまだ定義できていませんが
「問題を解くための考え方の引き出し（問題によって実装の仕方はバラバラ）」をこの章に記載していきます。

Greedyアルゴリズム（貪欲法）

  • 問題を複数の部分問題に分割する
  • 各部分問題に対する解を評価する(各部分問題ごとに考えられる解のパターンは複数ある．)
  • 評価が最も良いものをその部分問題の解(=局所最適解)として，次の部分問題の解(これも複数通り考えられる)を評価する

パリティ

「偶数」と「奇数」に関する性質をパリティと言う。

以下のようなパリティに着目することはAtCoderでは頻出らしい。

  • 毎ステップごとにある量の偶奇が入れ替わる
  • どのステップもある量の偶奇が変化しない (という問題もある)

バックトラック法（バックトラッキング）

すべての場合を調べないと正解が得られないような複雑な問題において、
解の候補をローラーしていくが、途中で解になり得ないと分かった候補群は間引いていく手法。
（ゴリゴリですねぇ。。。）

二部グラフ

「"グラフ理論"的に言うと。。。」
頂点が$N$個、辺が$M$本あるグラフがあり、$i$番目の辺$M_i$は頂点$A_i$と頂点$B_i$を結んでいるとする。
各頂点には$0$or$1$が格納されており、辺で結ばれている頂点同士の値が異なるグラフのこと。

グラフが二部グラフになっているかどうかを求める問題

以下のコードはグラフが二部グラフになっているかどうかを深さ優先探索で判定するコード。
問題はこちら
https://atcoder.jp/contests/abc327/tasks/abc327_d

#include <iostream>
#include <vector>

std::vector<int> X; // -1:未定 0: 1:
std::vector<std::vector<int>> Graph;
bool is_bipartite = true;

void dfs(int pos, int val) {
    X[pos] = val;
    for (auto d : Graph[pos]) {
        if (X[d] == -1) {
            dfs(d, 1 - val); //valが０なら１、１なら0を入れる。
        }
        else if(X[d]==X[pos]) {
            is_bipartite = false;
        }
    }
}

int main()
{
    int N, M;
    std::cin >> N >> M;
    std::vector<int> A(M), B(M);
    X.resize(N + 1);
    Graph.resize(N + 1);
    
    for (int i = 0; i <= N; i++) {
        X[i] = -1;
    }

    for (int i = 0; i < M; i++) {
        std::cin >> A[i];
    }
    for (int i = 0; i < M; i++) {
        std::cin >> B[i];
        
        Graph[A[i]].push_back(B[i]);
        Graph[B[i]].push_back(A[i]);
    }

    for (int i = 1; i <= N; i++) {
        if (X[i] == -1) {
            dfs(i, 0);
        }
    }

    if (is_bipartite == false) {
        std::cout << "No" << std::endl;
        exit(0);
    }
    else {
        std::cout << "Yes" << std::endl;
    }
}

（所見では全然わからなかったので解説を見ながら自分なりに作成）

全探索

全探索の基本３パターン
　1. 問題文の通りに全探索すると解ける問題
　2. あり得る通り数を全部試すと解ける問題
　3. 答えを全探索する問題

全探索のよくある工夫３パターン
　A. 既に分かっているものは探索しない
　B. 探索の通り数を絞り込む
　C. 別の視点から全探索する

bit全探索

bit演算を使って全探索をする方法。bit全探索を使えば、部分集合を全パターン列挙することができる。

「2通り→2通り→2通り→・・・」で$2^N$の場合を管理することになったらbit全探索！！

#include <iostream>
#include <vector>

int main() {
	int N, K;
	std::cin >> N >> K;
	std::vector<std::string> S(N);
	for (int n = 0; n < N; n++) std::cin >> S[n];

	int ans = 0;
	for (long long selected = 1; selected <= (1 << N); selected++) {
		std::vector<int> backet(('z' - 'a') + 1, 0);
		for (int n = 0; n < N; n++) {
			if (((selected >> n) & 1) == 1) {
				for (char c : S[n]) backet[c - 'a']++;
			}
		}
		int tmp_ans = 0;
		for (int c = 0; c < backet.size(); c++) if (K == backet[c]) tmp_ans++;
		ans = std::max(ans, tmp_ans);
	}
	
	std::cout << ans << std::endl;
}

順列全探索

C++に関すること

数値型

型の最大・最小値

#include <limits.h>が必要

型 最大値 最小値
int INT_MAX INT_MIN
long LONG_MAX LONG_MIN
long long LLONG_MAX LLONG_MIN
double

よく使いそうなのはこれくらい？

小数を結果として出力する際はstd::fixedとstd::setprecision(xx)を使って出力桁数を調整した方がいい。（というよりもコレが原因でWAなんてアホらしすぎる、、）
※std::setrecisionは#include <iomanip>が必要

（例）小数型のansを小数点以下10桁で出力する場合

std::cout << std::fixed << std::setprecision(10) << ans << std::endl;

「int」と「long long」の使い分け

以下のような場合にはint型だとオーバーフローする可能性があるのでlong longを使う。

  • $10^9$を超える数値を扱う可能性のある問題
  • $10^5$くらいの比較的大きな数値同士を掛け算する可能性のある問題（積が10^9を超える）
  • $10^5$くらいの比較的大きな数値を１つの変数に繰り返し格納していく可能性のある問題（なぁぜ？）

double型の誤差に気を付ける

double型をそのまま使って計算するとWAになる問題もあるので、なるべく整数型で計算するように気を付ける。

例題はこちら

https://atcoder.jp/contests/abc308/tasks/abc308_c

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <stack>

//浮動小数点の演算誤差によりWAとなる。
//int main() {
//	int N;
//	std::cin >> N;
//	std::map<long double, std::vector<int>> A;
//	for (int n = 0; n < N; n++) {
//		long long a, b;
//		std::cin >> a >> b;
//		long double p = (double(a) /double(a + b));
//		A[p].push_back(n);
//	}
//	std::stack<int> s;
//	for (auto a :A) {
//		if (1 < a.second.size()) std::sort(begin(a.second), end(a.second), std::greater<int>());
//		for (int i = 0; i < a.second.size(); i++) s.push(a.second[i] + 1);
//	}
//	while (0 < s.size()) {
//		std::cout << s.top() << " ";
//		s.pop();
//	}
//	std::cout << std::endl;
//}

int main() {
	int N;
	std::cin >> N;
	std::vector<long long> A(N), B(N);
	for (int n = 0; n < N; n++) std::cin >> A[n] >> B[n];
	
	std::vector<int> Players(N);
	for (int n = 0; n < N; n++) Players[n] = n; //初めは番号の昇順に並べる
	auto sort_func = [&](int i, int j) //小数演算誤差を防ぐために整数で計算する用の並び替え関数を用意する
	{
		long long ai, aj, bi, bj;
		ai = A[i];
		bi = B[i];

		aj = A[j];
		bj = B[j];

		return ((aj * (ai + bi)) < (ai * (aj + bj))); //iとjを比較して、大きい方が先（True）となるよう並び替える（※成功率が同じ場合は番号順＝並びはそのまま）
	};
	std::stable_sort(begin(Players), end(Players), sort_func);
	for (int i = 0; i < Players.size(); i++) std::cout << (Players[i] + 1) << " ";
	std::cout << std::endl;
}
例題その２（小数部を整数で受け取る）

https://atcoder.jp/contests/abc169/tasks/abc169_c

※Visual studioでデバッグするときはscanf_s()を使うが、コード提出時（）はscanf()を使わないとコンパイルエラーが出るので注意！！（両方とも「std::」は要らない）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <atcoder/all>

#define INF (1LL<<30)

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true; }
    else return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true; }
    return false;
}

long long popcount(long long n) {
    long long ans = 0;
    for (int x = 0; x <= 60; x++) if (((n >> x) & 1) == 1) ans++;
    return ans;
}

struct TreeNode {
    std::vector<int> Children;
    bool IsVisited = false;
};

int main() {
    long long A, B1, B2;
    scanf("%lld %lld.%lld", &A, &B1, &B2);
    long long ans = (A * (B1 * 100 + B2)) / 100;
    std::cout << ans << std::endl;
}

また、double型の値を出力する際に出力する小数点以下の桁数を指定するには以下のようにする。（#include <iomanip>が必要）
std::cout << std::fixed << std::setprecision(10) << ans << std::endl;

switch文

C#と同じように書ける（T.B.D.）

算数

操作 コード #include
最小値 std::min() math.h
最大値 std::max() math.h
平方根 std::sqrt() math.h
絶対値 abs() 不要

ラムダ式

auto "関数名" = [](引数リスト){};
で宣言する。
[]を[&]にするとラムダ式中から式外のローカル変数にアクセスが可能となる。

bit演算

記号 日本語 C++での実装
OR 論理和 ```
AND 論理積 &
XOR 排他論理和 ^
反転 ~

べき乗

$ \fallingdotseq $累乗
（指数部が自然数の時に累乗というらしいが、区別出来て使っている人はあんまりいないらしい。。）

C++ではstd::pow()で計算できるのだが、以下の問題点には注意。

  • 戻り値の型がdoubleのため、結果が大きくなるとオーバーフローして変な値が返ってくる
  • 遅い（らしい。）

無難な実装は以下。（例として$13^{13}$を計算してみる）

long long int answer = 1;
int a = 13;
for(int i=0; i<a; i++){
    answer *= a;
}

std::cout << answer << std::endl;

最大・最小

std::max({ a, b, c })

文字(char)

char cに対して
大文字にする c -= 32;
ASCIIコード上で32減少させる
大文字にする c += 32;
ASCIIコード上で32増加させる

文字列

string

std::string sに対して

操作 コード
文字列sを１文字ずつループ for(auto c : s){}
文字列の末尾に１文字付け加える std::string new_s += c;
文字列sの文字数を取得する s.size()
posから最後までの部分文字列を生成する s.substr(pos)
posからn文字の部分文字列を生成する s.substr(pos, n)
pos番目からn個の要素（文字）を削除する s.erase(pos, n)
全て大文字にする std::transform(s.begin(), s.end(), s.begin(), ::toupper);
std::transform()を使うには#include <algorithm>が必要。
全て小文字にする std::transform(s.begin(), s.end(), s.begin(), ::tolower);
std::transform()を使うには#include <algorithm>が必要。

他にもS[1] = std::toupper(s[1]);で文字列中のある文字を大文字にしたり（小文字化も可）、
std::transform(s.begin()+1, s.begin()+4, s.begin()+1, ::tolower);で文字列中の2文字目から4文字目までを小文字にしたり（大文字化も可）できる。
※添え字にちょっとクセあるので注意

regex　正規表現

std::regex()の構築が遅いらしいので注意。
（検索したい文字列や置換元にしたい文字列が固定なら、さほど問題にはならないかもしれmay。（staticで初めに宣言しておくなど工夫する事））

操作 メソッド
検索 std::regex_search("対象の文字列", std::regex("検索したい文字列"))
置換 std::regex_replace("対象の文字列", std::regex("置換元となる文字列"), "置換先となる文字列")

実用例

文字列$S$に文字列ABCが含まれるか判定したいときは、

bool ret = std::regex_search(S, std::regex("ABC"));

文字列$S$内の文字列ABCを文字列Dに置換したいときは、

std::string new_string = std::regex_replace(S, std::regex("ABC"), "D");;

配列系

型

std::vector

ベクターは、配列を拡張したクラスで、あらかじめサイズを指定しなくても利用できるようにしたクラスである。そのため、添字を使って要素にアクセスしたり、最後の要素に新しい要素を追加したりすることができる。

std::vector<int[3]> v;

int a[3];
a[1] = 1;
a[0] = 2;
a[2] = 3;
v.push_back(a);

みたいなことは不可能なので

std::vector<std::vector<int>> v;
v.push_back({2, 1, 3});

のようにする。

後からサイズを変更したいときは、v.resize()を使う。

操作 実装方法
vector x内の最大値を取得する int max = *max_element(begin(x), end(x));
※#include <algorithm>が必要
vector x内の最小値を取得する int min = *min_element(begin(x), end(x));
※#include <algorithm>が必要
x.erase(i);
x.remove(v);
vector x内の重複を削除する x.erase(unique(begin(x), end(x)), end(x));

※戻り値がイテレータである点に注意
※array や 配列に対しても使える

list

リストも、配列を拡張したクラスで、任意の位置に要素を挿入したり、任意の位置の要素を削除したりすることを想定して作られている。要素の追加と削除で、要素の順番が変化するため、リストは添字で管理することはできない。

std::queue

FIFO（First-In First-Out）
#include <queue>が必要。

queue<T> q;

で宣言した変数qに対して、

操作 メソッド
要素aを追加する q.push(a)
先頭要素を削除する q.pop()
先頭要素にアクセス（参照）する q.front()
要素数を取得する q.size()

std::deque

デックと読む。二重終端キューと言われ、両端に対する要素の追加や削除が高速に行えるデータ構造。

std::priority_queue

優先度付きキューの特徴は以下。

  • キューに対して要素を優先度をつけて追加できる
  • 最も高い優先度を持つ要素をキューから取り除き、それを返すことができる。
  • 最も高い優先度を持つ要素を取り除くことなく、それを参照することが出来る。
  • 指定した要素を取り除くことなく、その優先度を変更できる。

STLの優先度付きキューはコンストラクタが曲者だ。

作りたい優先度付きキュー コンストラクタ実装例
int型の要素を降順に持つ優先度付きキュー std::priority_queue<int> pq;
int型の要素を昇順に持つ優先度付きキュー std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

※解説

std::priority_queue<
      int,                // 要素の型はint<br>
      std::vector<int>,   // 内部コンテナはstd::vector (デフォルトのまま)
      std::greater<int>   // 昇順 (デフォルトはstd::less<T>)
    > pq;

std::priority_queue pqに対して、

操作 メソッド
要素aを追加する pq.push(a)
先頭の要素にアクセスする pq.top()
先頭の要素を削除する pq.pop()
要素数を取得する pq.size()
キューが空かどうかを判定する pq.empty()

std::stack

LIFO（Last-In First-Out）

std::set

std::setは重複を許さず、要素を自動的にソートしてくれるコンテナ。
二分木探索を用いて実装されており、要素の挿入や削除、検索などの操作が高速に行える。
また、std::setはイテレータをサポートしているため、範囲ベースのforループなどで簡単に要素を取り出すことが出来る。（らしい）

使用時には#include <set>が必要。
std::set<T> stに対して、

操作 メソッド 備考
要素xの挿入 st.insert(x)
要素xの削除 st.erase(x)
要素xの検索 st.find(x) set内にnが存在するとき、st.find(n) != st.end()となる
要素の存在判定 st.contains(x) set内にnが存在するとき、st.contains(n)がTrueとなる
※C++20以降の機能なので注意！
要素のカウント st.count(x) （重複ないのはずなので0 or 1しかないのでは、、？）
サイズの取得 st.size()
要素xを二分探索 st.lower_bound(x)
st.upper_bound(x)

setのイテレータについての注意
set（とmapも？）のイテレータはvectorのイテレータとは異なるもので、扱い方も異なる
（巷ではvectorとかのイテレータはランダムイテレータと言い、setやmapのイテレータはランダムイテレータではないというそうな）
イテレータ間の距離を取得する std::distance(itr_1, itr_2);
先頭からイテレータまでの距離を取得する std::distance(st.begin(), itr);
※上記の応用
イテレータから末尾までの距離を取得する std::distance(itr, st.end());
※上記の応用
setの問題

https://atcoder.jp/contests/abc217/tasks/abc217_d

#include <iostream>
#include <set>
#include <algorithm>

int main() {
	long long L, Q;
	std::cin >> L >> Q;
	std::set<long long> st;
	st.insert(0); // 最大と最小は既に分かっているので予めを入れておく
	st.insert(L); // 最大と最小は既に分かっているので予めを入れておく

	for (int q = 0; q < Q; q++) {
		int c;
		long long x;
		std::cin >> c >> x;
		switch (c) {
		case 1:
			st.insert(x);
			break;
		case 2:
			auto itr = st.upper_bound(x);
			if (itr != end(st)) {
				std::cout << (*(itr)-*(std::prev(itr))) << std::endl;
			}
			else { } //問題の制約的にありえないはず
			break;
		}
	}
}

std::map

std::setと同じ連想配列に分類され、辞書型などと呼ばれることもある。
#include <map> が必要。
高速にキーから要素を取得できるという特徴がある。（map クラスが２分木で実装されているから、速いとのこと。）

std::map<T, T> mpに対して、
Keyに```Val``を設定する mp[Key] = Val;
Keyに設定されている```Val``を取得（して変数xに代入） auto x = mp[Key];
Keyが設定されているかを調べる auto itr = mp.find(Key);
※そのキーを指すイテレータが返ってくることに注意。キーが無ければmp.end()へのイテレータが返ってくる
Keyと一致するキーを持つ要素数を取得する mp.count(Key)
キーがKey、値がValの要素を挿入する mp.insert({Key, Val})
※要素はstd::pairで保持することに注意。
Keyに設定されているValを削除する mp.erase(Key)
空にする mp.clear()
サイズを取得する mp.size()
空かどうかを調べる mp.empty()
コンテナクラスに対してはmp.size() == 0よりもmp.empty()の方が早いことがあるらしい。。
最小のKeyを取得する mp.begin()->first
（おそらく）firstがKeyでsecondがVal
最大のKeyを取得する mp.rbegin()->first
（おそらく）firstがKeyでsecondがVal

mapの全要素にアクセスする時は以下のように実装する

auto begin = mp.begin(), end = mp.end();
for (auto iter = begin; iter != end; iter++) {
    // first: key, second: value
    cout << "key = " << iter->first << "\n";
    cout << "value = " << iter->second << "\n";
}

操作

イテレータ

「次の要素に順にアクセスできるもの」＝イテレータ。
1つ前の要素にアクセスする（方法①） itr--;としてから*itr;
1つ前の要素にアクセスする（方法②） std::prev(itr);

イテレータ - Wikipedia
https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%86%E3%83%AC%E3%83%BC%E3%82%BF
イテレータ（英語: Iterator）とは、プログラミング言語において配列やそれに類似するデータ構造の各要素に対する繰返し処理の抽象化である。実際のプログラミング言語では、オブジェクトまたは文法などとして現れる。反復するためのものの意味で反復子（はんぷくし）と訳される。繰返子（くりかえし）という一般的ではない訳語もある。

一般には配列のようなものを順番にたどるためのものです。

この記事が分かりやすい

https://betrue12.hateblo.jp/entry/2019/12/04/000146

image.png
image.png

next_permutation()

ソートした状態で渡すと順列を生成してくれる（スゲー。）
大小関係があれば対応できるので文字列にも使える（スゲー。）
計算量が$O(n!)$となるので処理時間には注意（Oh...）
※$n \leqq 10$くらいが目安らしい

使うためには#include<algorithm>が必要。

配列に対しては、

int main(){
    int N = 5;
    int A[N]={1,2,3,4,5};
    do{
        //
    }while(std::next_permutation(array,array + N));
    return 0;
}

vectorに対しては、


int main(){
    std::vector<int> v={1,2,3,4};
    do{
        //
    }while(std::next_permutation(v.begin(),v.end()));
    return 0;
}

のような形で配列やvectorの順列の全てのパターンに対して処理を実施できる。

逆順？で実施できるprev_permutation()という親戚がいるらしい

探索系

std::binary_search()

ソートされた配列やvectorの中に、keyがあるかどうかを探索する。（#include <algorithm>が必要。）

特徴としては

  • ソートされてないと使えない
  • keyがあるかどうかは分かる
  • どこにkeyがあるかは分からない
  • 同じ値のkeyが複数あったときに、どれを指しているかは分からない

std::lower_bound()

ソートされた配列やVector内で、Key以上の要素のうちの一番左側のイテレータをReturnする。

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    int N, M;
    std::vector<int> A(N);
    std::cin >> N >> M;
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
    }

    std::sort(A.begin(), A.end());

    auto Iter = lower_bound(A.begin(), A.end(), 10);
}

取得したイテレータを使って、イテレータ先頭の値、先頭からイテレータまでの距離、イテレータから末尾までの距離、などを取得できる。

//値を表示
std::cout << *Iter << std::endl;

//先頭からイテレータまでの距離を表示
std::cout << (Iter - A.begin()) << std::endl;

//イテレータから末尾までの距離を表示
std::cout << (A.end() - Iter) << std::endl;

std::upper_bound()

ソートされた配列やVector内で、Keyより大きいの要素のうちの一番左側のイテレータをReturnする。
（え、lower_bound()とあんまり変わらない。。？）

使い方もざっと見た感じlower_bound()と同じなので割愛。（違いあれば追記します。）

注意点としては返ってくるイテレータに目的の値が含まれるかどうか！

  • lower_bound()ではイテレータに目的の値が含まれる
  • upper_bound()ではイテレータに目的の値が含まれない

std::bitset

#include <bitset>が必要。
bitset型の変数bs（ビット数は60bit）に対して、

やりたい操作 実装
変数bsを宣言する。(0d15を2進数にする。) std::bitset<"bit数"> bs("2進数にしたい10進数");
（例）std::bitset<60> bs(15);
右からiビット目にアクセスする bs[i]※右端のビットにアクセスしたいときはbs[0]
※左端のビットにアクセスしたいときはbs[N-1]（Nはビット数）

数学的な話

基本のΣ公式

これくらいは知っておきましょうという話。
例えば整数N以下の整数の総和をforループで計算してたら話にならないので、「$(n*(n+1))/2$でやりましょうね」ということ。

備考
$\sum_{k=1}^{n} c = cn$
$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$
$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$
$\sum_{k=1}^{n} k^3 = \bigl( \frac{1}{2} n (n+1) \bigr) ^2 $
$\sum_{k=1}^{n} a^k = \frac{1}{1-a} $ ※$(0 < a < 1)$
$\sum_{k=1}^{n} \frac{1}{k} \fallingdotseq \log_e N $

整数問題

偉い人からのお言葉

AtCoder の整数問題は、500 点以下であれば「素因数分解」と「最大公約数」と「エラトステネスの篩」と「合同式」に関する考察・アルゴリズムを自在に操れば、ほとんど解けるようになっています

というわけでやってみる。

素因数分解

おまけ①素数判定

素数とは「1 と自分自身以外では割り切れない整数」のこと

素数判定
//素数判定関数（nが素数ならtrue、素数でないならfalseを返す
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;
}
おまけ②約数列挙
約数列挙
//約数列挙関数
#include <set>
std::set<long long> enum_divisors(long long n) {
    std::set<long long> ret;
    for (long long i = 1; (i * i) <= n; i++) {
        if ((n % i) == 0) {
            ret.insert(i);
            ret.insert((n / i)); //大きい方の約数も格納する
        }
    }
    return ret;
}
素因数分解
//素因数分解関数(pairのvectorを返し、「{i,k}＝iのk乗」を意味する)
#include <vector>
std::vector<std::pair<long long, long long>> prime_factorize(long long n) {
    std::vector<std::pair<long long, long long>> ret;
    for (long long i = 2; (i * i) <= n; i++) {
        if ((n % i) != 0) continue;

        long long tmp_ex = 0;
        while ((n % i) == 0) //nをiで割れるだけ割って、割った数（＝乗数）をカウントする。
        {
            tmp_ex++;
            n /= i;
        }
        ret.push_back({ i,tmp_ex }); //nをiで分解した結果を格納する
    }
    if (n != 1) ret.push_back({ n,1 }); //残りが1でなければ、（残りは素数のはずなので）格納する　※この時ex=1となる
    
    return ret;
}

最小公倍数・最大公約数

最小公倍数を求めるためには最大公約数が必要で、最大公約数はユークリッドの互除法を使って求める。

auto gcd = [](auto self, long long a, long long b) -> long long //2数の最大公約数を求める関数
{
    //ユークリッドの互除法
    if (b < a) std::swap(a, b); //bよりaの方が大きい時は入れ替える（常にa<bの構図を作っておく）
    if ((b % a) == 0) return a; //bがaで割り切れるとき、aはbの約数になる
    return self(self, a, (b % a));
};

auto lcm = [&](long long a, long long b) {return (a * b) / gcd(gcd, a, b); }; //2数の最小公倍数を求める関数

4の倍数、8の倍数の性質

image.png
（参考：https://www.try-it.jp/chapters-4962/sections-4963/lessons-4976/#:~:text=8%E3%81%AE%E5%80%8D%E6%95%B0%E3%81%AF%E4%B8%8B,8%E3%81%AE%E5%80%8D%E6%95%B0%E3%81%A0%E3%81%AD%E3%80%82）

エラトステネスの篩

エラトステネスの篩は、$1$以上$N$以下の素数をすべて列挙する方法。
素数判定、約数列挙、素因数分解などを高速で実行できる！（$O(N log log N)$）

//エラトステネスの篩
#include <vector>
std::vector<bool> Eratosthenes(int n) {
    std::vector<bool> is_prime((n + 1), true); //n以下の全ての整数について素数ラベルをtrueとして初期化したテーブルを準備する
    is_prime[0] = false; //0は素数ではないので素数ラベルを剥奪
    is_prime[1] = false; //1は素数ではないので素数ラベルを剥奪
    for (int i = 2; i <= n; i++) {
        if (is_prime[i] == false) continue; //素数でないものはスキップ
        for (int k = (2 * i); k <= n; k += i) is_prime[k] = false; //i以外のiの倍数から素数ラベルを剥奪
    }
    return is_prime;
}

合同式

$n$を自然数（$1$以上の整数）とすると、
整数$a,b$に対して、その差$a-b$が$n$で割り切れるとき
$a$と$b$は$n$を法として合同であるといい、
「$a \equiv b \pmod{n}$」で表される。このような式の事を合同式という。

「余りで考える」というのが大事だという問題。
MODは先に計算しても後から計算してもよいという性質が重要！！

ちなみに鳩ノ巣原理というのは、
「Nこの箱にN+1個以上のボールを収納しようとした場合に、
2個以上ボールが入る箱が必ず1個以上存在する」という原理らしい。

繰り返し二乗法

$a^b$を計算するときを考える。
整数$b$の二進法表記における$2^i$の位が$1$であるときのみに$a^{2^i}$を掛けていけばよい。

// aのb乗をmで割った余りを返す関数
long long Power(long long a, long long b, long long m = 1){
    long long p = a, ans = 1;
    for(long long i = 0; i<30; i++){ // b<=10^9くらいまでなら30回のループでまかなえるが、それ以上になるようならループ回数を増やす
        long long wari = (1<<i);
        if(((b/wari)%2)==1) ans = ((ans*p)%m);
        p = ((p*p)%m);
    }
    return ans;
}

場合の数に関する公式

項目 公式 例
n個のものを並び替える方法の数 $n!$（nの階乗）
n個のものの中からr個を選ぶ方法の数 $nCr=\frac{n!}{r!(n-r!)}$
n個のものの中からr個を選び、並び順まで決める方法の数 $nPr=\frac{n!}{(n-r)!}$

入れ替えパズル問題（ルービックキューブ的な..？）

1)「2つの行または2つの列を入れ替える」という操作を0回以上実施した後の状態は、行番号・列番号それぞれの順列で表すことが可能。

2)「隣接する2項を入れ替える」という操作を繰り返すことにより、数列$(1,2,・・・,N)$をある所望の順列$A=(A_1,A_2,・・・,A_N)$へと変えるために必要な、最小操作回数は、順列の転倒数（定義は以下参照）に等しい。

$1 \leqq i < j \leqq N$かつ$A_i > A_j$を満たす組$(i,j)$の個数

グリッドの入れ替えと転倒数の問題

問題はこちら

https://atcoder.jp/contests/abc325/tasks/abc325_c

#include <iostream>
#include <vector>
#include <algorithm>

//転倒数をカウント
int calc_inversion_count(std::vector<int> input_vector) {
    int ret_count = 0;
    for (int i = 0; i < input_vector.size(); i++) {
        for (int j = i + 1; j < input_vector.size(); j++) {
            if (input_vector[i] > input_vector[j]) {
                ret_count++;
            }
        }
    }
    return ret_count;
}

int main()
{
    int H, W;
    std::cin >> H >> W;
    std::vector<int> P, Q;
    for (int h = 0; h < H; h++) {
        P.push_back(h);
    }
    for (int w = 0; w < W; w++) {
        Q.push_back(w);
    }
    std::vector<std::vector<int>> A(H, std::vector<int>(W, 0)), B(H, std::vector<int>(W, 0));
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            std::cin >> A[h][w];
        }
    }
    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            std::cin >> B[h][w];
        }
    }

    int ret_count = -1;
    do {
        do {
            //入れ替え後のAがBと一致するかを調べる
            bool is_match = true;
            for (int h = 0; h < H; h++) {
                for (int w = 0; w < W; w++) {
                    if (A[P[h]][Q[w]] != B[h][w]) {
                        is_match = false;
                        break;
                    }
                }

                if (is_match == false) {
                    break;
                }
            }

            if (is_match == true) {
                //一致したら転倒数を調べる
                int inversion_count_p = calc_inversion_count(P);
                int inversion_count_q = calc_inversion_count(Q);
                int inversion_count_total = inversion_count_p + inversion_count_q;
                if (ret_count == -1) {
                    ret_count = inversion_count_total;
                }
                else {
                    ret_count = std::min(ret_count, inversion_count_total);
                }
            }

        } while (std::next_permutation(Q.begin(), Q.end()));
    } while (std::next_permutation(P.begin(), P.end()));

    std::cout << ret_count << std::endl;
}

上記の転倒数を求めるプログラムは計算量が$O(n^2)$と遅いが、
BITなるものを使って実装すると$O(n^2)$の計算量で済むらしい。

https://qiita.com/wisteria0410ss/items/296e0daa9e967ca71ed6

場合分けをしなくていいようにデータを整形する

与えられた数値が全部正（０より大きく）なるように入力値に同じ値を足してずらす、とか

例（として適切な問題かどうかは疑問が残るが、、、）

数式から考察する

Σの公式を分解すると高速化の糸口が見えるときもある

コードはこちら
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int N, M, P;
    std::cin >> N >> M >> P;
    std::vector<int> A(N), B(M);
    std::vector<long long> SumB(M + 1); // long long で計算しないといけない点に注意
    for (int n = 0; n < N; n++) std::cin >> A[n];
    for (int m = 0; m < M; m++) std::cin >> B[m];

    /*
    * 求めたい値をΣ公式を使って考察すると、実装が見えてくる
    * （詳しくは公式解説を参照）
    */
    std::sort(begin(A), end(A));
    std::sort(begin(B), end(B));
    for (int m = 0; m < M; m++) SumB[m + 1] = SumB[m] + B[m];
    long long ans = 0; // long long で計算しないといけない点に注意
    for (int n = 0; n < N; n++) {
        auto itr = std::upper_bound(begin(B), end(B), (P - A[n]));
        long long idx = (itr - begin(B)); // long long で計算しないといけない点に注意
        ans += (long long)((P * (M - (idx)))); // long long で計算しないといけない点に注意
        ans += (long long)(A[n] * (idx)); // long long で計算しないといけない点に注意
        ans += SumB[idx];
    }
    std::cout << ans << std::endl;
}

因数分解（多項式の除算）

コードはこちら
#include <iostream>
#include <vector>

int main() {
	int N, M;
	std::cin >> N >> M;
	N++; M++;
	int C_degree = (N + M - 1);
	std::vector<int> A(N), B(M, 0), C(C_degree), CC(C_degree, 0);
	for (int n = 0; n < N; n++) std::cin >> A[n];
	for (int nm = 0; nm < C_degree; nm++) std::cin >> C[nm];

	//for (int n = 0; n < N; n++) {
	//	for (int m = 0; m < M; m++) {
	//		CC[n + m] += (A[n] * B[m]);
	//	}
	//}

	//B[M - 1] = (C[C_degree - 1] / A[N - 1]);
	//B[0] = (C[0] / A[0]);

	for (int m = (M - 1); 0 <= m; m--) {
		int tmp_cor = (C[(N - 1) + m] / A[(N - 1)]);
		B[m] = tmp_cor;
		for (int n = (N - 1); 0 <= n; n--) {
			C[m + n] -= (B[m] * A[n]);
		}
	}

	for (int m = 0; m < M; m++) std::cout << B[m] << " ";
	std::cout << std::endl;
}

ベル数

N 個のものをグループに分ける方法（グループの順番、グループ内の順番は区別しない）の個数はベル数
B(N) としてしられています。

最後に

概念的なこともそうだし、記事を書くためのという面でもそうだが、
日本語や言語化の難しさを痛感しています。
章立てとかも難しいですね、いい訓練になります。

今までの歩み
Date 状態
2023/11/17 AtCoderなる面白そうなものを発見し、登録した。
コンテスト参加数はゼロ。過去問を何問か解いただけ。
2023/11/24 未だコンテスト参加数はゼロ。（はよせんかい）
隙間時間を使って過去問を3回分くらい追加でやった。
現在の視点としては、C++（というか使用する言語）の基礎的な実装力(今回でいうとSTL)の上に「テクニック的な話」の引き出しが成り立ち、その引き出しをどう使って「概念的なもの」をくみ上げていくかという景色が見えている。
AtCoderのA問題、B問題は引き出しを持っているとある程度解けるが、C問題、D問題になってくると引き出しの使い方を問われるようになっているイメージ。
2023/11/25 競プロは仕様がしっかり定まった状態でコーディングできる点と、仕様外の入力が来ない（ユーザーがお利口さん）という点は実務より優しいイメージ。
（もちろんアルゴリズム的な部分は歯ごたえ満点です！）
2023/12/7 コンテスト1回参加！（えらい！⇦おい）C問題までしか解けず。。
問題文を脳内でグラフに落とし込んだり、どの技法で解くべきかをマッチさせることの難しさ＆面白さを実感中。
C++はやっぱり楽しい。好き。
2023/12/17 ABC333に参加するもまたもやC問題までの3完。。
2024/1/10 コンテスト5回参加。まだまだ課題は多い。
2024/2/24 11回目のコンテストで入茶。本当は10回目で茶色になりたかった。
image.png
5
7
15

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
7

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?