ABC - 021 - A&B&C

#AtCoder ABC 021 A&B&C
[AtCoder - 021](https://atcoder.jp/contests/abc021)
**201905/15追記**　A問題の解法がコメント欄に有


#A問題

 - 同じの何度も利用してよいなら全部1でもよいとおもって。。。一応AC

```java
	private void solveA() {
		int n = nextInt();

		out.println(n);

		IntStream.range(0, n).forEach(i -> out.println(1));

	}
```

#A問題：ベタにループ
**201905/15追記**
　コメント欄にきれいなループでのコード有

 - 簡略化しないとこんな感じになるのか？

```java
	private void solveA2() {
		int n = nextInt();

		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				for (int k = 0; k <= n; k++) {
					for (int l = 0; l <= n; l++) {
						if (i * 1 + j * 2 + k * 4 + l * 8 == n) {
							out.println(i + j + k + l);
							for (int l2 = 0; l2 < i; l2++) {
								out.println(1);
							}
							for (int j2 = 0; j2 < j; j2++) {
								out.println(2);
							}
							for (int k2 = 0; k2 < k; k2++) {
								out.println(4);
							}
							for (int l2 = 0; l2 < l; l2++) {
								out.println(8);
							}
							return;
						}
					}
				}
			}

		}

	}
```

#B問題

 - 経路が以下の条件を満たせば、少なくとも余計な回り道はしていない
    - 始点と終点を含んでいない
    - 同じ町が二回出てこない

 コメントアウトは最初にforで考えた名残

```java
	private void solveB() {
		int n = nextInt();
		int a = nextInt();
		int b = nextInt();
		int k = nextInt();
		int[] wk = IntStream.range(0, k).map(i -> nextInt()).toArray();
		Map<Integer, Long> tmp = Arrays.stream(wk).mapToObj(i -> new Integer(i))
				.collect(Collectors.groupingBy(s -> s, Collectors.counting()));

		boolean res = tmp.entrySet().stream()
				.allMatch(entry -> !entry.getKey().equals(a) && !entry.getKey().equals(b) && entry.getValue() < 2);
		out.println(res ? "YES" : "NO");

		//		for (Entry<Integer, Long> entry : tmp.entrySet()) {
		//			if (entry.getKey().equals(a) || entry.getKey().equals(b) || entry.getValue() > 1) {
		//				out.println("NO");
		//				return;
		//			}
		//		}
		//		out.println("YES");
	}
```

#C問題：最短経路問題

Stream使ってとか余裕ないので全部For文・・・

**参考：**
　[最短経路問題の解法まとめ](https://qiita.com/ta-ka/items/a023a11efe17ab097433#warshall-floyd%E6%B3%95)
　[DPの話](http://d.hatena.ne.jp/Tayama/20111210/1323502092)
　[ダイクストラ法が分からなかった君のために](http://kuuso1.hatenablog.com/entry/2015/12/20/212620)
　プログラミングコンテストチャレンジブック P.87~
　[有向非巡回グラフ（DAG）の意味とトポロジカルソート](https://mathwords.net/dag)

 - ワーシャルフロイド法で実装(Dijkstra法やBellmanFordだと上手く実装できなかったんや。。。)
 - トポロジカルソート
 - DP

遷移についてコードのコメントにも書いてあるけど抜き出し

##最初に、隣接行列から各拠点間の移動にかかる最小コストを算出している

 - ワーシャルフロイド法を利用
 - 各町間の移動コストは1と仮置き（問題遺文中には移動コストがないかつ、入力例より各町間の移動コストは等価と読んだ）
    - 各町間での移動コストが不定の場合は、、、**その問題を解く時に考えよう**

**1:最小コストの計算**

|始点\終点|町1|2|3|4|5|6|7||
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|町1|0| 1| 1| 2| 3| 3| 4||
|2|1| 0| 2| 1| 2| 2| 3||
|3|1| 2| 0| 1| 2| 2| 3||
|4|2| 1| 1| 0| 1| 1| 2||
|5|3| 2| 2| 1| 0| 2| 1||
|6|3| 2| 2| 1| 2| 0| 1||
|7|4| 3| 3| 2| 1| 1| 0||

**2:最小コスト&入力された辺より始点→終点の移動についてトポロジカルソート**

 - ワーシャルフロイド法の結果をもとに、`次の町`をマップ
 - `次の町`の判定は、移動コストが $\pm 1$　であること
    - $+1$なら次の町、$-1$なら前の町

|始点\終点|町1|2|3|4|5|6|7||
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|町1|0| 1| 1| 0| 0| 0| 0||
|2|0| 0| 0| 1| 0| 0| 0||
|3|0| 0| 0| 1| 0| 0| 0||
|4|0| 0| 0| 0| 1| 1| 0||
|5|0| 0| 0| 0| 0| 0| 1||
|6|0| 0| 0| 0| 0| 0| 1||
|7|0| 0| 0| 0| 0| 0| 0||

**3:トポロジカルソートの結果をもとに始点から終点まで、各コストごと（かつ、コスト順。順序性を持つためTreeMap利用している）に経由地が何個ずつあるのかをまとめ**

|コスト|0|1|2|3|4||
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|経由する町|1|2,3| 4|5,6|7| |

**4:DPで（コスト順に）計算**

```java
	private void solveC() {
		int n = nextInt();
		int a = nextInt() - 1;
		int b = nextInt() - 1;
		int m = nextInt();

		final int CONST_INF = 999999999;
		int[][] graph = new int[n][n];
		for (int i = 0; i < graph.length; i++) {
			Arrays.fill(graph[i], CONST_INF);
			graph[i][i] = 0;
		}
		Edge[] edge = new Edge[m];
		for (int j = 0; j < m; j++) {
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			graph[from][to] = 1;
			graph[to][from] = 1;
			Edge wkEdge = new Edge();
			if (from > to) {
				wkEdge.from = to;
				wkEdge.to = from;
				wkEdge.cost = 1;
			} else {
				wkEdge.from = from;
				wkEdge.to = to;
				wkEdge.cost = 1;
			}

			edge[j] = wkEdge;
		}

		/*
		 * ワーシャルフロイド法の計算結果
		 *  [0, 1, 1, 2, 3, 3, 4]
		 *  [1, 0, 2, 1, 2, 2, 3]
		 *  [1, 2, 0, 1, 2, 2, 3]
		 *  [2, 1, 1, 0, 1, 1, 2]
		 *  [3, 2, 2, 1, 0, 2, 1]
		 *  [3, 2, 2, 1, 2, 0, 1]
		 *  [4, 3, 3, 2, 1, 1, 0]
		 */
		getMinByWarshall(graph, n);
		/*
		 * 最短路DAG
		 * トポロジカルソート実施後
		 * [0, 1, 1, 0, 0, 0, 0]
		 * [0, 0, 0, 1, 0, 0, 0]
		 * [0, 0, 0, 1, 0, 0, 0]
		 * [0, 0, 0, 0, 1, 1, 0]
		 * [0, 0, 0, 0, 0, 0, 1]
		 * [0, 0, 0, 0, 0, 0, 1]
		 * [0, 0, 0, 0, 0, 0, 0]
		 */
		int[][] dag = new int[n][n];
		for (int i = 0; i < m; i++) {
			int x = edge[i].from;
			int y = edge[i].to;
			if (graph[a][x] == graph[a][y] + 1) {
				dag[y][x] = 1;
			}
			if (graph[a][x] == graph[a][y] - 1) {
				dag[x][y] = 1;
			}
		}
		/*
		 * 最短距離マップ
		 * a地点(a=0)からの距離ごとのマップ
		 * {0=[0], 1=[1, 2], 2=[3], 3=[4, 5], 4=[6]}
		 */
		Map<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
		for (int i = 0; i < n; i++) {
			int d = graph[a][i];
			if (map.containsKey(d)) {
				List<Integer> list = map.get(d);
				list.add(i);
				map.put(d, list);
			} else {
				List<Integer> list = new ArrayList<Integer>();
				list.add(i);
				map.put(d, list);
			}
		}
		long CONST_MOD = (long) Math.pow(10, 9) + 7;
		long[] minStep = new long[n];
		minStep[a] = 1;
		/*
		 * 地点aから地点bへの移動コスト分回す
		 */
		for (List<Integer> towns : map.values()) {
			for (Integer town : towns) {
				for (int k = 0; k < n; k++) {
					/*
					 * 地点：townから地点：kへ行くことが可能なら（dag上で1=）
					 * minStep[k]にminStep[town]からの移動回数をプラス(k地点への移動が可能)
					 */
					if (dag[town][k] == 1) {
						minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
					}
				}
			}
		}
		System.out.println(minStep[b]);
	}

	private static class Edge {
		private int from;
		private int to;
		private int cost;
	}

	private void getMinByWarshall(int[][] edge, int vertex) {
		for (int k = 0; k < vertex; k++) {
			for (int i = 0; i < vertex; i++) {
				for (int j = 0; j < vertex; j++) {
					edge[i][j] = Integer.min(edge[i][j], edge[i][k] + edge[k][j]);

				}
			}
		}

	}
```

##C問題注記

**最短距離マップ** を作ったのち、最後のDPはマップを利用している。

 - 該当のコード

```java
		for (List<Integer> towns : map.values()) {
			for (Integer town : towns) {
				for (int k = 0; k < n; k++) {
					/*
					 * 地点：townから地点：kへ行くことが可能なら（dag上で1=）
					 * minStep[k]にminStep[town]からの移動回数をプラス(k地点への移動が可能)
					 */
					if (dag[town][k] == 1) {
						minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
					}
				}
			}
		}
```

ただ、入力例1や入力例2をもとにMapの中を見てみると以下（改修？コード）の様に改修できる気がしてくる。
　結局全部のtownで回しているならMap要らないじゃん？
　じゃぁ、最初から全て回せばよいのでは？？？と。
結論としては、MapをもとにDPをしないと正確な値は出てこない。

 - 入力値：本来は出力=1となるはずだが、失敗改修後のコードだと出力=0になる

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

 - 改修？コード(改修失敗)

```java
		for (int town = 0; town < n; town++) {
			for (int k = 0; k < n; k++) {
				if (dag[town][k] == 1) {
					minStep[k] = (minStep[k] + minStep[town]) % CONST_MOD;
				}
			}
		}
```