LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@shihou22

ABC - 022 - A&B&C

Last updated at Posted at 2019-05-12

AtCoder ABC 022 A&B&C

AtCoder - 022

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

A問題

  • 取り込みごとに体重が適正範囲かどうか確認する
	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受粉するのでカウントする

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

		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|

	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|

	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);

	}
0
0
2

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
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?