ABC - 022 - A&B&C

#AtCoder ABC 022 A&B&C
[AtCoder - 022](https://atcoder.jp/contests/abc022)

**2019/05/14 追記**
　B問題：resの合計を出すところのコード修正

#A問題

 - 取り込みごとに体重が適正範囲かどうか確認する

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

		long sum = w;
		int res = 0;
		for (int i = 0; i < n; i++) {
			if (i != 0) {
				sum += nextInt();
			}
			if (s <= sum && sum <= t) {
				res++;
			}
		}

		out.println(res);
	}
```

#B問題
(2019/05/14 resの合計を出すところのコード修正)

 - 問題文を読むと以下がわかる
    - ある種類の花が1つしかないときは受粉できない
    - 2つ以上ある花はn-1受粉する
        - 3個ある花は2個受粉する

 - 2つ以上ある花をカウント
 - それぞれの花でn-1受粉するのでカウントする

 - コメントアウトしてあるところも動作する。書き方確認のためいくつか試行中

```java
		int numN = nextInt();

		Map<Integer, Long> tmp = IntStream.range(0, numN).map(i -> nextInt()).mapToObj(i -> new Integer(i))
				.collect(Collectors.groupingBy(s -> s, Collectors.counting()));

		long res = tmp.values().stream().mapToLong(i -> i - 1).sum();

		//		long res = tmp.values().stream().filter(i -> i.longValue() > 1).reduce(0L, (sum, i) -> sum += (i - 1));

		//		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		//		Map<Integer, Long> tmp = Arrays.stream(wk).mapToObj(i -> new Integer(i))
		//				.collect(Collectors.groupingBy(s -> s, Collectors.counting()));
		//		long res = tmp.values().stream().filter(i -> i.longValue() > 1).reduce(0L, (sum, i) -> sum += (i - 1));

		out.println(res);
```

#C問題：ワーシャルフロイド法

 - 1から出て1に戻ってくる
 - ただし、同じ道を使えない
    - 1に隣接する頂点は往路と復路で変える必要がある
    - 1に隣接する頂点間の最短経路を求めておいて以下の移動コストを計算する
        - 1 -> 隣接する頂点1 -> 隣接する頂点2 -> 1
            - 隣接する頂点1-2については総当たり
    - [隣接する頂点1 -> 隣接する頂点2]を計算するにあたり **ワーシャルフロイド法** を利用
        - [隣接する頂点1 -> 隣接する頂点2]を計算する際に、[1]を経由すると2回同じところを通るので、1のコストを省いた隣接行列を作成して計算した



 - 例1をもとにしたgraphWithOutStartの計算結果(頂点1を抜いた隣接行列鵜の計算結果)
    - 頂点1を通らないため、すべtINFになっている

||頂点1|2|3|4|5|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|1|0|INF|INF|INF|INF|
|2|INF|0|5|10|3|
|3|INF|5|0|5|2|
|4|INF|10|5|0|7|
|5|INF|3|2|7|0|


 - 比較用：例1をもとにしたgraphの計算結果(各頂点への最小コストの計算結果)

||頂点1|2|3|4|5|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|頂点1|0| 2| 6| 1| 5|
|2|2| 0| 5| 3| 3|
|3|6| 5| 0| 5| 2|
|4|1| 3| 5| 0| 6|
|5|5| 3| 2| 6| 0|

```java
	private void solveC() {
		final long CONST_INF = Long.MAX_VALUE / 10;

		int n = nextInt();
		int m = nextInt();
		long[][] graphWithOutStart = new long[n][n];
		long[][] graph = new long[n][n];
		List<Integer> edgeNearByStart = new ArrayList<Integer>();

		/*
		 * graphの初期化
		 * [1]を含めた隣接行列と[1]を入れない隣接行列の作成
		 */
		for (int i = 0; i < n; i++) {
			Arrays.fill(graph[i], CONST_INF);
			Arrays.fill(graphWithOutStart[i], CONST_INF);
			graphWithOutStart[i][i] = 0;
			graph[i][i] = 0;
		}

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

			/*
			 * 添え字に合わせて-1して取り込み
			 */
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			int cost = nextInt();
			if (from != 0) {
				/*
				 * [1]を除いたgraph
				 */
				graphWithOutStart[from][to] = cost;
				graphWithOutStart[to][from] = cost;
			} else {
				/*
				 * [1]に隣接している頂点たち
				 */
				edgeNearByStart.add(to);
			}
			graph[from][to] = cost;
			graph[to][from] = cost;
		}

		long res = Long.MAX_VALUE;

		Collections.sort(edgeNearByStart);

		/*
		 *  Warshall–Floyd法で頂点の更新
		 */

		getMinByWarshall(graphWithOutStart, n);

		for (int i = 0; i < edgeNearByStart.size(); i++) {
			for (int j = i + 1; j < edgeNearByStart.size(); j++) {
				int start = edgeNearByStart.get(i);
				int end = edgeNearByStart.get(j);
				/*
				 * [1]から[隣接する頂点1]のコスト + [隣接する頂点1][隣接する頂点2]のコスト + [隣接する頂点2]から[1]のコスト
				 */
				long total = graph[0][start] + graphWithOutStart[start][end] + graph[0][end];
				//低い値を採用
				res = Long.min(res, total);
			}

		}

		out.println(res >= CONST_INF ? -1 : res);

	}

	/**
	 *
	 * @param edge
	 * @param point
	 */
	private void getMinByWarshall(long[][] edge, int point) {
		for (int k = 0; k < point; k++) {
			for (int i = 0; i < point; i++) {
				for (int j = 0; j < point; j++) {
					edge[i][j] = Long.min(edge[i][j], edge[i][k] + edge[k][j]);
				}
			}
		}

	}
```

#C問題：ワーシャルフロイド法（コード短い版）

 - [隣接する頂点1 -> 隣接する頂点2]を計算する際に、[1]を経由すると2回同じところを通るので、1のコストを省いた隣接行列を作成したのだが、ワーシャルフロイド方での計算時に、添え字を[0]からではなく[1]から始めると[頂点1]を経由しないでコスト算出できる。。。
 - これを利用すると、`頂点1を省いた隣接行列を作成せずにワーシャルフロイド法で計算`ができて速度アップ＆見やすい

---

 - 例1を添え字[1]からワーシャルフロイド法で計算した結果が下記の表
    - 1に隣接している頂点(2,4,5)については1へ移動するときのコストが計算されているが1に隣接していない頂点(3)はコストが計算されていない
    - 頂点2から頂点4への最小コストは3だが計算された結果は頂点を[2->5->3->4]と移動したコスト10になっている


||頂点1|2|3|4|5|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|頂点1|0| 2| INF| 1| 12|
|2|2| 0| 5| 10| 3|
|3|INF| 5| 0| 5| 2|
|4|1| 10| 5| 0| 7|
|5|12| 3| 2| 7| 0|

 - 比較用：添え字[1]から計算した場合と添え字[0]から計算した場合
    - 以下の表は、頂点1を抜いた隣接行列を添え字[0]から計算している

||頂点1|2|3|4|5|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|1|0|INF|INF|INF|INF|
|2|INF|0|5|10|3|
|3|INF|5|0|5|2|
|4|INF|10|5|0|7|
|5|INF|3|2|7|0|

---

```java
	private void solveC() {
		final long CONST_INF = Long.MAX_VALUE / 10;

		int n = nextInt();
		int m = nextInt();
		long[][] graph = new long[n][n];

		/*
		 * graphの初期化
		 * [1]を含めた隣接行列と[1]を入れない隣接行列の作成
		 */
		for (int i = 0; i < n; i++) {
			Arrays.fill(graph[i], CONST_INF);
			graph[i][i] = 0;
		}

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

			/*
			 * 添え字に合わせて-1して取り込み
			 */
			int from = nextInt() - 1;
			int to = nextInt() - 1;
			int cost = nextInt();
			graph[from][to] = cost;
			graph[to][from] = cost;
		}

		long res = Long.MAX_VALUE;

		/*
		 *  Warshall–Floyd法で頂点の更新
		 */

		/*
		 * 1から添え字を始めると、1については更新されない
		 */
		for (int k = 1; k < n; k++) {
			for (int i = 1; i < n; i++) {
				for (int j = 1; j < n; j++) {
					graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
				}
			}
		}

		for (int i = 1; i < n; i++) {
			for (int j = 1; j < n; j++) {
				if (i != j) {
					res = Math.min(res, graph[0][i] + graph[i][j] + graph[j][0]);
				}
			}
		}

		out.println(res >= CONST_INF ? -1 : res);

	}
```