ABC - 120 - A&B&C&D

AtCoder ABC 120 A&B&C&D

AtCoder - 120

2019/05/27
　問題名修正
　D問題のコードの書き方を修正 int[][]の生成部分

A - Favorite Sound

	private void solveA2() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numA = scanner.nextInt();
			int numB = scanner.nextInt();
			int numC = scanner.nextInt();

			int res = 0;
			if (numB / numA > numC) {
				res = numC;
			} else {
				res = numB / numA;
			}

			System.out.println(res);

		}
	}

B - K-th Common Divisor

• 割り切れるかどうかはすべて試してみないとわからない。。。
  • コメントに記述

	private void solveB() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numA = scanner.nextInt();
			int numB = scanner.nextInt();
			int numK = scanner.nextInt();

			List<Integer> wk = new ArrayList<Integer>();
			//その値が何番目の値か
			int cnt = 0;
			/*
			 * 何番目に大きいか？なので、
			 * 大きいほうから探していく。
			 * 小さいほうからだと探しづらいので。
			 * そして、AまたはBを割り切れる数なので、AまたはBより大きくなることはない。
			 * なので、AまたはBのうち、大きいほうが最大値
			 */
			for (int i = Math.max(numA, numB); i >= 1; i--) {
				if (numA % i == 0 && numB % i == 0) {
					cnt++;
				}
				/*
				 * 割り切れる
				 */
				if (cnt == numK) {
					System.out.println(i);
					return;
				}
			}

		}
	}

C - Unification

計算量削減Version

• 考え方は落ちものゲーと同じ
• 0と1を組み合わせて消した後は間が詰まる
  • どのような順序で消しても連鎖することが可能なので、消し方としては
    • 0と1の数を数える
    • 数が少ないほう×2倍の数を消せる

	private void solveC2() {

		try (Scanner scanner = new Scanner(System.in)) {
			char[] wkS;
			wkS = scanner.next().toCharArray();

			int cnt0 = 0;
			int cnt1 = 0;
			for (char c : wkS) {
				if (c == '0') {
					cnt0++;
				} else if (c == '1') {
					cnt1++;
				}
			}

			System.out.println(Math.min(cnt0, cnt1) * 2);

		}
	}

TLE解法

• とても無理くりやっている
• これでも解けるけど、、、TLEにはなる

	/*
	 * これはTLEになる解法
	 */
	private void solveC() {

		try (Scanner scanner = new Scanner(System.in)) {
			char[] wkS;
			wkS = scanner.next().toCharArray();

			List<Character> wk = new ArrayList<Character>();
			for (char c : wkS) {
				wk.add(c);
			}

			System.out.println(getList(wk));

		}
	}

	private int getList(List<Character> wk) {

		if (wk.size() < 2) {
			return 0;
		}

		int res = 0;
		int i1 = 0;
		int i2 = 1;
		/*
		 * 0-1の組み合わせがある初期位置を見つける
		 */
		for (int i = 1; i < wk.size(); i++) {
			if (wk.get(i) != wk.get(i - 1)) {
				i1 = i - 1;
				i2 = i;
				break;
			}
			if (i == wk.size() - 1) {
				return 0;
			}
		}
		/*
		 * 消せる限りリストからremoveする
		 */
		while (i2 < wk.size()) {

			char c1 = wk.get(i1);
			char c2 = wk.get(i2);
			if (c1 != c2) {
				wk.remove(i2);
				wk.remove(i1);
				res += 2;
			} else {
				i1 = i2;
				i2 = i2 + 1;
			}
		}
		return getList(wk) + res;
	}

D - Decayed Bridges

• 図は解説のyoutubeをみる

• 解放としては以下

  • 全ての頂点が接続されていない状態で不便さが最大の状態をスタートする
  • 1つずつ辺をつなぐことにより、不便さを解消していく

• Union Findの参考サイト
  重み付き Union-Find 木とそれが使える問題のまとめ、および、牛ゲーについて
  Union-Find木の解説と例題

/*
	 * Union Find(Disjoint Set)
	 */
	private void solveD() {

		try (Scanner scanner = new Scanner(System.in)) {
			int numN = scanner.nextInt();
			int numM = scanner.nextInt();

			int[][] wk = Stream.generate(() -> new int[] { scanner.nextInt() - 1, scanner.nextInt() - 1 }).limit(numM)
					.toArray(int[][]::new);
			//			int[][] wk = IntStream.range(0, numM).collect(() -> new int[numM][2],
			//					(t, i) -> {
			//						t[i][0] = scanner.nextInt() - 1;
			//						t[i][1] = scanner.nextInt() - 1;
			//					}, (t, u) -> {
			//						Stream.concat(Arrays.stream(t), Arrays.stream(u));
			//					});
			long maxFuben = ((long) numN * (long) (numN - 1)) / 2;

			/*
			 *
			 * 切り離す処理はつなぐ処理に出来る。
			 *回答の配列はMの長さ
			 */
			long[] res = new long[numM];
			res[numM - 1] = maxFuben;

			UnionFind unionFind = new UnionFind(numN);

		/*
			 * 最後が繋がったら点数に入らず
			 * なのでj>=1
			 * そして、全て繋がっているところから、全てを切り離していく作業を行う
			 * -> 最大の不便さの状態から、端をつなげることによって不便ではなくしていく作業
			 *
			 * * (1, 2)
			* (3, 4)
			* (1, 3)
			* (2, 3)
			* (1, 4)
			*
			* 最初(以下、[...]の中身はUnionFindのparentの中身)
			* [-1, -1, -1, -1]
			*
			*  (1, 4)が接続
			* [-2, -1, -1, 0]
			*
			* (2, 3)が接続
			* [-2, -2, 1, 0]
			*
			* (1, 3)が接続
			* [-4, 0, 1, 0]
			*
			* (3, 4)が接続...済
			* 3の親は、
			* 3 -> 1
			* 1 -> 0
			* 0 -> -4
			*
			* 4の親は、
			* 0 -> -4
			 */
			for (int j = wk.length - 1; j >= 1; j--) {

				//繋がっていなかった箇所が繋がった[
				int a = wk[j][0];
				int b = wk[j][1];
				if (unionFind.getRoot(a) != unionFind.getRoot(b)) {
					/*
					 * 親が違うのでつなぐ対象
					 * つなぐので、親のサイズ×親のサイズの組数分不便さが解消される
					 * 例：
					 * 1 - 2
					 * 3 - 4
					 * の組があったとき
					 * 2 - 3
					 * が繋がると、
					 *  1 - 3
					 *  1 - 4
					 *  2 - 3
					 *  2 - 4
					 *  の4組ができる。
					 */
					res[j - 1] = res[j] - ((long) unionFind.getSize(a) * (long) unionFind.getSize(b));
					unionFind.connect(a, b);
				} else {
					//最初から繋がっているので変化無し
					res[j - 1] = res[j];
				}

			}

			for (int j = 0; j < res.length; j++) {
				System.out.println(res[j]);
			}

		}
	}

	private static class UnionFind {
		/*
		 * 親の番号
		 * 親の場合は -(その集合のサイズ)
		 * にしておくと、その集合がどれくらいの子を持っているのかがわかる
		 *
		 */
		private int[] parentNo;

		/*
		 * 作るときはparentの値を全て-1にしておく
		 */
		public UnionFind(int size) {
			parentNo = new int[size];
			Arrays.fill(parentNo, -1);
		}

		private int getRoot(int a) {
			if (parentNo[a] < 0) {
				//親が-ということは自分が親
				return a;
			} else {
				/*
				 * 超重要
				 * 次の探索のために、親を付け替えておく
				 */
				return parentNo[a] = getRoot(parentNo[a]);
			}
		}

		/*
		 * 自分のいるグループの頂点数を調べる
		 */
		private int getSize(int a) {
			//親を取ってきたい
			int parent = getRoot(a);
			/*
			 * 親のサイズを調べる
			 * ×-1をしていないのは、
			 */
			return parentNo[parent];
		}

		/*
		 * AとBをくっつける
		 */
		private boolean connect(int a, int b) {
			//AとBを直接つなぐのではなく、root(a)にroot(b)をくっつける
			int wkA = getRoot(a);
			int wkB = getRoot(b);
			if (wkA == wkB) {
				//既にくっついています
				return false;
			}
			/*
			 * 大きい方(a)に小さい方(b)をくっつけたい
			 * 大小が逆だったらひっくり返す
			 */
			if (getSize(wkA) < getSize(wkB)) {
				int tmp = wkA;
				wkA = wkB;
				wkB = tmp;
			}
			//Aのサイズ更新
			parentNo[wkA] = parentNo[wkA] + parentNo[wkB];
			//Bの親をAに変更
			parentNo[wkB] = wkA;

			return true;

		}

		private boolean isSame(int a, int b) {

			int wkA = getRoot(a);
			int wkB = getRoot(b);
			return wkA == wkB;
		}

	}