ABC - 016 - A&B&C

AtCoder ABC 016 A&B&C

AtCoder - 016

A - 12月6日

	private void solveA() {
		int m = nextInt();
		int d = nextInt();
		out.print(m % d == 0 ? "YES" : "NO");
	}

B - A±B Problem

	private void solveB() {
		int a = nextInt();
		int b = nextInt();
		int c = nextInt();

		boolean p = a + b == c;
		boolean m = a - b == c;

		if (p && m) {
			out.println("?");
		} else if (!p && !m) {
			out.println("!");
		} else if (p && !m) {
			out.println("+");
		} else if (!p && m) {
			out.println("-");
		}

	}

C - 友達の友達

• 無向グラフの頂点間の距離を求める
  • 友達を頂点とする
  • 友達との距離は1（友達間の距離は同じ）
  • 友達の友達は頂点間の距離が2
  • 友達の友達の友達は頂点間の距離が3

そろそろワーシャルフロイド法以外での解き方覚えないと。。。

	private void solveC() {
		int n = nextInt();
		int m = nextInt();

		int[] a = new int[m];
		int[] b = new int[m];
		int[][] graph = new int[n][n];
		for (int i = 0; i < n; i++) {
			//MAXで埋めておく
			Arrays.fill(graph[i], Integer.MAX_VALUE / 2);
			//自分への移動コストは0
			graph[i][i] = 0;
		}
		for (int i = 0; i < m; i++) {
			a[i] = nextInt() - 1;
			b[i] = nextInt() - 1;
			//隣接行列の作成
			graph[a[i]][b[i]] = 1;
			graph[b[i]][a[i]] = 1;
		}

		//ワーシャルフロイド法
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					graph[j][k] = Integer.min(graph[j][k], graph[j][i] + graph[i][k]);
				}
			}
		}

		/*
		 * 自分からの移動コスト
		 * 1=友達
		 * 2=友達の友達
		 * 3=友達の友達の友達
		 * 4=友達の友達の友達の友達・・・
		 * 以下続く
		 */
		for (int i = 0; i < graph.length; i++) {
			int res = 0;
			for (int j = 0; j < graph.length; j++) {
				res += graph[i][j] == 2 ? 1 : 0;
			}
			out.println(res);
		}
	}