けんちょん本を読みながらプログラミングしてみたよ。

**[けんちょん本](https://www.amazon.co.jp/dp/4065128447)**を買って、読みながらいろいろプログラミングしてます。その一部を紹介します。

※この記事は私の自分用の日記みたいなものですので、読む価値があるかどうかはアレです。
※この記事における「過去問」とは、競技プログラミングサイトである**[AtCoder](https://atcoder.jp/)**の過去問のことです。
※この記事内のコードはいろいろとお作法が下手なので正直あちこち修正したい気持ちです、が実装当時の自分の実力の記録ってことで放置しています。

# 「二分探索法」の章を読んで過去問を解いた
解いてみた問題は「**[ABC174 E - Logs](https://atcoder.jp/contests/abc174/tasks/abc174_e)**」で、**回数制限のあるノコギリを使ってなるべく丸太を短くせよ**という問題。短さの限界を探すときに二分探索のテクニックが役立つ。8ｍが可能で4mが無理なら、答えは5ｍ～8ｍのどれかだから、真ん中の6ｍを試して…という流れで探索していく。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// 出典: AtCoder Beginner Contest 174 E - Logs
public class Main {

	static int n;
	static int k;
	static int[] logs;

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		n = Integer.parseInt(sc.next());
		k = Integer.parseInt(sc.next());
		logs = new int[n];
		for (int i = 0; i < n; i++) {
			logs[i] = Integer.parseInt(sc.next());
		}

		// 二分探索の初期値
		int left = 0; // f(0)はfalse
		int right = 2147483647; // f(2147483647)はtrue

		// 二分探索の基本形　ここから
		while (right - left > 1) {
			int mid = left + (right - left) / 2;
			if (f(mid)) {
				right = mid;
			} else {
				left = mid;
			}
		}
		// 二分探索の基本形　ここまで

		// 上記のwhileループを抜けた時点で、leftとrightが隣合せ、かつ、
		// f(left)がfalseでf(right)がtrueになっている

		// 今回はrightをそのまま出力
		System.out.println(right);
	}

	// k回の切断ですべての丸太をtarget以下の長さにできるか？
	static boolean f(int target) {

		// コーナーケース
		if (target <= 0) {
			return false;
		}

		// 今回使えるノコギリの本数
		int knife = k;

		for (int i = 0; i < n; i++) {

			// 切断しなくていい丸太はスキップ
			if (logs[i] <= target) {
				continue;
			}

			// ノコギリを消費して切断していく
			// 例：丸太の長さが9で目標が4なら2回切断
			knife -= logs[i] / target;

			// ノコギリが途中で不足したらfalse
			if (knife < 0) {
				return false;
			}
		}

		return true;
	}
}
```
</div></details>

# 「Union-Find」の章を読んで過去問を解いた
解いてみた問題は「**[ABC075 C - Bridge](https://atcoder.jp/contests/abc075/tasks/abc075_c)**」で、**グラフにおいて切り落としていけない "橋" を探せ**という問題。Union-Findを使うと、グループ（点の集まり）がいくつあるかを調べられる。試しに辺をひとつ切ってみて、２グループに分裂したら、切った辺は "橋" だったと分かる。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// 出典: AtCoder Beginner Contest 075 C - Bridge
public class Main {

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		int[] a = new int[m];
		int[] b = new int[m];
		for (int i = 0; i < m; i++) {
			a[i] = Integer.parseInt(sc.next());
			b[i] = Integer.parseInt(sc.next());
		}

		// 順番に橋かどうか判定していく
		int result = 0;
		for (int i = 0; i < m; i++) {

			// 橋かもしれない辺を使わずにunionfindを作ってみる
			UnionFindTree uf = new UnionFindTree(n);
			for (int j = 0; j < m; j++) {
				if (i != j) {
					uf.unite(a[j] - 1, b[j] - 1);
				}
			}

			// 確認用
			// uf.printAllNode();

			// 作ったunionfindが木ではなく林になっていたら橋だと分かる
			int treeNum = 0;
			for (int j = 0; j < n; j++) {
				if (uf.root(j) == j) {
					treeNum++;
				}
			}
			if (treeNum == 2) {
				result++;
			}

		}

		System.out.println(result);

	}
}

class UnionFindTree {

	int[] parent;
	int[] size;

	// コンストラクタ
	UnionFindTree(int n) {
		parent = new int[n];
		size = new int[n];
		for (int i = 0; i < n; i++) {
			parent[i] = -1;
			size[i] = 1;
		}
	}

	// xが属する木の根を返す
	int root(int x) {
		if (parent[x] == -1) {
			return x;
		}
		parent[x] = root(parent[x]); // ついでに経路圧縮
		return parent[x];
	}

	// xとyが同じ木にいるかどうか調べて返す
	boolean isSame(int x, int y) {
		return root(x) == root(y);
	}

	// xとyを同じ木にする
	void unite(int x, int y) {
		if (x == y) {
			return;
		}
		int rx = root(x); // xの根
		int ry = root(y); // yの根
		if (rx == ry) {
			return;
		}
		// 木の高さをおさえる工夫をしておく
		if (size[rx] < size[ry]) {
			int tmp = rx;
			rx = ry;
			ry = tmp;
		}
		// つなぐ
		parent[ry] = rx;
		size[rx] += size[ry];
	}

	// xが属する木のサイズを返す
	int getSize(int x) {
		return size[root(x)];
	}

	// 確認用
	void printAllNode() {

		System.out.println(Arrays.toString(parent));
		System.out.println(Arrays.toString(size));

		for (int i = 0; i < parent.length; i++) {
			System.out.println(i + "の根は" + root(i));
			System.out.println(i + "の高さは" + getSize(i));
		}
	}
}
```
</div></details>

# 「Union-Find」の章を読んで過去問を解いた_その2
解いてみた問題は「**[ABC177 D - Friends](https://atcoder.jp/contests/abc177/tasks/abc177_d)**」。さきほどの問題ではグループを数えたが、今度は**最も大きなグループにはいくつの点が所属しているか求めよ**という問題。これもUnion-Findを使えばすぐ求まる。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// 出典: AtCoder Beginner Contest 177 D - Friends
public class Main {

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		UnionFindTree uf = new UnionFindTree(n);
		for (int i = 0; i < m; i++) {
			int left = Integer.parseInt(sc.next());
			int right = Integer.parseInt(sc.next());
			uf.unite(left - 1, right - 1);
		}

		// コーナーケース
		if (m == 0) {
			System.out.println(1);
			return;
		}

		// 確認用
		uf.printAllNode();

		// 最も友達が多い人の、グループの人数を求めれば、それが答え
		int max = 0;
		for (int i = 0; i < n; i++) {
			if (max < uf.getSize(i)) {
				max = uf.getSize(i);
			}
		}

		System.out.println(max);

	}
}

class UnionFindTree {

	int[] parent;
	int[] size;

	// コンストラクタ
	UnionFindTree(int n) {
		parent = new int[n];
		size = new int[n];
		for (int i = 0; i < n; i++) {
			parent[i] = -1;
			size[i] = 1;
		}
	}

	// xが属する木の根を返す
	int root(int x) {
		if (parent[x] == -1) {
			return x;
		}
		parent[x] = root(parent[x]); // ついでに経路圧縮
		return parent[x];
	}

	// xとyが同じ木にいるかどうか調べて返す
	boolean isSame(int x, int y) {
		return root(x) == root(y);
	}

	// xとyを同じ木にする
	void unite(int x, int y) {
		if (x == y) {
			return;
		}
		int rx = root(x); // xの根
		int ry = root(y); // yの根
		if (rx == ry) {
			return;
		}
		// 木の高さをおさえる工夫をしておく
		if (size[rx] < size[ry]) {
			int tmp = rx;
			rx = ry;
			ry = tmp;
		}
		// つなぐ
		parent[ry] = rx;
		size[rx] += size[ry];
	}

	// xが属する木のサイズを返す
	int getSize(int x) {
		return size[root(x)];
	}

	// 確認用
	void printAllNode() {

		System.out.println(Arrays.toString(parent));
		System.out.println(Arrays.toString(size));

		for (int i = 0; i < parent.length; i++) {
			System.out.println(i + "の根は" + root(i));
			System.out.println(i + "の高さは" + getSize(i));
		}
	}
}
```
</div></details>

# 「貪欲法」の章を読んで過去問を解いた
解いてみた問題は「**[ABC131 D - Megalomania](https://atcoder.jp/contests/abc131/tasks/abc131_d)**」で、**すべてのタスクを時間内に完了できるかどうか判定せよ**という問題。タスクによって所要時間と締切日が違うので、締切日が迫っているタスクを最優先で消化するという処理をループで繰り返す。このように毎回最優先のものを選び続ける考え方を貪欲法（どんよくほう）と呼ぶ。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// 出典: AtCoder Beginner Contest 131 D - Megalomania
public class Main {

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		Task t[] = new Task[n];
		for (int i = 0; i < n; i++) {
			int kibo = Integer.parseInt(sc.next());
			int sime = Integer.parseInt(sc.next());
			t[i] = new Task(kibo, sime);
		}

		// ソートの規則を作る
		Comparator<Task> c = new Comparator<Task>() {
			public int compare(Task task1, Task task2) {

				// 納期が等しいなら規模の降順、そうでなければ納期の昇順
				if (task1.sime == task2.sime) {
					return task2.kibo - task1.kibo;
				}
				return task1.sime - task2.sime;

			}
		};

		// ソート（オブジェクト単位のソートなので配列aと連動して配列bも変化）
		Arrays.sort(t, c);

		// 確認用
//		for (int i = 0; i < n; i++) {
//			System.out.println(t[i].kibo + " " + t[i].sime);
//		}

		// 貪欲法で答えを求める
		int now = 0;
		for (int i = 0; i < n; i++) {
			now += t[i].kibo;
			if (t[i].sime < now) {
				System.out.println("No");
				return;
			}
		}
		System.out.println("Yes");

	}
}

class Task {

	int kibo; // タスクの規模
	int sime; // タスクの納期

	// コンストラクタ
	public Task(int kibo, int sime) {
		this.kibo = kibo;
		this.sime = sime;
	}
}
```
</div></details>

# 「ソート」の章を読んで過去問を解いた
解いてみた問題は「**[ABC121 C - Energy Drink Collector](https://atcoder.jp/contests/abc121/tasks/abc121_c)**」で、**ドリンクをなるべく安く買うにはどの店に行けばいいか求めよ**という問題。店によって値段と在庫が違うので、値段の配列を安い順にソートしつつ在庫の配列も連動させてソートする。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// 出典: AtCoder Beginner Contest 121 C - Energy Drink Collector
public class Main {

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		Shop s[] = new Shop[n];
		for (int i = 0; i < n; i++) {
			int price = Integer.parseInt(sc.next());
			int zaiko = Integer.parseInt(sc.next());
			s[i] = new Shop(price, zaiko);
		}

		// ソートの規則を作る
		Comparator<Shop> c = new Comparator<Shop>() {
			public int compare(Shop s1, Shop s2) {

				// 価格の安い順
				return s1.price - s2.price;

			}
		};

		// ソート（オブジェクト単位のソートなので配列aと連動して配列bも変化）
		Arrays.sort(s, c);

		// 確認用
		// for (int i = 0; i < n; i++) {
		// System.out.println(s[i].price + " " + s[i].zaiko);
		// }

		// 答えを求める
		long cost = 0;
		for (int i = 0; i < n; i++) {

			if (s[i].zaiko < m) {
				// この店のドリンクを買い占め
				m -= s[i].zaiko;
				cost += (long) s[i].zaiko * (long) s[i].price;
			} else {
				cost += (long) m * (long) s[i].price;
				System.out.println(cost);
				return;
			}
		}

	}
}

class Shop {

	int price; // ドリンクの値段
	int zaiko; // ドリンクの在庫

	// コンストラクタ
	public Shop(int price, int zaiko) {
		this.price = price;
		this.zaiko = zaiko;
	}
}
```
</div></details>

# 「グラフ探索」の章を読んでDFSを作った
DFS（深さ優先探索）のプログラムを作成した。グラフにおいて始点から到達可能な点を列挙できる。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// 再帰関数を使ったDFSの練習
public class Main {

	static List<List<Edge>> graph; // グラフ
	static boolean[] result; // 点0から到達可能かどうかの判定結果

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next()); // 点の数
		int m = Integer.parseInt(sc.next()); // 辺の数
		graph = new ArrayList<List<Edge>>();
		for (int v = 0; v < n; v++) {
			graph.add(new ArrayList<Edge>());
		}
		for (int e = 0; e < m; e++) {
			int from = Integer.parseInt(sc.next()) - 1; // 始点
			int to = Integer.parseInt(sc.next()) - 1; // 終点
			long w = Long.parseLong(sc.next()); // 重み
			graph.get(from).add(new Edge(to, w));
			// graph.get(to).add(new Edge(from, w)); // 無向グラフであれば逆向きもある
		}

		// 確認用
		for (int v = 0; v < n; v++) {
			System.out.println("点" + v);
			for (Edge e : graph.get(v)) {
				System.out.println("　⇒" + e.w + "⇒点" + e.to);
			}
		}

		// 探索
		result = new boolean[n];
		for (int v = 0; v < n; v++) {
			result[v] = false;
		}
		dfs(0);

		// 結果
		for (int v = 0; v < n; v++) {
			System.out.println(result[v]);
		}

	}

	static void dfs(int v) {
		result[v] = true;
		for (Edge e : graph.get(v)) {
			int next = e.to; // 次の点
			if (result[next] == false) {
				dfs(next);
			}
		}
	}
}

class Edge {

	int to; // 行先の頂点
	long w; // この辺の重み

	// コンストラクタ
	public Edge(int to, long w) {
		this.to = to;
		this.w = w;
	}
}
```
</div></details>

DFSは応用範囲が非常に広い。作成した上記プログラムを流用＆改造することで、例えば下記５つの問題を解くことができた。
・「**[ABC126 D - Even Relation](https://atcoder.jp/contests/abc126/tasks/abc126_d)**」⇒**条件に従ってグラフの点を白か黒かで塗り分けろ**という問題。
・「**[ABC137 E - Coins Respawn](https://atcoder.jp/contests/abc137/tasks/abc137_e)**」⇒**道中に落ちているコインをなるべくたくさん拾いながらゴールを目指せ**という問題。
・「**[ABC138 D - Ki](https://atcoder.jp/contests/abc138/tasks/abc138_d)**」⇒**グラフ構造に対する操作（クエリ）を高速で処理せよ**という問題。
・「**[ABC157 D - Friend Suggestions](https://atcoder.jp/contests/abc157/tasks/abc157_d)**」⇒**「友達関係」や「ブロック関係」といった情報をもとに友達候補の人数を求めよ**という問題。
・「**[ABC188 E - Peddler](https://atcoder.jp/contests/abc188/tasks/abc188_e)**」⇒**最大の利益を得るにはどの街で品を買ってどの街で品を売ればよいか求めよ**という問題。

# 「グラフ探索」の章を読んでBFSを作った
BFS（幅優先探索）のプログラムを作成した。始点から到達可能な点を列挙できるのはDFSと同じだが、BFSだと最短歩数（辺をいくつ経由すれば到達できるか）も同時に求められる。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// BFSで最短歩数を求める練習
public class Main {

	static List<List<Integer>> graph; // グラフ
	static int[] dist; // 点0からの最短歩数

	public static void main(String[] args) {

		// 入力（今回は重みなしグラフとする）
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next()); // 点の数
		int m = Integer.parseInt(sc.next()); // 辺の数
		graph = new ArrayList<List<Integer>>();
		for (int v = 0; v < n; v++) {
			graph.add(new ArrayList<Integer>());
		}
		for (int e = 0; e < m; e++) {
			int from = Integer.parseInt(sc.next()); // 始点
			int to = Integer.parseInt(sc.next()); // 終点
			graph.get(from).add(to);
			graph.get(to).add(from); // 無向グラフであれば逆向きもある
		}

		// 結果用配列を初期化してから、点0を始点としてBFS
		dist = new int[n];
		for (int v = 0; v < n; v++) {
			dist[v] = -1;
		}
		bfs(0);

		// 結果
		for (int v = 0; v < n; v++) {
			System.out.println(dist[v]);
		}

	}

	static void bfs(int s) {

		// スタート地点をキューに入れる
		Queue<Integer> queue = new ArrayDeque<Integer>();
		queue.add(s);
		dist[s] = 0;

		// キューが空になるまでループ
		while (!queue.isEmpty()) {

			// キューからひとつ取り出す
			int v = queue.poll();

			// 次の点それぞれ処理
			for (int next : graph.get(v)) {

				// 過去に調べた点は行かない
				if (dist[next] != -1) {
					continue;
				}

				// キューに入れる
				dist[next] = dist[v] + 1;
				queue.add(next);
			}

		}
	}
}
```
</div></details>

<details><summary>余談　ビームサーチについて（クリックで展開）</summary><div>
けんちょん本では一切触れられていないので完全に余談だが、ビームサーチという考え方がある。
あるグラフをBFSしていて、例えば始点から深さ3のところに点が5個あったとしよう。ところがなんらかの事情（計算量とか計算速度とか）で5個の点全てを調べるのは避けたい。そこで5個の点の「良さ」のランキングを作り、上位3個だけ残し、下位2個は探索を打ち切る（いわゆる枝刈り）。これがビームサーチ。
ランキングの付け方とか、上位何個を残すかとか、いろいろカスタマイズできそうだ。ちなみに上位1位だけを残すことにした場合、それはつまり貪欲法である。
当たり前の話だが、このようにビームサーチはヒューリスティック（近似アルゴリズム）なので、最適解へと至る点を刈ってしまうかもしれないことに注意。特に「悪い点」の先に「良い点」があるようなモデルの問題だと使いにくい。
</div></details>

# 「グラフ探索」の章を読んで木判定処理を作った
さきほどのDFSを応用して、グラフが木かどうか判定するプログラムを作成した。ただしこれは本では扱っていない話題であり、私のオリジナルなアイデアをプログラムにしたものである。そのためもっと効率的に判定できるやりかたがあるかもしれない。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// DFSでグラフが木かどうかを判定する練習
public class Main {

	static List<List<Integer>> graph; // グラフ
	static int[] asi; // DFSの足跡記録用
	static boolean treeSearchResult; // 木かどうかの判定結果

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = 5000; // 点の数
		int m = Integer.parseInt(sc.next()); // 辺の数
		int s = Integer.parseInt(sc.next()); // 始点の番号
		graph = new ArrayList<List<Integer>>();
		for (int v = 0; v < n; v++) {
			graph.add(new ArrayList<Integer>());
		}
		for (int e = 0; e < m; e++) {
			int a = Integer.parseInt(sc.next()); // 始点
			int b = Integer.parseInt(sc.next()); // 終点
			graph.get(a).add(b);
			graph.get(b).add(a); // 無向グラフなので逆向きもある
		}

		// 変数初期化
		asi = new int[n + 1];
		treeSearchResult = true;

		// 始点からDFS開始
		dfs(s, -1, s);

		// 結果
		System.out.println("木だった？" + (treeSearchResult ? "Yes" : "No"));

	}

	static void dfs(int v, int from, int root) {

		// 新しい点に到着したので足跡記録
		asi[v] = 1;

		// この点から行ける次の点
		for (int next : graph.get(v)) {

			// ひとつ前の点には戻らない
			// ※無向グラフなので点と点の間に往路と復路の２本の枝があり
			// 　復路を使うと木なのに閉路があると判断してしまうため
			if (next == from) {
				continue;
			}

			// 過去に通った点には行かない
			// ※過去に通った点を見つけたので木でないことが確定
			if (asi[next] != 0) {
				treeSearchResult = false;
				continue;
			}

			// 次の点へ
			dfs(next, v, root);
		}
	}
}
```
</div></details>

# 「最短路問題」の章を読んでベルマンフォード法を作った
本の「最短路問題」の章を読みながら、ベルマンフォード法のプログラムを作成した。ベルマンフォード法はDFSと違って、重み付きグラフの最短距離を求めることができ、しかも重みの値が負であっても正しく動作する。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// 重み付きグラフの練習
public class Main {

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next()); // 点の数
		int m = Integer.parseInt(sc.next()); // 辺の数
		int s = Integer.parseInt(sc.next()); // 始点
		List<List<Edge>> graph = new ArrayList<List<Edge>>();
		for (int v = 0; v < n; v++) {
			graph.add(new ArrayList<Edge>());
		}
		for (int e = 0; e < m; e++) {
			int from = Integer.parseInt(sc.next()); // 始点
			int to = Integer.parseInt(sc.next()); // 終点
			long w = Long.parseLong(sc.next()); // 重み
			graph.get(from).add(new Edge(to, w));
			// graph.get(to).add(new Edge(from, w)); // 無向グラフであれば逆向きもある
		}

		// 確認用
		// for (int v = 0; v < n; v++) {
		// System.out.println("点" + v);
		// for (Edge e : graph.get(v)) {
		// System.out.println("　⇒" + e.w + "⇒点" + e.to);
		// }
		// }

		// 以下、ベルマンフォード法。始点から各点への最短距離を求める。
		// 負の重みの辺があるグラフでもOK。
		// ※ぐるぐる回って永遠に距離を減らせる負閉路を検出したら "No" と出力する。
		boolean resultNegativeCycle = false;
		long resultDist[] = new long[n];
		for (int i = 0; i < n; i++) {
			resultDist[i] = 9999999;
		}
		resultDist[s] = 0;

		// 緩和処理をn回反復することで答えを求めていく
		for (int iter = 0; iter < n; iter++) {

			boolean updateFlg = false;

			// 点それぞれについて
			for (int v = 0; v < n; v++) {

				// 自身がまだ ∞ なら、そこから出ていく辺は考慮外
				if (resultDist[v] == 9999999) {
					continue;
				}

				// この点から出ていく辺それぞれについて
				for (Edge e : graph.get(v)) {

					// 緩和
					if (resultDist[v] + e.w < resultDist[e.to]) {
						resultDist[e.to] = resultDist[v] + e.w;
						updateFlg = true;
					}
				}
			}

			// 一度も緩和が発生しなかったら問題は解けている
			if (!updateFlg) {
				break;
			}

			// n回目の反復でも緩和が発生したら負閉路があったということ
			if (iter == n - 1 && updateFlg) {
				resultNegativeCycle = true;
			}
		}

		// 結果出力
		if (resultNegativeCycle) {
			// 負閉路があった場合は No を出力
			System.out.println("No");
		} else {
			// 負閉路がなかった場合は結果を出力
			for (int i = 0; i < n; i++) {
				System.out.println("点" + s + "から点" + i + "への最短距離は "
						+ resultDist[i]);
			}
		}

	}
}

class Edge {

	int to; // 行先の頂点
	long w; // この辺の重み

	// コンストラクタ
	public Edge(int to, long w) {
		this.to = to;
		this.w = w;
	}
}
```
</div></details>

# 「最短路問題」の章を読んでダイクストラ法を作った
最短路問題といえばやはりこれ、ダイクストラ法のプログラムを作成した。辺の重みがすべて非負なら、ベルマンフォード法よりもこちらのほうが高速。さらにダイクストラ法の中で「次に調べる点」を探すとき、優先度付きキュー`PriorityQueue`を使うように工夫してある。また、作ったプログラムをうまく流用して「**[ABC191 E - Come Back Quickly](https://atcoder.jp/contests/abc191/tasks/abc191_e)**」を解くこともできた。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// ダイクストラ法で、重み付き有向グラフの単一始点最短経路問題を解く
public class Main {

	static List<List<Edge>> graph;

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next()); // 点の数
		int m = Integer.parseInt(sc.next()); // 辺の数

		// 重み付き有向グラフ
		graph = new ArrayList<List<Edge>>();
		for (int v = 0; v < n; v++) {
			graph.add(new ArrayList<Edge>());
		}
		for (int e = 0; e < m; e++) {
			int from = Integer.parseInt(sc.next()) - 1; // 始点
			int to = Integer.parseInt(sc.next()) - 1; // 終点
			long w = Long.parseLong(sc.next()); // 重み
			graph.get(from).add(new Edge(to, w));
		}

		// 点0をスタートとするダイクストラ法
		long[] saitan = dijkstra(0);
		System.out.println(Arrays.toString(saitan));
	}

	// startから各点への最短距離
	static long[] dijkstra(int start) {

		// 変数初期化して、スタートの町をキューに入れる
		long[] result = new long[graph.size()];
		Arrays.fill(result, Long.MAX_VALUE);
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> Long.compare(result[a], result[b]));
		pq.add(start);
		result[start] = 0;

		while (!pq.isEmpty()) {

			// 出発点v（resultが最も小さい町）から伸びている道それぞれ
			int v = pq.poll();
			for (Edge e : graph.get(v)) {

				// 次の町を緩和できたら、そこから先も調べたいのでキューに追加
				if (result[e.to] > result[v] + e.w) {
					result[e.to] = result[v] + e.w;
					pq.add(e.to);
				}
			}

		}

		return result;
	}

	// 道１つの情報
	static class Edge {

		int to; // 行先の町
		long w; // この道の重み

		// コンストラクタ
		public Edge(int to, long w) {
			this.to = to;
			this.w = w;
		}
	}
}
```
</div></details>

# 「動的計画法」の章を読んでナップサック問題を解くプログラムを作った
けんちょん本ではDPで解ける問題の代表例としてナップサック問題が取り上げられている。ナップサック問題は非常に有名な問題なので、どういった問題かについてはここでは紹介しない（ググってください）。プログラムを作る際は**[けんちょんさんのQiita記事](https://qiita.com/drken/items/a5e6fe22863b7992efdb)**も参考にさせていただいた。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.*;

// ナップサック問題をDPで解く
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next()); // 荷物の種類数
		int w = Integer.parseInt(sc.next()); // ナップザックの容量
		int[] val = new int[n + 1];
		int[] cost = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			val[i] = Integer.parseInt(sc.next()); // 荷物iの価値
			cost[i] = Integer.parseInt(sc.next()); // 荷物iの重さ
		}

		// DPテーブル
		// 例えば dp[3][4] は、荷物が3種類、ナップサックの容量が4、のときの解
		int dp[][];
		dp = new int[n + 1][w + 1];

		// 荷物が0種類だったら解も0
		for (int j = 0; j <= w; j++) {
			dp[0][j] = 0;
		}

		// 荷物の種類数を増やしながら
		for (int i = 1; i <= n; i++) {

			// ナップサックの容量を増やしながら
			for (int j = 0; j <= w; j++) {

				// 今、荷物がi種類、ナップサックの容量がjである。

				// 増えたばかりの新しい荷物を使わないとしたら？
				// この荷物を考慮していなかったときの解のまま変わらない。
				int kai1 = dp[i - 1][j];

				// 増えたばかりの新しい荷物を使うとしたら？
				// この荷物の容量がcost[i]なので、
				// この荷物を考慮していなかったときの、かつ、ナップサックが今よりcost[i]小さかったときの、
				// 解にこの荷物を入れたのが解。（このとき配列外参照を防ぐためif文で囲っておく）
				int kai2 = 0;
				if (j - cost[i] >= 0) {
					kai2 = dp[i - 1][j - cost[i]] + val[i];
				}

				// 新しい荷物を使うべきか使わないべきか、最適なほう
				dp[i][j] = Math.max(kai1, kai2);
			}
		}

		// 答え
		System.out.println(dp[n][w]);
	}
}
```
</div></details>

# 「動的計画法」の章を読んで部分和問題を解くプログラムを作った
部分和問題もナップサック問題と同様、非常に有名な問題なのでここでは紹介を省く（ググってください）。部分和問題はナップサック問題とよく似ている（というか部分和問題はナップサック問題の一種だと言えなくもない）ためか、けんちょん本には部分和問題をDPで解く手法は載っていない（ただし部分和問題が一切登場しないわけではなく全探索の章や再帰関数の章では登場する）。ということで先ほどと同様、**[けんちょんさんのQiita記事](https://qiita.com/drken/items/a5e6fe22863b7992efdb)**を参考にさせていただきつつプログラムを作成した。このプログラムではDPテーブルの左端を "作れる和の最小値" としているので、問題の入力に負のアイテムがあっても正常に動作する。また、作ったプログラムをうまく流用して「**[ABC044 C - 高橋君とカード](https://atcoder.jp/contests/abc044/tasks/arc060_a)**」を解くこともできた。

<details><summary>作ったプログラム（クリックで展開）</summary><div>

```java
import java.util.Scanner;

// 部分和問題をDPで解く
public class Main {

	public static void main(String[] args) {

		// 入力
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next()); // カードの枚数
		int[] a = new int[n]; // カード
		for (int i = 0; i < n; i++) {
			a[i] = Integer.parseInt(sc.next());
		}

		// 利用法サンプル 和10を作れるか？
		System.out.println(new Bubunwa(a).canAble(10));

		// 利用法サンプル 和10を作る方法は何通りか？
		System.out.println(new Bubunwa(a).getCount(10));

		// 利用法サンプル 和-1を作る方法は何通りか？
		System.out.println(new Bubunwa(a).getCount(-1));

		// 利用法サンプル 和0を作る方法は何通りか？（カードを一切選ばないという1通りも含む）
		System.out.println(new Bubunwa(a).getCount(0));

	}

	// 部分和問題を解く
	static class Bubunwa {

		private int l = 0; // DPテーブルの左端、つまり作れる和の最小値（全カードの数字が非負なら0）
		private int r = 0; // DPテーブルの右端、つまり作れる和の最大値
		private long[] count; // count[i] := 狙った和を作る方法の数

		// コンストラクタ
		Bubunwa(int[] a) {

			int n = a.length; // カードの枚数
			l = 0; // DPテーブルの左端、つまり作れる和の最小値（全カードの数字が非負なら0）
			r = 0; // DPテーブルの右端、つまり作れる和の最大値
			for (int i = 0; i < n; i++) {
				if (a[i] < 0) {
					l += a[i];
				} else {
					r += a[i];
				}
			}

			// dp[i][j] := 最初のi枚のカードだけを使ってjを作る方法は何通りあるか
			long[][] dp = new long[n + 1][r - l + 1];
			dp[0][-l] = 1;
			for (int i = 1; i <= n; i++) {
				for (int j = 0; j <= (r - l); j++) {
					dp[i][j] = dp[i - 1][j];
					if (0 <= j - a[i - 1] && j - a[i - 1] <= r - l) {
						dp[i][j] += dp[i - 1][j - a[i - 1]];
					}
				}
			}

			// 結果まとめ
			count = new long[r - l + 1];
			for (int i = 0; i < r - l + 1; i++) {
				count[i] = dp[n][i];
			}

		}

		// 狙った和 m を作る方法の数を返す
		// ※mが0の場合、カードを一切選ばないという1通りも含んでいる
		long getCount(int m) {
			if (0 <= m - l && m - l < count.length) {
				return count[m - l];
			} else {
				return 0; // 引数mがおかしいエラー
			}
		}

		// 狙った和 m を作れるかどうかを返す
		boolean canAble(int m) {
			if (0 <= m - l && m - l < count.length) {
				return 0 < count[m - l];
			} else {
				return false; // 引数mがおかしいエラー
			}
		}

	}

}
```
</div></details>

***

いったんここまでにします。
今後また何か作ったら追記していきます。