競技プログラミングの上達に必要な、 "学ぶべき" アルゴリズムを解説！

今回の概要

上の記事に対応したアルゴリズムの説明などがこの記事には書かれています。
上の記事も競技プログラミングの上達にとても役立つので、読むことをお勧めします。

また、基礎的な文法¹ は理解している前提で話を進めます。
もし、文法を学びたい場合は下のサイトで勉強してみてください。
プログラムを実際に書きながら学ぶことができます。
競技プログラミングでよく使用される言語は C++, Python などで、下のサイトはC++² を学べるサイトです。

基礎的な文法は理解していても、競技プログラミングに慣れていない という方は、この問題を解いてみてください。
(AtCoderへの登録が必要です。)

また、アルゴリズムの理解に重点を置いています。
アルゴリズムの発展的な内容はあまり取り扱っていません。

私が使用している言語はC++なので、正答例などのコードもC++で書かれたものになっています。ご了承ください。
理解できないアルゴリズムがあれば、その場合は一旦スルーして、後日考え直してみるといいでしょう。下の方が難しいアルゴリズム というわけではありません。

本編

全探索

全探索というのはあり得るすべての場合を確かめるアルゴリズムです。
例題を解きながら理解していきましょう。

ABC330 A - Counting Passes

---

$N$ 人の人$1,2,…,N$ がある試験を受け、人iは$A_i$点を取りました。
この試験では、 $L$ 点以上を取った人のみが合格となります。
$N$ 人のうち何人が合格したか求めてください。

---

この問題では、参加者の点数をそれぞれ、$L$ 点以上か確かめていくことによって解くことができます。
$L$点以上の点数かどうかを確かめる処理をfor文で繰り返せば良いです。

入力例1 への処理

入力例1

5 60
60 20 100 90 40

5人が試験を受け、60点以上で合格です。

• 一人目は60点なので、合格です。
• 二人目は20点なので、不合格です。
• 三人目は100点なので、合格です。
• 四人目は90点なので、合格です。
• 五人目は40点なので、不合格です。

3人が合格しているので、3 と出力すればよいです。

正答例

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

int main(void) {
	int n, l;
	cin >> n >> l;
	int score[n], ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> score[i];
		//i人目の点数を受け取る
		if (score[i] >= l) { //i人目が l 点以上なら
			ans++; //カウントする
		}
	}
	cout << ans << endl;
	
	return 0;
}

ITP1_7_B 組み合わせの数

---

1 から $n$ までの数の中から、重複無しで３つの数を選びそれらの合計が $x$ となる組み合わせの数を求めるプログラムを作成して下さい。
例えば、1 から 5 までの数から３つを選んでそれらの合計が 9 となる組み合わせは、
$1 + 3 + 5 = 9$
$2 + 3 + 4 = 9$
の２通りがあります。
制約
$3 ≤ n ≤ 100$
$0 ≤ x ≤ 300$

---

この問題は、ループ文を三重にすることによって解くことができます。
ループ文を多重にするというのは今後もよく使うテクニックです。
この問題では、一番外のループ文で1つ目の数字を決めて、二つ目のループ分で2つ目の数字を決めて、３つ目のループ分で3つ目の数字を決めています。
(下のコードは誤答です。)

誤答の例

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

int main(void) {
	int n, x;
	while (true) {
		int ans = 0;
		cin >> n >> x;
		if (n == 0 && x == 0) {
			break;
		}
		for (int i = 1; i <= n; i++) { //1つめの数字
			for (int j = 1; j <= n; j++) {  //2つ目の数字
				for (int k = 1; k <= n; k++) {  //3つ目の数字
					if (i + j + k == x) {
						ans++;
						//printf("%d %d %d\n", i, j, k);
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

こちらのプログラムは一見正しいように見えますが、間違えています。
例えば 5 9 という入力があった場合に、想定出力は2なのですが、19と出力されてしまいます。
何故間違えているのかを考えてみましょう。

間違えている理由

上のコードの中にprintf("%d %d %d\n",i,j,k);という記述を追加してみましょう。(このコードは3つの数の組み合わせを出力してくれます。)

下は、5 9の場合の出力結果です。

出力結果

1 3 5
1 4 4
1 5 3
2 2 5
2 3 4
2 4 3
2 5 2
3 1 5
3 2 4
3 3 3
3 4 2
3 5 1
4 1 4
4 2 3
4 3 2
4 4 1
5 1 3
5 2 2
5 3 1
19

ここからなぜこの解答が間違えているのかを考えてみると、問題文の中には 重複なしで3つの数を選び と書かれていますが、3 3 3 などの重複がある組み合わせもカウントしていることがわかります。
また、2 3 4と2 4 3 という 同じ組み合わせもカウントしている ということもわかります。
これを直すにはどうすればいいでしょうか。

これを直すには $1\leqq i < j < k \leqq n $という条件を加えるという方法があります。
この条件を加えると数の重複、同じ組み合わせのカウントを回避できます。

---

以下に正答例を示します。

正答例

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

int main(void) {
	int n, x;
	while (true) {
		int ans = 0;
		cin >> n >> x;
		if (n == 0 && x == 0) {
			break;
		}
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) { //jを変更 j = i + 1 にして、 i < j に
				for (int k = j + 1; k <= n; k++) { //kを変更 k = j + 1 にして、 j < k に
					if (i + j + k == x) {
						ans++;
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

全探索 の問題をさらに

---

工夫が必要な全探索

ここから先は 計算量 について考える必要が出てきます。

コンピューターではおおよそ$10^8$ (1億) 回の処理を1秒間に行うことができます。
そして競技プログラミングの問題では、実行時間制限というものがあり、その実行時間に処理が間に合わないと TLE という誤答になってしまいます。(2秒などの場合が多いです)
例えば、上の ITP1_7_B 組み合わせの数 という問題も、制約が$3\leqq N \leqq 5000$ などの大きな値になると、先程の解き方ではTLEになってしまいます。
TLE を避けるために 処理のスピードが速い全探索の方法を考える必要があります。(この、高速で処理を実行するという考え方は他のアルゴリズムなどでも重要になってきます)
また、問題には必ず制約というものが書かれているのですが、それも TLE を避けるためにとても大切になってきます。制約を確認する癖をつけておくといいでしょう。

計算量についてはこちらの記事に詳しく書かれています。

---

ABC179 C - A x B + C

---

正整数 $N$ が与えられます。
$A×B+C=N$ を満たす正整数の組 $(A,B,C)$はいくつありますか？
制約
$2\leqq N \leqq 10^6$
入力はすべて整数

---

まずは A,B,C の三重ループのコードを書いてみましょう。

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

int main(void) {
	int n, ans = 0;
	cin >> n;
	for (int a = 1; a < n; a++) { // a の値
		for (int b = 1; b < n; b++) { // b の値
			for (int c = 1; c < n; c++) { // c の値
				if (a * b + c == n) {
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	
	return 0;
}

このコードの提出結果はTLE でした。
この問題での $N$ の制約は $2 \leqq N \leqq 1000000$ なので、このコードのような三重ループがあると、最大で $1000000^3$ 回の処理を行わなければなりません。 この回数の処理は、長い実行時間がかかってしまい、 TLE になってしまいます。

この問題で AC するために、このコードを高速化する方法を考えてみましょう。

高速化の方法

$AB < N$ が成り立てば、$A\times B + C =N$ も成り立たせることができます。

($N - A\times B$の値を$C$とすれば成り立つ。)

つまり、 $AB < N$になる$A,B$の組み合わせが何通りあるかを確かめれば良いです。
これによって、三重ループを二重ループに変更することができて、計算量を削減できます。

このように、 他の値を決めれば 1つの変数の値が一つに決まる というパターンはよくあります。
なので、このような考え方をしっかりと理解しましょう。

正答例

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

int main(void) {
	int n, ans = 0;
	cin >> n;
	for (int a = 1; a < n; a++) {
		for (int b = 1; a * b < n; b++) {
			if (a * b < n) {
				ans++;
			}
		}
	}
	cout << ans << endl;
	
	return 0;
}

三井住友信託銀行プログラミングコンテスト2019 D - Lucky PIN

---

---

Sの中から選ぶ文字を全探索すると、TLE になってしまいます。
なので、他の解き方を考えます。

3桁の暗証番号 は、 000 ~ 999 の 1000通り しかありません。
なので、暗証番号を作成できるか 000 から 999 まで確かめることでこの問題は解くことができます。

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


int main(void){
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  for(int i = 0; i <= 999; i++){ //全ての暗証番号について試す
    int first = -1, second = -2, third = -2;
    string pin = to_string(i);
    if(i < 100) pin = "0" + pin; //0埋め
    if(i < 10)  pin = "0" + pin; //0埋め
    
    for(int j = 0; j < n; j++){
      if(first == -1 && pin[0] == s[j]){ //1文字目を探す
        first = j; //1文字目の場所を記録する
        second++;  //2文字目を探し始める
      }
      else if(second == -1 && pin[1] == s[j]){ //2文字目を探す
        second = j; //2文字目の場所を記録する
        third++;    //3文字目を探し始める
      }
      else if(third == -1 && pin[2] == s[j]){ //3文字目を探す
        third = j; //3文字目の場所を記録する
      }
    }
    if(first < second && second < third){
      ans++;
    }
  }
  cout << ans << endl;
}

工夫の必要な全探索 の問題をさらに

bit全探索

bit全探索を理解するには、まずbit演算について理解する必要があります。
そもそも、bitとは二進数のことで、0か1 で表されるデータのことです。
(二進数については、調べてみてください。)
整数でいう足し算のように、bitでも計算のようなものをすることができます。
それがbit演算です。
bit演算には、足し算の記号のような、演算子というものがあります。
演算子がどんな意味を持っているのかを下の表で理解しましょう。

ビット演算	演算子	意味
AND	&	両方のビットが1ならば1
OR	|	少なくとも一方のビットが1ならば1
XOR	^	どちらか一方だけのビットが1ならば1
NOT	~	各ビットで、0と1を入れ替える
左シフト演算	<<	指定したビット数、ビット列を左にずらす。
右シフト演算	>>	指定したビット数、ビット列を右にずらす。

011 & 010 なら、両方のビットが1のところのみ1なので、 010 となります。

(3 << 2) なら、 11 が左に2ビットずれて、 1100 となります。
シフト演算は、範囲外のビットは切り捨てられて、足りないビットは0になります。

(1 << n) と書くことによって $2^n$を表せます。
(1 << n) という記述はbit全探索でよく使います。

---

bit全探索は2択が複数あるときなどに使う探索の方法です。
難しそうに思えますが、 選ぶか、選ばないか を全探索しているだけです。
どのような例で使えるかというと、

A,B,Cという3枚の数字が書かれたカードがあります。3枚のカードからいくつかを選び、書かれていた数字の合計がNになる組み合わせはありますか。

この問題では、カードを選ぶか、カードを選ばないかを全探索するのにbit全探索が使えます。
A,B,Cのカードを選ぶか選ばないかを数字の1(選ぶ),0(選ばない)で表すと下の表のようになります。

Aのカードを選ぶか	Bのカードを選ぶか	Cのカードを選ぶか
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

そして、これらの組み合わせは 2進数の値 の様になっていることがわかります。
一番上のCのカードのみを選ぶ組み合わせは 001 となっていて、これを10進数に直すと1になるということがわかります。
同じ様に10進数に直したものをまとめた表を見てみましょう。

2進数	10進数
001	1
010	2
011	3
100	4
101	5
110	6
111	7

先程のカードの選び方の組み合わせを2進数にすると、 10進数で 1~7 という連続した値になることがわかります。
逆に考えると、 10進数の 1~7 という数字を 2進数に直すとカードの選び方の組み合わせが表せるということです。

これがbit全探索の考え方です。

この問題でいうと、 1~7 の繰り返しの処理を作り、その数を2進数に直して、処理することによって、全ての場合について調べることができます。

2進数$i$ の $j$桁目 (右から $0$桁, $1$桁, ...桁としたとき) が 1かどうかを確かめるには、if (i & (1 << j)) などと書くことができます。

注意としては、 選ぶか選ばないかを決定する対象が 20個程度 まででないと使えないことです。計算量は$O(2^n)$ で、対象が一つ増えるだけで、組み合わせの数が指数関数的に増加していきます。

ABC044 C - 高橋君とカード

---

ここからは問題を解いて理解してみましょう。

高橋君は、$N$ 枚のカードを持っています。
$i(1≤i≤N)$ 番目のカードには、整数$x_i$が書かれています。
高橋君は、これらのカードの中から $1$ 枚以上を選び、 選んだカードに書かれた整数の平均をちょうど $A$ にしたいと考えています。
そのようなカードの選び方が何通りあるか求めてください。
制約
$1≤N≤50, 1≤A≤50 , 1≤x , i≤50$
$N,A,x_i$はいずれも整数である
部分点
$1≤N≤16$を満たすデータセットに正解した場合は、 200 点が与えられる。

今回は部分点を獲得することを目指します。(満点にはDPというアルゴリズムを使う必要があります。)

この問題ではカードを選ぶか、選ばないかでbit全探索をします。
実装の方向性としては、

• 10進数を2進数に変換する(選ぶカードの桁のみ1となる)
• 選んだカードの枚数とカードの数字の合計を求める
• 選んだカードの数字の平均を求める。
• 平均がaならば、答えに+1する

これらを$2^n$回繰り返し、答えを出力します。
この処理を行うことによって、カードの選び方の組み合わせをすべて試すことができます。

正答例

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

int main(void){
  int n, a;
  cin >> n >> a;
  int x[n];
  for(int i = 0; i < n; i++) cin >> x[i];
  
  int ans = 0;
  for(int i = 1; i < (1 << n); i++){ //2^n 回繰り返す
    double sum = 0;
    int count = __builtin_popcount(i);
    //i を2進数に変換したときの1の数を返す
    //つまりは、count に 選ぶカードの数を代入する
    
    for(int j = 0; j < n; j++){
      if(i & (1 << j)){ //iを2進数に変換したもののj桁目が 1 なら
        sum += x[j]; //sum に カードに書かれた数字を加える
      }
    }
    
    if(sum / count == a) ans++;
    //カードの平均がaなら、組み合わせの数にカウントする
  }
  cout << ans << endl;
}

このコードでは AC ではなく WA などと表示されると思いますが、
部分点の200点を獲得できていれば、問題ありません。

bit全探索 の問題をさらに

順列全探索

例えば、1,2,3 という3つの要素を持つ配列があったとします。
その配列で順列の全列挙をした結果を出力すると下のようになります。

順列の全列挙をした結果

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

上の処理を行うコード

このように、順列の全列挙をするには、next_permutation という物を使います。
下のように記述すれば、順列を全列挙し、それに対して処理を行うことができます。

vectorの場合です

sort(配列変数.begin(), 配列変数.end());
do {
  // 順列に対する処理
} while (next_permutation(配列変数.begin(), 配列変数.end()));

なお、配列の長さを$N$ とすると、計算量は$O(N!)$ になります。
使う際は、配列のサイズに注意しましょう。

これらの並び替えた配列に対して、全探索を行うことを 順列全探索 といいます。

早速問題に入りましょう。

ABC150 C - Count Order

---

大きさ $N$ の順列 (($1, 2, ..., N$) を並び替えてできる数列) $P, Q$ があります。大きさ $N$ の順列は $N!$ 通り考えられます。このうち、$P$ が辞書順で $a$ 番目に小さく、$Q$ が辞書順で $b$ 番目に小さいとして、$|a−b|$ を求めてください。
注記
2 つの数列 $X, Y$ について、ある整数 $k$ が存在して $X_i=Y_i(1≤i<k)$ かつ $X_k<Y_k$が成り立つとき、$X$ は $Y$ より辞書順で小さいと定義されます。
制約
$2≤N≤8$
$P, Q$ は大きさ $N$ の順列である。入力は全て整数である。

P,Qが辞書順で何番目に小さいかを求めて、$|a-b|$を出力します。
next_permutationを使うと、辞書順に繰り返す処理を書くことができます。

正答例

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

int main(void) {
	int n;
	cin >> n;
	vector<int> li(n), p(n), q(n);
	for (int i = 0; i < n; i++) li[i] = i + 1; //n個の要素がある順列を生成する
	for (int i = 0; i < n; i++) cin >> p[i];
	for (int i = 0; i < n; i++) cin >> q[i];
	int count = 1, a, b;
	do {
		if (li == p) a = count; //li == p なら、aにpが辞書順で何番目に小さいかを代入する。
		if (li == q) b = count; //li == q なら、bにqが辞書順で何番目に小さいかを代入する。
		count++; //辞書順で何番目かを保存しておく変数
	} while (next_permutation(li.begin(), li.end()));
	cout << abs(a - b)<<endl;
	
	return 0;
}

順列全探索の問題をさらに

貪欲法

貪欲法³ とは、その後のことは考えずに、 今できる最善の選択をする というアルゴリズムです。
必ず最適な回答を導き出すわけではありませんが、一部の問題には有効です。

ABC160 B - Golden Coins

---

高橋君は金色の硬貨が好きです。自分が持っている500円硬貨1枚につき1000、5円硬貨1枚につき 5の 嬉しさ を得ます。
高橋君は $X$ 円を持っています。これを高橋君の嬉しさが最大になるように両替したとき、高橋君の嬉しさはいくらになりますか？

この問題は貪欲法を用いて解くことができます。

まず、高橋君が500円以上を持っているときには、500円を 5円100枚に両替 するよりも、500円1枚に両替したほうが、嬉しさは多くなります。
500,5円硬貨以外では嬉しさを得ないので、 500円以上あるなら、500円に両替して、5円以上500円未満なら、5円に両替する プログラムを作ることによって、この問題は解くことができます。

正答例

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

int main(void) {
	int x, happy = 0;
	cin >> x;
	while (true) {
		if (x / 500 != 0) { //500円以上なら
			x -= 500; //所持金から500円マイナスする
			happy += 1000;
		}
		else if (x / 5 != 0) { //5円以上500円未満なら
			x -= 5; //所持金から5円マイナスする
			happy += 5;
		}
		else break; //5円未満なら処理を終える
	}
	cout << happy << endl;
	
	
	return 0;
}

二分探索

候補の半分を除外していき、目的のものを見つける探索法を 二分探索 といいます。よくあげられる二分探索の例として、数当てゲーム があります。

例えば、ある人が1~100の中から1つの数字を思い浮かべます。ある人が思い浮かべた数字をあなたはできるだけ少ない回数の質問で当てるというゲームです。

• 1ですか?
• 2ですか?
• 3ですか?

と1つずつ聞いていくと、100を思い浮かべていた場合に100回の質問が必要です。
言い換えると、1回の質問で1つの数字を除外しています。

他の方法でもっと少ない質問で思い浮かべている数字を当てられないか考えてみましょう。

• 51以上ですか?
• 26以上ですか?
• 38以上ですか?

と聞いていくと、どんな数を思い浮かべていた場合でも、7回以下で当てることができます。
これは、1回の質問で候補の半分を除外しています。

下の表は、質問の回数と、候補の個数の関係を表しています。

質問の回数	nですか?	n以上ですか?
0	100	100
1	99	50
2	98	25
3	97	13
4	96	7
5	95	4
6	94	2
7	93	1

というように、明らかにn以上ですか? という質問のほうが効率が良いです。

先程の1つずつ聞いていく方法を 線形探索 、候補を半分にしていく方法を 二分探索 といいます。

候補数を$N$とすると、 線形探索では 最悪$N$回の質問が必要ですが、二分探索では 最悪でも$log_2N$回で数を当てることができます。
二分探索は、配列から目的の値があるかを確かめるときなどに使うことができます。
ただし、昇順 などになっていないと使うことができません。

---

二分探索は主に、ソートされた配列から目的の値を探すときに使われます。

例えば、10 ~ 50 の 41個 の値があった配列 $A = 10, 11,...,50$ があったとします。その配列$A$の中から、$38$ という値を二分探索で探します。

二分探索をするには、まず$left, right, mid$ という変数3つを用意します。
そして、$left$ は配列の1つ目の値、$right$ は配列の最後の値,$mid$ を配列の真ん中辺りの値 にします。

この例で言えば、$left = 10, right = 50, mid = 30$ にします。

そして、目的の値が $mid$の値以上なら、$left$ を $mid$の値にして、目的の値が $mid$の値未満なら、$right$ を $mid$ の値にします。
(要するに、数当てゲームでいう、質問と同じようなことをしています。)
その処理の後に、$mid$ を $left$ と $right$ の間の要素にしておきます。

この例で言えば、目的の値は$38$ なので、目的の値は $mid$ つまり $30$ 以上です。
なので、$left$ を $mid$ の値にして、$mid$ を $left$ と $right$ の間の値にします。
つまり、$left = 30, right = 50, mid = 40$ になります。

次に、目的の値は$38$ なので、目的の値は $mid$ つまり $40$ 未満です。
なので、$right$ を $mid$ の値にして、$mid$ を $left$ と $right$ の間の値にします。
つまり、$left = 30, right = 40, mid = 35$ になります。

この処理を続けていくと、

となります。
最終的に、$left$ が目的の値になったなら、その目的の値が配列の中から見つけられたということです。

つまり、最終的に$left = 38$ になったので、配列$A$の中から $38$ を見つけられたということです。

二分探索とはこのような処理を行うアルゴリズムです。

この記事がわかりやすいと思います。
@Pro_ktmr (きたむー) さん、ありがとうございます。

---

ALDS1_4_B 二分探索

---

$n$個の整数を含む数列$S$と、$q$個の異なる整数を含む数列 $T$を読み込み、$T$に含まれる整数の中で $S$に含まれるものの個数 $C$を出力するプログラムを作成してください。
制約
$S$の要素は 昇順に整列されている
$n≤100,000$
$q≤50,000$
$0≤Sの要素≤10^9$
$0≤Tの要素≤10^9$
$T$の要素は互いに異なる

数値がいくつか与えられるので、その数が数列$S$に含まれるか判定するという問題です。
線形探索では制限時間内に処理を終えられません。

上に書いてある処理を実際に実装してみましょう。

正答例

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

int main(void) {
	int n, q;
	cin >> n;
	int s[n];
	for (int i = 0; i < n; i++) cin >> s[i];
	cin >> q;
	int t[q];
	for (int i = 0; i < q; i++) cin >> t[i];
	int left, right, mid, ans = 0, num;
	
	//読み込み・準備完了
	for (int i = 0; i < q; i++) {
		left = 0, right = n;
		num = t[i]; //Sに含まれるか確かめる数
		while (left + 1 != right) { //幅1でなければ
			mid=(left + right)/2;
			if (s[mid] <= num) { //確かめる数がsの中心以上なら
				left = mid; //sの中心の数以下を確かめる
			}
			else { //確かめる数がsの中心未満なら
				right = mid; //sの中心の数よりも大きい数を確かめる
			}
		}
		if (s[left] == num) { //numがsに含まれるなら
			ans++;
		}
	}
	cout << ans << endl;
	
	return 0;
}

二分探索の問題をさらに

データ構造

グラフ

こちらの記事には、グラフについてのわかりやすい説明が書かれています。

グラフは 頂点 と 辺 で構成されています。
また、辺の向きを考えるグラフを 有向グラフ、
辺の向きを考えないグラフを 無向グラフ といいます。

以下はグラフに関係する用語の説明です。

• 次数：頂点に繋がっている辺の数のことです。
• 切断点/切断辺：削除すると連結グラフが二つに分割されてしまう点と辺のことです。
• 路： グラフ上の二頂点において、隣接する頂点を辿っていくと、二つの頂点が結べるとき、その経路を 路 といいます。
• パス： 同じ頂点を二度通らない路をパスとよびます。
• サイクル (閉路)： 始点と終点が等しい路をサイクルとよびます。
• 連結： 任意の二頂点を結ぶことができるグラフのことです。
• 強連結： どちらの方向からも任意の二頂点を結ぶことができるグラフのことです。

---

グラフの出題例
ABC284 C - Count Connected Components

木

こちらの記事には木構造について書かかれています。

木とは、 サイクルを持たない かつ 連結 であるようなグラフのことです。木に対し、特定の一つの頂点を 根 とよびます。そのような根をもつ木のことを 根つき木 とよびます。また、根までの距離のことを、 深さ といいます。

下の図は根つき木の例です。

この根つき木の探索する順番の違いが 深さ優先探索 と 幅優先探索 の違いです。
下の図は、数字が探索する順番を指しています。

---

木構造の出題例
ABC138 D - Ki

Union-Find

これらのサイトにはUnion-Find についてのわかりやすい説明が書かれています。
Union-Findとは、 木構造でグループを管理する データ構造のことです。

根が同じならば、同じグループだということがいえます。
逆に、2つの要素を同じグループにするには 根を同じにすると良いともいえます。

DSL_1_A 互いに素な集合

---

互いに素な動的集合 $S = {S_1, S_2,...,S_k}$ を管理するプログラムを作成してください。
まず、整数 $n$ を読み込み、$0, 1, ... n-1$ をそれぞれ唯一の要素とする $n$ 個の互いに素な集合を作成します。次に、整数 $q$ を読み込み、$q$ 個のクエリに応じて集合を操作します。クエリは以下の二種類を含みます：

• unite($x, y$): $x$ を含む集合 $S_x$ と $y$ を含む集合 $S_y$ を合併する。
• same($x, y$): $x$ と $y$ が同じ集合に属しているかを判定し、同じ集合に属しているならば、1を出力する。そうでなければ、0を出力する。

下の正答例のコードは、構造体というC++の機能を使用しています。
構造体についてを知らない場合は、下のサイトを見てみましょう。

この問題は、Union-Findを用いて解くことができます。

unite というクエリは、$x$を含む集合と$y$を含む集合を合併するという内容です。下のコードでは、要素の数が少ない方の集合の親に、要素の数が多い方の集合をくっつけるという実装をしています。
下の図は、二つの木構造をuniteした結果を表しています。

same というクエリは、$x$と$y$が同じ集合に属しているかを判定するという内容です。下のコードでは、$x$と$y$の親が同じかどうかを判定することによって、同じ集合に属しているかを判定しています。

正答例

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

struct UnionFind {
	vector<int> parents;
	//親を記録するvector
UnionFind(int n): parents(n,-1) {}
	//全てを親にする
	
	int leader(int x) {
		if (parents[x] < 0) return x;
		//一番上の親なら、その親の番号を返す
		else return parents[x] = leader(parents[x]);
		//上に親がまだいるなら、一番上の親になるまで再帰する
		
		//つまりは、leader(int x) は必ず一番上の親の番号を返す
	}
	
	void unite(int x, int y) {
		x = leader(x);
		y = leader(y);
		if (x != y) { //xとyが同じ親ではないなら、
			if (parents[x] > parents[y]) swap(x, y);
			//yをより多くの子がいる方にする
			
			parents[x] += parents[y];
			//これからできるxの子の数を先に記録しておく
			
			parents[y] = x;
			//親yの親をxにする
			//つまり、親がyだったグループを 親がxのグループに併合する
		}
		//つまりは、unite(int x, int y)は、xを含む集合とyを含む集合を併合する
		
	}
	bool same(int x, int y) {
		return leader(x) == leader(y);
		//x, yの親が一緒かどうかを返す
	}
};

int main(void) {
	int n, q, com, x, y;
	cin >> n >> q;
	UnionFind UF(n);
	for (int i = 0; i < q; i++) {
		cin >> com >> x >> y;
		if (com) {
			//xとyが同じ集合に属すなら1,そうでなければ0を出力
			cout << UF.same(x, y) << endl;
		}
		else {
			//xを含む集合とyを含む集合を合併する
			UF.unite(x, y);
		}
	}
}

Union-Find の問題をさらに

深さ優先探索

深さ優先探索は、探索対象となる最初のノードから、目的のノードが見つかるか 子のないノードに行き着くまで、 深く伸びていく探索 です。
スタック、再帰関数 を使うことによって実装できます。

ABC075 C - Bridge

---

自己ループと二重辺を含まない $N$ 頂点 $M$ 辺の無向連結グラフが与えられます。$i(1≦i≦M)$番目の辺は頂点$a_i$と頂点$b_i$を結びます。
グラフから辺を取り除いたとき、グラフ全体が非連結になるような辺のことを橋と呼びます。
与えられた $M$ 本のうち橋である辺の本数を求めてください。
制約
$2≦N≦50$
$N−1≦M≦min(N(N−1)⁄2,50)$
$1≦a_i<b_i≦N$
与えられるグラフは自己ループと二重辺を含まない。
与えられるグラフは連結である。

この問題は、入力を受け取ってから

• 1つ辺を取り除く
  • 頂点1に訪れる
    • 今いる頂点から訪れたことのない頂点に移動できるなら移動する
    • 上の処理を頂点の数だけ繰り返す
• もしすべての頂点に訪れられなかった場合、ansに+1する
• 取り除いた辺を元に戻す

という処理を辺の数だけ繰り返すことによって、解くことができます。

入力例1 への処理

入力例1

7 7
1 3
2 7
3 4
4 5
4 6
5 6
6 7

まずは、入力例1 の状態そのままをグラフにしてみると、

となります。

7つの辺について、その辺を取り除いて橋であるかどうかを確かめます。

その辺を取り除くとグラフが非連結になってしまう辺を赤色にして表すと、

このようになり、赤色の辺を数えると4つなので、答えは 4 になります。

正答例

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

int n, m;
int a[50], b[50];
bool graph[50][50], visited[50];
//graph[x][y] = true なら、xとyが結ばれているということ。
//visited[x] = true なら、xにすでに訪れたということ。

void dfs(int visit) { //visit = 場所
	visited[visit] = true; //今いる場所を訪れたと記録する
	
	for (int i = 0; i < n; i++) { //すべての頂点に訪れられるか試す
		
		//今いる場所と次に行く点が結ばれていないか、次に行く点に訪れている場合
		if (!graph[visit][i] || visited[i]) continue; //dfs(i) をスキップする
		
		dfs(i); // 0 ~ (n - 1) の頂点に訪れられるなら訪れる
	}
}

int main(void) {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i]>>b[i];
		a[i]--;
		b[i]--;
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
		//点aと点bが辺で結ばれていることを記録する
	}
	int ans = 0;
	for (int i = 0; i < m; i++) { //すべての辺について繰り返す
		
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = false;
		//点aと点bが辺で結ばれていない場合について試す
		
		for (int j = 0; j < n; j++) {
			//すべての頂点に訪れていないことにする
			visited[j] = false;
		}
		dfs(0);
		//すべての頂点に訪れられるかを調べる
		
		for (int j = 0; j < n; j++) {
			if (!visited[j]) { //点(j + 1)に訪れていないなら
				//つまり1辺を取り除くと、すべての点に訪れられなかった場合
				ans++; //答えに+1する
				break;
			}
		}
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = true;
		//辺を取り除いた2点を辺で結び直す
	}
	cout << ans << endl;
}

(この問題は、DFS,BFS,Union-Find などを用いることで解くことができます。)

深さ優先探索 の問題をさらに

幅優先探索

幅優先探索は、出発点の近くから順に調べていく探索です。
つまりは、 浅いところをしっかり探索してから、深いところを探索していく ということです。

探索の始点となる頂点から、各頂点への最短経路を求めることもできます。
キュー を使うことによって実装できます。

ABC088 D - Grid Repainting

---

問題文
縦 $H$ マス, 横 $W$ マスに広がるマス目があり, 各マスは白または黒で塗られている. 上から $i$ 番目で左から $j$ 番目のマスを $(i,j)$ で表す. すぬけ君は, このマス目を使って次のようなゲームをしたい. ゲームの開始時点ではマス $(1,1)$ にゲームキャラクター「けぬす君」がいる. プレイヤーはけぬす君を上下左右の $4$ 方向のいずれかに $1$ マスだけ動かすことを繰り返す. けぬす君が白いマスだけを通って $(H,W)$ にたどり着けばゲームクリアとなる.
ゲームを開始する前に, すぬけ君はいくつかの白いマス目の色を黒に変えることができる. ただし, マス $(1,1)$ と $(H,W)$ の色を変えることはできず, ゲームを開始するまでにすべての色の変更を行わなければならない.
ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる. そのとき, すぬけ君が取る可能性のある最大のスコアを求めなさい.ただし, すぬけ君がどのようにマス目の色を変えてもけぬす君が $(H,W)$ にたどり着くことが出来ない場合、−1 と出力しなさい.
ただし, 各マスの色の情報は文字 $s_i,_j$ として与えられる. マス $(i,j)$ が最初白で塗られている場合 $s_i,_j$ は . であり, マス $(i,j)$ が最初黒で塗られている場合 $s_i,_j$ は # である.
制約
$H$ は $2$ 以上 $50$ 以下の整数
$W$ は $2$ 以上 $50$ 以下の整数
$s_i,_j$は.または#$(1≤i≤H,1≤j≤W)$
$s_1,_1$,$s_H,_W$は.である

この問題文はかなり長いですが、考えてみると要するに

白いマスの数 - すぬけ君が最短経路で通る白いマスの数 = 答え 

となります。
幅優先探索を用いて、 $(1, 1)$から、 $(h, w)$ への最短経路を求めることによって、この問題は解くことができます。

この問題で最短経路を幅優先探索で求めるには、

• $(1,1)$に訪れる
  • 今いる場所の上下左右のマスについて試す
    • そのマスに 訪れられる かつ 訪れたことがないならば そのマスに訪れる
    • そのマスに訪れたこと、何回の移動でそのマスにたどり着けるか、を記録しておく
  • 訪れたことはあるが、上下左右のマスについて試してはいないマスに移動する

という処理をすれば良いです。

入力例1 への処理

入力例1

3 3
..#
#..
...

入力例1 はつまり、マスがこのような状況になっていることを表しています。

そして、$(1, 1)$ から何回の移動で辿り着けるか、それぞれのマスに書き入れると、このようになります。

そうすると、$(H, W)$ に最短で移動する場合は、4回の移動が必要だとわかります。
つまりは、最短経路で通る白いマスは全てで 5つです。
そして、白いマスは全てで 7つ なので、 $7 - 5 = 2$ で、答えは 2 ということがわかります。

正答例

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
int grid[50][50], visited[50][50];
int h, w, white;
int dir[4] = {0, 1, 0,-1}; //方向用の配列

int bfs() {
	queue<pair<int, int> > que;
    que.push({0, 0});
	visited[0][0];
	
	while (!que.empty()) { //どこにも訪れられなくなるまで繰り返す
		int x, y;
        x = que.front().first;
        y = que.front().second;
		//今いる場所をx, yに代入する
		que.pop();
		
		if (x == w - 1 && y == h - 1) return grid[x][y];
		//ゴールに到着したなら、最短経路のときに通る白マスの数を返す
		
		for (int i = 0; i < 4; i++) { //四方向について試す
			
			int x_next = x + dir[i];
			int y_next = y + dir[3 - i];
			//次に行く可能性のあるマスを代入する (以下 そのマスと呼ぶ)
			
			if (0 <= x_next && x_next <= w - 1  &&  0 <= y_next && y_next <= h - 1) {
				//そのマスが存在するならば
				if (grid[x_next][y_next] && !visited[x_next][y_next]) {
					//そのマスが白色 かつ そのマスに訪れていないならば
					
					visited[x_next][y_next] = 1;
					//そのマスに訪れる
					
					grid[x_next][y_next] = grid[x][y] + 1;
					//そのマスが何回の移動で訪れられたかを記録する
					
				que.push({x_next, y_next});
					//キューにそのマスを追加する
				}
			}
			
		}
	}
	return 0;//ゴールに到着できなければ、0を返す
}

int main(void) {
	cin >> h >> w;
	string s;
	for (int i = 0; i < h; i++) {
		cin >> s;
		for (int j = 0; j < w; j++) {
			//黒で塗られているなら0に、白なら1にする
			if (s[j] == '#') {
				grid[j][i] = 0;
			} else {
				white++; //白マスの数を記録しておく
				grid[j][i] = 1;
			}
		}
	}
	//入力を受けとり完了
	
	//関数を呼び出し
	int res = bfs();
	
	if (res == 0) { //右下に辿り着けなかったなら
		cout << -1 << endl; //-1を出力
	}
	else { //右下に辿り着けたなら
		cout << white - res << endl;
		//白マスの数 - 最短経路で通る白マスの数 を出力
	}
	
	return 0;
}

幅優先探索 の問題をさらに

動的計画法 DP

こちらのコンテストは、dpを学ぶ上で大切な問題などを26問集めたコンテストです。このコンテストの問題などを使用して、dpについて解説していきます。

chminとchmax (下のコード) を使用します。
chmin(a,b) と書くと、aのほうが大きい場合は aがbになり、そうでないなら、何も変わらない。
chmax なら、その逆です。

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

---

DPとは問題をさらに 細かい問題に分解 して、その細い問題をすべて解くことによって、大元の問題の答えを出すというアルゴリズムです。

下の動画がわかりやすいです。

evima さん ありがとうございます。

---

DPまとめコンテスト A - Frog 1

---

問題文
$N$ 個の足場があります。 足場には $1,2,…,N$ と番号が振られています。 各$i(1≤i≤N)$ について、足場 $i$ の高さは $h_i$です。
最初、足場 1 にカエルがいます。 カエルは次の行動を何回か繰り返し、足場 $N$ まで辿り着こうとしています。
足場 $i$ にいるとき、足場 $i+1$ または $i+2$ へジャンプできます。 このとき、ジャンプ先の足場を $j$ とすると、コスト $|h_i​ − h_j|$を支払います。
カエルが足場 $N$ に辿り着くまでに支払うコストの総和の最小値を求めてください。

制約
入力はすべて整数である。
$2≤N≤10^5$
$1≤h_i​≤10^4$

入力例1を例にこの問題について考えてみましょう。

入力例1

4
10 30 40 20

さっき、DP とは問題をさらに細かい問題に分解して、その問題を解くことで大元の問題を解くアルゴリズムだといいました。
この問題も、さらに細かい分解に分解してみましょう。

大元の問題は、足場1 から 足場4 に移動するのに支払うコストの最小値を求めるというものです。その問題を 足場1 から 足場2, 足場3, 足場4 に移動するのに支払うコストの最小値を求めるという問題に分解してみます。
(下は状況を説明する図です。)

まずは、足場1 から 足場2 に移動するのに支払うコストの最小値を求めてみましょう。足場1 から 足場2 に移動するコストの $20$ が最小値になります。

その次に、足場1 から 足場3 に移動するのに支払うコストの最小値を求めてみましょう。
足場1 から 足場3 に直接移動するコストは $30$ です。
足場2 から 足場3 に移動するコストは、 足場2 まで移動するコストを加えて $20 + 10$ で $30$ です。
どちらも同じなので、足場1 から 足場3 に移動するコストの最小値は $30$ となります。

最後に、足場1 から 足場4 に移動するのに支払うコストの最小値を求めてみましょう。
足場3 から 足場4 に移動するコストは、足場3 まで移動するコストを加えて、 $30 + 20$ で $50$ です。
足場2 から 足場4 に移動するコストは、足場2 まで移動するコストを加えて、 $20 + 10$ で $30$です。
足場2 から 足場4 に移動するコストの方が小さいので、足場1 から 足場4 に移動するコストの最小値は $30$ となります。

---

このように、細かい問題に分解することによって、この問題は解くことができます。

上のような処理を実装するには、$n+10$個の要素がある配列 dp を用意して、$dp[i-1]$ に 足場$i$ に移動するコストの最小値を代入していけば良いです。
(+10 しているのは、RE を防ぐためです。)

正答例 （配るDPという）

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
template<typename T> inline bool chmin(T & a, T b) {
	if (a > b) a = b; else return false; return true;
}
template<class T> inline bool chmax(T & a, T b) {
	if (a < b) a = b; else return false; return true;
}

int main(void) {
	int n;
	cin >> n;
	long long h[n + 10], dp[n + 10];
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		dp[i] = 1e15;
	}
	
	dp[0] = 0;
	//スタート地点へ行くコストは0なので、 dp[0] = 0;
	
	for (int i = 0; i < n; i++) {
		chmin(dp[i + 1] , dp[i] + abs(h[i] - h[i + 1]));
		//今までに判明している、最小のコストで足場i + 1に行く方法と、
		//今いる足場iから、足場i + 1に行く方法の
		//小さい方を dp[i + 1] に代入する
		chmin(dp[i + 2] , dp[i] + abs(h[i] - h[i + 2]));
		//今までに判明している、最小のコストで足場i + 2に行く方法と、
		//今いる足場iから足場i + 2に行く方法の
		//小さい方を dp[i + 2] に代入する
	}
	cout << dp[n - 1]<<endl;
	//最小のコストでゴールに行く方法を出力する
}

貰うDP・集めるDP という方法での解法

DPまとめコンテスト D - Knapsack 1

---

問題文$N$ 個の品物があります。 品物には $1,2,…,N$ と番号が振られています。 各 $i (1≤i≤N)$ について、品物 $i$ の重さは $w_i$で、価値は $v_i$ です。
太郎君は、$N$ 個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。 ナップサックの容量は $W$ であり、持ち帰る品物の重さの総和は $W$ 以下でなければなりません。
太郎君が持ち帰る品物の価値の総和の最大値を求めてください。

制約
入力はすべて整数である。
$1≤N≤100$
$1≤W≤10^5$
$1≤w_i≤W$
$1≤v_i≤10^9$

この問題も、入力例1を例にこの問題について考えてみましょう。

入力例1 (価値を1/10にしています)

3 8
3 3
4 5
5 6

この問題は、重さの総和が $8$ 以下になるように品物を選んだときの、その品物の価値の総和の最大値を求めるという問題です。
この問題を、$i$ までの品物を重さの総和が$w$ 以下になるように選んだとき、品物の価値の総和の最大値はいくつになるか という問題に分解します。

下の図は、横軸が$w$ で、縦軸が$i$を表しています。

まずは、$i = 1$ の場合を考えてみましょう。
1品目の重さは 3 なので、 $3 \leqq w$ の所は、1品目の価値の 3 になります。

次は、$i = 2$ の場合を考えてみましょう。
2品目の重さは 4 で、 価値は 5 です。

$w < 3$ なら 何も選べないので 0 で、
$w = 3$ なら 1品目のみが選べるので 3 で、
$4 \leqq w \leqq 6 $ なら、2品目を選んだほうが、1品目を選ぶよりも価値の総和が大きいので 5 で、
$7 \leqq w$ なら、2品両方を選べるので、1品目と2品目の価値の和の 8 です。

最後に、$i = 3$ の場合を考えてみましょう。
3品目の重さは 5 で、 価値は 6 です。

$w < 3$ なら 何も選べないので 0 で、
$w = 3$ なら 1品目のみが選べるので 3 で、
$w = 4$ なら、2品目を選んだほうが、1品目を選ぶよりも価値の総和が大きいので 5 で、
$4 \leqq w \leqq 5$ なら、3品目を選んだほうが、他の品物を選ぶよりも価値の総和が大きいので 6 で、
$w = 7$ なら、1品目と2品目を選ぶ場合が最も価値の総和が大きいので 8 で、
$w = 8$ なら、1品目と3品目を選ぶ場合が最も価値の総和が大きいので 9 で、
$9 \leqq w \leqq 11$ なら、2品目と3品目を選ぶ場合が最も価値の総和が大きいので 11 で、
$12 \leqq w$ なら、すべての品物を選ぶ場合が最も価値の総和が大きいので 14 です。

---

この問題は、重さの総和が $8$ 以下になるように品物を選んだときの、その品物の価値の総和の最大値を求めるという問題でした。
図でいう、$i= 3,w = 8$ のところが答えになります。

なので、赤で囲まれた $9$ が答えです。

---

上のような処理を実装するには、 $dp[n+10][w+10]$ という二次元配列 dp を用意して、$dp[i-1][sum]$に、 $i$ 番目までの品物を総和が $sum$ 以下になるように選んだときの価値の総和の最大値を代入していけばよいです。
(+10 しているのは、RE を防ぐためです。)

正答例

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
template<typename T> inline bool chmin(T & a, T b) {
	if (a > b) a = b; else return false; return true;
}
template<class T> inline bool chmax(T & a, T b) {
	if (a < b) a = b; else return false; return true;
}

int main(void) {
	int n, w;
	cin >> n >> w;
	long long weight[n + 10], value[n + 10], dp[n + 10][w + 10];
	for (int i = 0; i < n; i++) {
		cin >> weight[i] >> value[i];
		for (int j = 0; j <= w; j++) {
			dp[i][j] = 0;
		}
	}
	
	for (int i = 0; i < n; i++) {
		for (int sum = 0; sum <= w; sum++) {
			
			//i + 1番目を選ぶことができ、選ぶ場合
			if (sum - weight[i] >= 0) {
				chmax(dp[i + 1][sum] , dp[i][sum - weight[i]] + value[i]);
				//同じ重さ、同じ品物の範囲で、価値の総和が大きい方を dp[i + 1][sum]に代入する
			}
			
			//i + 1を選ばない場合、dp[i + 1][sum] = dp[i][sum]といえる
			chmax(dp[i + 1][sum], dp[i][sum]);
			//価値の総和が大きい方を dp[i + 1][sum]に代入する
			
		}
	}
	cout << dp[n][w] << endl;
}

解説に @drken さん の この記事 を参考にさせていただきました。
ありがとうございます。

動的計画法（DP） の問題をさらに

区間DP

区間DPとは、 区間を表す添え字を持つDP のことです。

DPまとめコンテスト L - Deque

---

問題文を言い換えています。

問題文
太郎君と次郎君が次のゲームで勝負します。
最初に、整数の書かれた$N$枚のカード$a_1​,a_2,…,a_N$ が与えられます。
カードが0枚になるまで、二人は次の操作を交互に行います。 先手は太郎君です。
ルール
$a$の先頭のカード、または末尾のカードを取り除く。 取り除いたカードに書かれた整数を $x$ とすると、操作を行った人は $x$ 点を得る。

ゲーム終了時の太郎君の総得点を $X$、次郎君の総得点を $Y$ とします。 太郎君は$X−Y$ を最大化しようとし、次郎君は $X−Y$ を最小化しようとします。
二人が最適に行動すると仮定したとき、$X−Y$ を求めてください。

制約
入力はすべて整数である。
$1≤N≤3000$
$1≤a_i≤10^9$

問題文を言い換えると、$自分の点 - 相手の点$ を大きい値にするために、$a$の先頭か末尾を取り除いていくということです。

この問題は、先頭と末尾の要素の大きい方を取り除けば良いというわけではありません。
$(20, 100, 50, 10)$ という4枚のカードが与えられたとします。
要素の大きい方を必ず取り除いてみて試してみましょう。

• 太郎君が20を取り除く
• 次郎君が100を取り除く
• 太郎君が50を取り除く
• 次郎君が10を取り除く

結果は、太郎君70点、次郎君が110点となります。
しかし、この例では、

• 太郎君が10を取り除く
• 次郎君が50を取り除く
• 太郎君が100を取り除く
• 次郎君が20を取り除く

という方法が最善の選択になります。

---

この問題では、 $dp[l][r]$ を $l$ ~ $r$ 枚目のカード があるときの手番のプレイヤーのスコアの最大値とします。
カードの枚数が少ないときの最大値を求めて、その後にカードの枚数が多いときの最大値を求めていくことによって、この問題は解くことができます。

---

入力例1 への処理について考えてみましょう。

入力例1

4
10 80 90 30

まずは、下の処理でどうなるかを考えてみましょう。

cin >> a[i];
dp[i][i] = a[i];

という処理を行うと、 $dp[i][i]$ の値は下のようになります。

• $dp[1][1] = 10$
  • 1枚目のカードに書かれた整数は 10 です。
  • カードが1枚ということは、先手のみが操作を行えるということで、先手の得点$X$に 10 が加算されて、 $X - Y$ の値は 10 になります。
• $dp[2][2] = 80$
  • 2枚目のカードに書かれた整数は 80 です。
  • カードが1枚ということは、先手のみが操作を行えるということで、先手の得点$X$に 80 が加算されて、 $X - Y$ の値は 80 になります。
• $dp[3][3] = 90$
  • 3枚目のカードに書かれた整数は 90 です。
  • カードが1枚ということは、先手のみが操作を行えるということで、先手の得点$X$に 90 が加算されて、 $X - Y$ の値は 90 になります。
• $dp[4][4] = 30$
  • 4枚目のカードに書かれた整数は 30 です。
  • カードが1枚ということは、先手のみが操作を行えるということで、先手の得点$X$に 30 が加算されて、 $X - Y$ の値は 30 になります。

---

次はこの処理について考えてみましょう。

dp[l][r] = max(a[l] - dp[l + 1][r] , a[r] - dp[l][r - 1]);

2枚のカードの場合

• $dp[1][2] = max(10 - 80, 80 - 10) = 70$
  • 1枚目のカードに書かれた整数は 10 で、 2枚目のカードに書かれた整数は 80 です。
  • 先手が 1枚目のカード を選んだ場合と、 2枚目のカード を選んだ場合で $X - Y$ の値が大きくなる方を $dp[1][2]$ に代入します。
• $dp[2][3] = max(80 - 90, 90 - 80) = 10$
  • 2枚目のカードに書かれた整数は 80 で、 3枚目のカードに書かれた整数は 90 です。
  • 先手が 2枚目のカード を選んだ場合と、 2枚目のカード を選んだ場合で $X - Y$ の値が大きくなる方を $dp[2][3]$ に代入します。
• $dp[3][4] = max(90 - 30, 30 - 90) = 60$
  • 3枚目のカードに書かれた整数は 90 で、 4枚目のカードに書かれた整数は 30 です。
  • 先手が 3枚目のカード を選んだ場合と、 4枚目のカード を選んだ場合で $X - Y$ の値が大きくなる方を $dp[3][4]$ に代入します。

3枚のカードの場合

• $dp[1][3] = max(10 - 10, 90 - 70) = 20$

先手の1ターン目で 1枚目のカード を選ぶ場合、$X$ に 1枚目のカードに書かれた 10 を加えます。その次に、次郎君を先手と考えると、$dp[2][3]$ の値が、$次郎君の1ターン目 - 太郎君の2ターン目$ の値になります。

$a[1] - dp[2][3] = 太郎君の1ターン目 - (次郎くんの1ターン目 - 太郎君の2ターン目) = 太郎君の1ターン目 - 次郎くんの1ターン目 + 太郎君の2ターン目$ となり、$a[1] - dp[2][3] = X - Y$ の値になります。

先手の1ターン目で 3枚目のカード を選ぶ場合、$X$ に 3枚目のカードに書かれた 90 を加えます。その次に、次郎君を先手と考えると、$dp[1][2]$ の値が、$次郎君の1ターン目 - 太郎君の2ターン目$ の値になります。

$a[3] - dp[1][2] = 太郎君の1ターン目 - (次郎くんの1ターン目 - 太郎君の2ターン目) = 太郎君の1ターン目 - 次郎くんの1ターン目 + 太郎君の2ターン目$ となり、$a[3] - dp[1][2] = X - Y$ の値になります。

そして、その2つの $X - Y$ の大きい方を dp[1][3] に代入しています。

dp[l][r] = max(a[l] - dp[l + 1][r] , a[r] - dp[l][r - 1]);

という処理は、即ち $l$ ~ $r$ 枚目のカードがあるとき、 先手の1ターン目に $l$ 枚目のカードを選ぶ場合と、 $r$ 枚目のカードを選ぶ場合で、$X - Y$ の値が大きくなる方を $dp[l][r]$ に代入するというものです。

• $dp[2][4] = max(80 - 60, 30 - 10) = 20$

これも、上と同じような処理を行っています。

すべてのカードの場合

• $dp[1][4] = max(10 - 20, 30 - 20) = 10$

これも、上と同じような処理を行っています。

答えは、 $dp[1][n] = dp[1][4] = 10$ となります。

正答例

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
template<typename T> inline bool chmin(T & a, T b) {
	if (a > b) a = b; else return false; return true;
}
template<class T> inline bool chmax(T & a, T b) {
	if (a < b) a = b; else return false; return true;
}

int main(void) {
	int n;
	cin >> n;
	vector<long long> a(n + 10);
	vector<vector<long long> > dp(n + 10, vector<long long>(n + 10));
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		dp[i][i] = a[i];
	}
	
	//DPスタート
	for (int wid = 1; wid <= n + 1; wid++) { //wid = 幅
		for (int l = 1; l <= n - wid; l++) { // l = 左
			int r = wid + l; //r = 右 = l + wid
			
			dp[l][r] = max(a[l] - dp[l + 1][r] , a[r] - dp[l][r - 1]);
			//左を取った場合と右を取った場合の大きい方を dp[l][r] に代入
		}
	}
	cout << dp[1][n] << endl;
}

区間DP の問題をさらに

bitDP

bitDPとは、 ビットで表現した集合を添え字に持つDP のことです。

DPまとめコンテスト O - Matching

---

$N$ 人の男性たちと $N$ 人の女性たちがいます。 男性たちには $1,2,…,N$ と番号が振られています。 同様に、女性たちには $1,2,…,N$ と番号が振られています。
各 $i,j (1≤i,j≤N) $について、男性 $i$ と女性 $j$ の相性の良し悪しが整数 $a_i,_j$によって与えられます。
$a_i,_j =1$ ならば男性 $i$ と女性 $j$ は相性が良く、$a_i,_j =0$ ならば相性が悪いです。
太郎君は、相性が良い男女どうしのペアを $N$ 組作ろうとしています。 このとき、各男性および各女性はちょうど 1 つのペアに属さなければなりません。
$N$ 組のペアを作る方法は何通りでしょうか？ $10^9+7$ で割った余りを求めてください。

制約
入力はすべて整数である。
$1≤N≤21$
$a_i,_j$は $0$ または $1$ である。

男性の方は固定して、女性について考えます。
プログラムでいう、 $c$ の値が、どの男性について考えているのかを表しています。そして、$j$の値が、どの女性について考えているのかを表しています。

---

このコードでは、i桁目のビットが立っている = i番目の女性がペアになれているということです。

例えば、 i = 1 のときについてを考えてみましょう。
男性0 と 女性0 がペアになったことを 001 が表しています。(0桁目が 1 だから)
~i & (1<<j) というコードによって、男性1 と 女性1 がペアになるのを防いでいます。(女性1はすでにペアになっているから)

この状態から、 男性1 と 女性2 がペアになったとしましょう。
女性2 がペアになったので、001 の2桁目を 1 として、女性2と男性2 がペアになることを防ぐ必要があります。

2進数での j桁目 を 1 にするには、 10進数での (1<<j) つまり、$2^j$ を元の2進数の数に加える必要があります。
i = 1のときについてを考えていて、001の2桁目を1にしたいのだから、 (1<<2) を i に加えて、10進数でいう i = 5 つまりは、 101 にします。

そして、 001 の状態から 101 になる組み合わせをプラスするdp[i + (1 << 2)] += dp[i] というコードでこの問題は解くことができます。

入力例1の場合の動作

入力例1

3
0 1 1
1 0 1
1 1 1

• i = 0 (000)
• 誰もペアになっていない
  • c = 0 (男性0について考える)
  • j = 0
    • 男性0 と 女性0 は 相性が良くない
  • j = 1
    • dp[2] += dp[0] (dp[0] = 1)
    • 男性0 と 女性1 がペアになり、010 (10進数で2)という状態になった。
    • 以下も同様にいえる
  • j = 2
    • dp[4] += dp[0] (dp[0] = 1)
• i = 1 (001)
• つまり、男性0 と 女性0 はペア
  • c = 1
  • j = 0
    • すでにペアになっている人を含んでいる
  • j = 1
    • 男性1 と 女性1 は相性が良くない
  • j = 2
    • dp[5] += dp[1]
    • dp[5] == 0
• i = 2 (010)
• つまり、男性0 と 女性1 はペア
  • c = 1
  • j = 0
    • dp[3] += dp[2]
    • dp[3] == 1
  • j = 1
    • すでにペアになっている人を含んでいる
    • 男性1 と 女性1 は相性が良くない
  • j = 2
    • dp[6] += dp[2]
    • dp[6] == 1
• i = 3 (011)
• つまり、 ペアになっていないのは 男性2 と 女性2
  • c = 2
  • j = 0
    • すでにペアになっている人を含んでいる
  • j = 1
    • すでにペアになっている人を含んでいる
  • j = 2
    • dp[7] += dp[3]
    • dp[7] == 1
• i = 4 (100)
• つまり、男性0 と 女性2 はペア
  • c = 1
  • j = 0
    • dp[5] += dp[4]
    • dp[5] == 1
  • j = 1
    • 男性1 と 女性1 は相性が良くない
  • j = 2
    • すでにペアになっている人を含んでいる
• i = 5 (101)
• つまり、 ペアになっていないのは 男性2 と 女性1
  • c = 2
  • j = 0
    • すでにペアになっている人を含んでいる
  • j = 1
    • dp[7] += dp[5]
    • dp[7] == 2
  • j = 2
    • すでにペアになっている人を含んでいる
• i = 6 (110)
• つまり、 ペアになっていないのは 男性2 と 女性0
  • c = 2
  • j = 0
    • dp[7] += dp[6]
    • dp[7] == 3
  • j = 1
    • すでにペアになっている人を含んでいる
  • j = 2
    • すでにペアになっている人を含んでいる
• i = 7 (111)
• 全員がすでにペア

dp[7] (つまり3) を出力する。

正答例

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
const int mod = 1000000007;
int a[22][22], dp[1 << 22];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
	dp[0] = 1;
	
	//bitDP
	for (int i = 0; i<(1 << n);i++) { //2 ^ n の状況について試す
		int c = 0;
		for (int j = 0; j < n; j++) if (i & (1 << j)) c++;
		//i に含まれる 1 の数 = c;
		// つまりは、考える対象の男性は c になる。
		
		for (int j = 0; j < n; j++) { //すべての女性とペアになれるか試す
			if (~i & (1 << j) && a[c][j]) {
				//女性jがまだペアになっていない
				// かつ 男性c と 女性j の 相性がいいなら
				
				dp[i + (1 << j)] += dp[i];
				// i+(i << j) という状況のときの組み合わせの数に
				//i+(i << j) の１つ前の状況(dp[i])の組み合わせの数を加える
				
				dp[i + (1 << j)] %= mod; //毎回割る
				
			}
		}
	}
	cout << dp[(1 << n) - 1]<<endl;
}

bitDP の問題をさらに

ダイクストラ法

重さに負のコストの辺が ない 場合によく使われる、単一始点最短経路問題を解くアルゴリズムです。priority_queue を使用します。

もし、負のコストがある場合は、ベルマン・フォード法を使用することが多いです。

GRL_1_A 単一始点最短経路

---

与えられたグラフ $G=(V,E)$と始点 $r$について、単一始点最短経路の重みを求めるプログラムを作成してください。
$G$のノード $r$を始点とし、$r$から各ノードについて、最短経路上の辺の重みの総和を出力してください。
入力
$|V| \ |E| \ r$
$s_0 \ t_0 \ d_0$
$s_1 \ t_1 \ d_1$
:
$s_{|E| −1} \ t_{|E|−1} \ d_{|E|−1}$

$|V|, |E|$はそれぞれグラフ $G$の頂点の数と辺の数を示す。
グラフ $G$の頂点にはそれぞれ $0,1,...,|V|−1$の番号が付けられている。
$r$は始点の番号である。
$s_i, t_i$はグラフ $G$の $i$番目の辺が結ぶ２つの頂点を表す（有向）。
$d_i$は $i$番目の辺の重みである。

この問題は、それぞれの頂点に辿り着くための最小の重さを調べていくことによって、解いていくことができます。

このコードは、#define を使用しています。

正答例

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

#define int long long
#define pa pair<int, int>
//pa = pair , int = long long と定義
int V, E, r, s, t, d;

signed main() {
	cin >> V >> E >> r;
	vector< pair<int, int> > graph[100001];
	for (int i = 0; i < E; i++) {
		cin >> s >> t >> d;
	graph[s].push_back({t, d});
		//sがtとつながっていて、その辺の重みはd だと記録する
	}
	//入力を受け取った
	
	priority_queue< pa, vector<pa>, greater<pa> > que;
	//常に降順に並び替えられるqueueを定義
    que.push({0, r}); //スタート地点rにコスト0の状態でいることを表す
	
	vector<int> dist(100001);
	for (int i = 0; i < 100001; i++) {
		dist[i] = 1e10;  //重さを最大にしておく
	}
	dist[r] = 0;
	//スタートの頂点までの重さを0にする
	
	while (!que.empty()) {
		int now_dist = que.top().first, now_vertex = que.top().second;
		//queの要素を読み込んでおく
		que.pop();
		
		if (dist[now_vertex] < now_dist) {
			//もし 今いる場所までの重さ よりも 今の重さ の方が大きいならば
			//つまり、非効率な方法で今の場所に来たならば
			continue;
		}
		
		for (int i = 0; i < graph[now_vertex].size();i++) {
			int next_vertex = graph[now_vertex][i].first;
			//次に行くことのできる頂点(頂点x) の番号を代入する
			
			int next_dist = now_dist + graph[now_vertex][i].second;
			//今までの重みと、頂点x への辺の重みの和を代入する
			
			if (dist[next_vertex] > next_dist) {
				//次のマスまでの重さ よりも 今回試している重さのほうが小さいならば
				//つまりは、もっと効率よく行く方法がなければ
				
				dist[next_vertex] = next_dist;
				//頂点x までの重さを記録する
				
			que.push({next_dist, next_vertex});
				//頂点x までの重さと、頂点xの番号をqueに挿入する
				//queの中で自動で重さ順に並び替えられる
			}
		}
	}
	for (int i = 0; i < V; i++) {
		if (dist[i] < 1e10) {
			cout << dist[i] << endl;
            //i番目の点までの重さを出力
		}
		else {
			cout << "INF" << endl;
            //辿り着けないなら、INFと出力
		}
	}
}

ダイクストラ法 の問題をさらに

ワーシャルフロイド法

全頂点対間の最短経路長を$O(N^3)$で計算するアルゴリズムです。
また、負のコストの辺があっても使用することができます。

GRL_1_C 全点対間最短経路

---

重み付き有向グラフ $G=(V,E)$の全点対間最短経路の距離を列挙してください。

入力
入力は以下の形式で与えられます。
$|V| \ |E|$
$s_0 \ t_0 \ d_0$
$s_1 \ t_1 \ d_1$
:
$s_{|E|−1} \ t_{|E|-1} \ d_{|E|-1}$

$|V|, |E|$はそれぞれグラフ $G$の頂点の数と辺の数を示します。グラフ $G$の頂点はそれぞれ $0,1,...,|V|−1$の番号が付けられているものとします。
$s_i, t_i, d_i$はグラフ $G$の $i$番目の辺が結ぶ（有向）２つの頂点の番号とその重みを表します。

DP的な考えで、この問題は解くことができます。
点 j から点 k に直接行くのと、点 j から 点 i を経由して 点 k に行く方法の主さが小さい方を 点 j から 点 k に行く重さとして記録して、解くことができます。

例えば、下の図の場合は、点j から 点k への重みは 10 ですが、点i を経由すると、$3 + 5$ で 8 になります。
なので、点j から 点k への重みは 8 と記録します。

このコードは、#define を使用しています。

正答例

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
#define int long long
const long long INF = (1LL << 32);

signed main(void) {
	int V, E;
	cin >> V >> E;
	int graph[V][V];
	//頂点の数*頂点の数 の二次元配列を用意
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			if (i != j) { //iとjが異なるなら
				graph[i][j] = INF;
			}
			else {
				graph[i][j] = 0;
			}
		}
	}
	for (int i = 0; i < E; i++) {
		int s, t, d;
		cin >> s >> t >> d;
		graph[s][t] = d;
		//sとtを結ぶ辺の重さを記録する
	}
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			for (int k = 0; k < V; k++) { //DPのように
				graph[j][k] = min(graph[j][k] , graph[j][i] + graph[i][k]);
				//jとkを結ぶ辺の長さと
				//jとiを結ぶ辺の長さとiとkを結ぶ辺の長さの和(つまり、iを経由)
				//小さい方をjからkに移動する重さとして記録する
			}
		}
	}
	
	for (int i = 0; i < V; i++) {
		if (graph[i][i]<0) {
			//iからiに戻ってくる時、重さが負になるなら
			cout << "NEGATIVE CYCLE" << endl;
			return 0;
		}
	}
	for (int i = 0; i < V; i++) {
		for (int j = 0; j < V; j++) {
			if (j != 0) cout << " "; //空白空け
			
			if (graph[i][j] >= INF / 2) cout << "INF";
			//辿り着けないなら、INFと出力
			
			else cout << graph[i][j];
			//そうでなければ、iからjへの行き方の重さを出力する
		}
		cout << endl;
	}
}

ワーシャル・フロイド法 の問題をさらに

クラスカル法

クラスカル法とは、最小全域木を求めるアルゴリズムです。
そもそも、最小全域木とは、

• すべての頂点を含む
• 辺のコストの和が最小
  という条件を満たしている木のことです。

このクラスカル法は、

• 辺の集合をコストの小さい順にソートする
• 以下の処理を最小全域木ができるまで繰り返す
  • 残っている辺でコストの最小な辺を取り出し、その辺を木に加えても閉路ができないならば、その辺を木に追加する。
    という処理を行うアルゴリズムです。

(閉路ができる というのは、グラフに輪ができる ということです。)

GRL_2_A 最小全域木

---

与えられた重み付きグラフ G = (V, E) に対する最小全域木の辺の重みの総和を計算するプログラムを作成してください。
入力
$|V| \ |E|$
$s_0 \ t_0 \ w_0$
$s_1 \ t_1 \ w_1$
:
$s_{|E|-1} \ t_{|E|-1} \ w_{|E|-1} $

$|V|, |E|$ はそれぞれグラフ $G$ の頂点の数と辺の数を示します。グラフ $G$ の頂点にはそれぞれ $0, 1, ..., |V|-1$ の番号が付けられています。
$s_i, t_i$ はグラフ $G$ の $i$ 番目の辺が結ぶ２つの頂点を表します（無向）。$w_i$ は $i$ 番目の辺の重みです。

正答例

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.
struct edge {int from, to, cost;};
bool operator < (const edge & a, const edge & b) {
	return a.cost < b.cost;
}

vector<edge> graph;
int parents[100000];

int parent(int x) {
	if (parents[x] == x) return x;
	return parents[x] = parent(parents[x]);
	//親を返す関数
}
bool Union(int x, int y) {
	x = parent(x);
	y = parent(y);
	if (x == y) return false;
	//違うグループなら、同じグループにする
	parents[x] = y;
	return true;
}

int main(void) {
	int V, E;
	cin >> V >> E;
	for (int i = 0; i < V; i++) parents[i] = i;
	for (int i = 0; i < E; i++) {
		int s, t, w;
		cin >> s >> t >> w;
	graph.push_back((edge) {s, t, w});
	}
	
	sort(graph.begin(), graph.end());
	//costで昇順にソートする
	
	int ans = 0;
	for (int i = 0; i < graph.size();i++) {
		edge e = graph[i];
		
		if (Union(e.from, e.to)) {
			ans += e.cost;
		}
		//eという辺の始点と終点を同じグループに併合して、その辺のコストを加える
	}
	cout << ans << endl;
}

クラスカル法（最短全域木） の問題をさらに

べき乗・逆元などの高速計算

上の記事がとてもわかり易いです。

素数2つ

(これはメモです。)

素数1

998244353

素数2

1000000007

求める数を 素数 で割ったあまりを出力する。 というタイプの問題の解き方などをまとめます。

素数で割るのは、答えの桁数がかなり多くなってしまい、C++などの言語だと答えがオーバーフローしてしまう場合があるからです。
そして、そのような問題を解くには、 計算の途中にもあまりを取る ということがとても重要になってきます。

オーバーフロー について

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

int main() {
	long long a = 123456789;
	long long b = 987654321;
	long long c = 4928751603;
	const long long mod = 1000000007;
	long long result;
	
	cout << "掛け算/随時割る" << endl;
	result = (((a * b) % mod) * c) % mod;
	cout<< result <<endl;
	cout << "掛け算/まとめて割る" << endl;
	result = (a * b * c) % mod;
	cout<< result << "\n\n";
	
	return 0;
}

というコードを実行すると

実行結果

掛け算/随時割る
705031618
掛け算/まとめて割る
606685091

となります。
正しいのは、705031618 です。
なぜ、掛け算の結果をまとめて割る 方が誤った解答になるのかというと、 a * b * c という計算をした時点で、 long long という型に収まらなくなってしまったからです。(long long の最大値 = 9,223,372,036,854,775,807 )

足し算・足し算では、途中にあまりを取ることは簡単なのですが、
引き算・割り算 では、途中にあまりを取るときに注意すべきことがあります。

---

引き算の際は、計算結果が負の数になるときに注意する必要があります。
例えば $ -17 \div 5$ のあまりは $3$ が正しい計算結果なのですが、
(あまりは 余剰なので、$ -20 \div 5$ のあまりの 0 に3を加えたものになる)
C++では、 -2 となってしまいます。
これを直すには、割る数をあまりに加えればよいです。
$-2 + 5 = 3$ で正しい計算結果になります。

実験

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

int main() {
	long long a = 1234567890;
	long long b = 987654321;
	long long c = 4928751603;
	const long long mod = 1000000007;
	long long result;
	
	cout << "引き算/直さない" << endl;
	result = (((a - b) % mod) - c) % mod;
	cout<< result <<endl;
	cout << "引き算/マイナスを直す" << endl;
	result = (((a - b) % mod) - c) % mod;
	if (result < 0) result += mod;
	cout<< result <<"\n\n";
}

出力結果

引き算/直さない
-681838006
引き算/マイナスを直す
318162001

割り算のあまり

割り算では、簡単にあまりを取ることができません。
しかし、あまりを取るのが不可能なわけではありません。
$p$を素数として、 $mod \ p$ の世界における割り算について考えてみます。
例えば $mod \ 13$ について考えてみます。
$9 \div 4 $ は、普通の世界では割り切れませんが、$mod \ 13$ の世界では
$9 \div 4 \equiv 12 (mod \ 13)$ となります。
これは、$4 \times 12 = 48 \equiv 9 (mod \ 13)$ が成り立つからです。
(48を13で割ったあまりは、 $48 - 13 \times 3 = 48 - 39 = 9$)

---

$p$を素数、$b$を$p$で割り切れない整数とします。このとき、$a$を整数として、
$bx \equiv a (mod \ p) $
を満たすような $x$ は、一意に存在するということがいえます。

---

$a \div b (mod \ p)$ を計算する方法を考えます。
まず、 $a \div b \equiv a \times (1 \div b) (mod \ p)$ が成り立つので、
$1 \div b (mod \ p)$ だけ計算できればよいです。
そして、 $1 \div b$ を $mod \ p$における $b$ の 逆元 といいます。
$b$の逆元は $b^{-1}$ と表記されることが多いです。
$mod \ p$ での$b$の逆元が存在する条件は、 $p$と$b$が 互いに素 でことです。

まとめると、
$a \div b \equiv a \times b^{-1} (mod \ p)$ （ a × bの逆元 ）
となります。

ここから後には、逆元の計算の仕方をまとめていきます。

---

１つ目の逆元の計算の仕方は、フェルマーの小定理を使います。
フェルマーの小定理とは、

$p$ を素数、$a$ を $p$ の倍数でない整数として

$a^{p-1} \equiv 1 \pmod{p}$

が成立する。 という定理です。
$p = 5$ で確かめてみると、

• $1^{5-1} = 1^4 = 1 \equiv 1 (mod \ 5) $
• $2^{5-1} = 2^4 = 16 \equiv 1 (mod \ 5) $
• $3^{5-1} = 3^4 = 81 \equiv 1 (mod \ 5) $

となります。
式を変形すると、

$ a \times a^{p-2} \equiv 1 (mod \ p)$

となります。
これは、 $a^{-2}$ が $a$ の逆元になっています。

---

2つ目は拡張 Euclid の互除法 を使います。
$x$ が$mod \ p$ における $a$ の逆元であるとは、
$ax \equiv 1 (mod \ p)$ が成立し、つまり
$ax + py = 1$ を満たすyが存在します。

そして、$x$ を求めるには 拡張 Euclid の互除法 を使えます。

拡張 Euclid の互除法 は

---

互いに素な2整数$a,b$ が与えられたとき、
$ax + by = 1$
を満たす$x,y$ を1つ求める

---

ことができます。

実装

#include <iostream>
using namespace std;

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m; 
	if (u < 0) u += m;
	return u;
}

int main() {
	// mod. 13 での逆元を求めてみる
	for (int i = 1; i < 13; ++i) {
		cout << i << " 's inv: " << modinv(i, 13) << endl;
	}
}

@drken さん作成のコードです。

---

その他

高速な累乗の計算

累乗の計算をする際に、愚直に計算すると $O(n)$ 回の計算が必要ですが、 高速な累乗の計算法 を使用することによって、 $O(\log n)$にできます。
(二分累乗法 と呼ばれます)

例えば $3^{45}$ を $ 1000000007$ で割ったあまりを求めたいとします。
45を二進数にすると、 00101101,
つまりは、 $2^0 + 2^2 + 2^3 + 2^5 = 45$ となります。なので、

3^{45} = 3^{2^0} \times 3^{2^2} \times 3^{2^3} \times 3^{2^5}

となります。

下のコードにある a = a * a % mod という部分は、繰り返されると、aが$2^0 ,2^1,2^2,...$ となっていきます。つまり、 a は 指数の役割になっています。

例で確認した通り、何も操作していないbの2進数表記の n桁目が1 なら、 $3^{2^n}$ が式に含まれていることを表しています。 bは右にシフトしていくので、 bの0桁目が1 のときに、数をかけることを繰り返せば、答えが求められます。

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

long long func(long long a, long long b, long long mod){
  long long res = 1;
	while(b > 0){ // b = 1 がラスト
	  //もし、bの0桁目が 1 ならば 
		if(b & 1) res = res * a % mod;
		
		a = a * a % mod;
		//aを2乗していく
		
		b = (b >> 1);
		//奇数なら b / 2 - 1 , 偶数なら b / 2 する
	}
	return res; //結果を返す
}

int main(){
  cout<< func(3, 45, 1000000007) <<endl;
}

逆元を使用する問題

---

累積和

配列の 区間の総和 を簡単に求められるアルゴリズムのことです。

例えば $A ={1, 2, 3, 4, 5,...,50}$という数列があったとします。($A_0=1$)
この配列の 3番目の要素から45番目の要素の総和を求めるとき、1つずつ加えていって計算することもできますが、もっと高速に計算する方法があります。
$B_0 = 0 $
$B_1 = A_0 $
$B_2 = A_0 + A_1$
$B_{50} = A_0 + A_1 + A_2 + ... + A_{49}$
という配列を用意して、$B_{46} - B_3$ を求めるという方法です。
この方法は、 45番目までの総和から、2番目までの総和を引いています。

ABC084 D - 2017-like Number

---

「$N$も $(N+1)÷2$ も素数」を満たす奇数 $N$ を 2017に似た数 とします。
$Q$ 個のクエリが与えられます。
クエリ $i(1≦i≦Q)$ では奇数 $l_i,r_i$が与えられるので、$l_i≦x≦r_i$かつ 2017に似た数 となる奇数 $x$ の個数を求めてください。
制約
$1≦Q≦10^5$
$1≦l_i≦r_i≦10^5$
$l_i$,$r_i$は奇数
入力は全て整数

2017に似た数が、ある数以下に何個あるかを記録する配列を作ることによって、累積和を使うことができます。
また、nが素数であるかを高速に確かめる方法は、$2$から$\sqrt{n}$までの数で割る というもので、それで割り切れなければ素数であるといえます。

正答例

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

int main() {
	bool prime[100009];
	//素数かどうかを記録する配列
	for (int i = 2; i <= 100000; i++) {
		prime[i] = true;
		for (int j = 2; j * j <= i; j++) {
			if (i % j == 0) { //もしiがjで割り切れれば
				prime[i] = false;
				//素数ではないと記録する
				break;
			}
		}
	}
	int like[100009];
	int count = 0; //これまでにあった2017に似た数を記録する
	for (int i = 3; i <= 100000; i++) {
		if (prime[i] && prime[(i + 1) / 2]) {//もし2017に似た数ならば、
			count++; //2017に似た数の個数を+1する
		}
		like[i] = count;
		//これまでに2017に似た数がいくつあったか記録する
	}
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int l, r;
		cin >> l >> r;
		int ans = like[r] - like[l - 1];
		//累積和を用いて、lとrの間にある2017に似た数を求める
		cout << ans << endl;
	}
}

いもす法

区間の入口と出口で加算・減算を行い、累積和を求めて、任意の区間の要素数などを高速で求めることができるアルゴリズムです。

ABC183 D - Water Heater

---

この問題は、水の使用開始、終了時間と使用量を記録しておいて、いもす法を用いることによって解くことができます。

入力例1 への処理

入力例1

4 10
1 3 5
2 4 4
3 10 6
2 4 1

例えば、2行目の 時刻1 から 時刻3 の間に お湯を毎分 5L 使うということを表すと、下の画像のようになります。

他の行も同じようにまとめると、以下のようになります。

そして、この例の場合、毎分 10L お湯を供給できるので、

このようになって、供給量よりも使用量のほうが多くなっているので、計画どおりにお湯を供給するのは不可能で、 No というのが正解です。

正答例

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

int main(void) {
	long long n, w;
	cin >> n >> w;
	vector < long long> water(200010, 0);
	for (int i = 0; i < n; i++) {
		long long s, t, p;
		cin >> s >> t >> p;
		
		water[s] += p;
		//時刻sから水の使用量がp増えることを記録
		water[t] -= p;
		//時刻tでそれが終了することも記録
	}
	for (int i = 0; i < 200001; i++) {
		water[i + 1] += water[i];
		//sからtの間水を使用するため、
		//water[i + 1]のときの水の使用量はこのように表せる
		
		//水の使用量が供給量を上回ったなら
		if (water[i] > w) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}

競プロ典型90問 - 028 - Cluttered Paper（★4）

---

問題文
二次元平面上に $N$ 枚の長方形の紙があります。すべての紙は辺が $x$ 軸または $y$ 軸に平行に なるように配置されており、$i$ 枚目の紙の左下角の座標は $(lx_i​,ly_i)$ 、右上角の座標は $(rx_ i​,ry_ i​)$ です。
$k=1,2,3,…,N$ について、紙がちょうど $k$ 枚重なっている部分の面積を求めてください。

制約
$1≤N≤10^5$
$0≤lx_i<rx_i≤1000$
$0≤ly_i<ry_i≤1000$
入力は全て整数

こちらの問題は、いもす法を二次元配列に用います。
下の解説に載っている画像がとてもわかり易いです。

正答例

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

int main(void) {
	int n;
	cin >> n;
	vector<vector<int>> grid(1100, vector<int>(1100, 0));
	for (int i = 0; i < n; i++) {
		int lx, ly, rx, ry;
		cin >> lx >> ly >> rx >> ry;
		grid[lx][ly]++;
		grid[rx][ry]++;
		//四角の左下と右上を+1
		grid[rx][ly]--;
		grid[lx][ry]--;
		//四角の左上と右下を-1
	}
	for (int i = 0; i < 1001; i++) {
		for (int j = 1; j < 1001; j++) { //横方向の累積和
			grid[i][j] += grid[i][j - 1];
		}
	}
	for (int i = 1; i < 1001; i++) {
		for (int j = 0; j < 1001; j++) { //縦方向の累積和
			grid[i][j] += grid[i - 1][j];
		}
	}
	//ここまでの処理で、１つの四角形の中のマスが全て1になる
	//(重なっていた場合はそれよりも数が大きい)
	
	vector<int> ans(n + 1, 0);
	for (int i = 0; i < 1001; i++) {
		for (int j = 0; j < 1001; j++) {
			ans[grid[i][j]]++;
			//grid[i][j]からそのマスにいくつ四角形が重なっているかを取り出す
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << ans[i] << endl;
	}
}

累積和・いもす法 の問題をさらに

おわりに

この記事を書くにあたって、様々な方の存在が不可欠でした。
AtCoder アルゴ式 Aizu Online Judge の運営者さん , 問題のwriterさん , testerさん , アルゴリズムロジック さん , TheLogicalBear さん , じゃいごテック さん , はまやんはまやん さん , @e869120 さん , @drken さん , evima さん , @ofutonton さん @Pro_ktmr さん , Qiitaなどの記事の投稿者さん

そして、この記事を読んでいただいた皆様に 感謝申し上げます。

---

もし、誤った点などがあれば、コメントで指摘をお願いします。
この記事の続編も執筆する予定なので、ぜひよろしくお願いします！

1. 基本的な文法の理解 とは、ここでは 出入力や変数、配列、関数の理解ができている, if文, for文, while文 などを正しく記述できるなど の能力があることです。 ↩

2. C++ は 処理が高速 など、競技プログラミングをする上で良い点がたくさんあります。必ず C++ でないといけないというわけではありませんが、特別な理由がない限り、C++ を学ぶことをお勧めします。 ↩

3. これは、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン には取り上げられていませんが、この記事では取り上げました。 ↩