ABC - 027 - A&B&C

AtCoder ABC 027 A&B&C

AtCoder - 027

A問題

• 3つの数字の内、2つは同じで1つ違う。違う1つを探す。
  • 2つを弾いて1つにしたい
  • XORしいていくと、打ち消せなかったものが残る

	private void solveA() {
		int wk = IntStream.range(0, 3).map(i -> nextInt()).reduce(0, (sum, i) -> sum ^ i);
		out.println(wk);
	}

A問題:無理やりstream

• なんかびみょー
• そもそも
  • Mapから条件に合致した値を取り出すのはcollectでいいのか？
  • このパターンだと条件に合致するのは1つのみというのが保証されているのでfindFirst()でもいいのか？

Stream難しい

	private void solveA2() {
		int[] wk = IntStream.range(0, 3).map(i -> nextInt()).toArray();
		Map<Integer, Long> resA = Arrays.stream(wk).mapToObj(i -> new Integer(i))
				.collect(Collectors.groupingBy(i -> i, Collectors.counting()));

		List<Entry<Integer, Long>> res = resA.entrySet().stream().filter(i -> i.getValue() != 2)
				.collect(Collectors.toList());
		//		Optional<Entry<Integer, Long>> res = resA.entrySet().stream().filter(i -> i.getValue() != 2).findFirst();
		out.println(res.get(0).getKey());
	}

B問題

• 累積和と愚直実装を両方試した

  • 片方コメントアウトしてある

• 人が流れるイメージ

i	1	橋	2	橋	3	橋	4	橋	5	平均人数
0	5	-							10	3
1	3	-	2	-					10	3
2	3	-	2	-		-			10	3
3	3	-	2	-		-		-	10	3
4	3	-	3	-	3	-	3	-	3	3

i	1	橋	2	橋	3	橋	4	橋	5	平均人数
0		-	10		5					3
1	3	-	7	-	5					3
2	3	-	3	-	9	-				3
3	3	-	3	-	3	-	6	-		3
4	3	-	3	-	3	-	3	-	3	3

• 橋が必要か否かは「片側にいる人数が、島×平均と同じか否か」のみで判定している

  • 多ければ、そこの島の人を減らすために橋が必要
  • 少なければ、そこの島に人を送るために橋が必要

• 下図だと、1-3の間に橋を架けたら1-3は平均になった

i	1	橋	2	橋	3	橋	4	橋	5	平均人数
0		-	9				3		3	3
1	3	-	6	-			3		3	3
2	3	-	3	-	3		3		3	3

• この例だと、4-5にも橋を架ける必要がある
  • 4-5の橋から左を見た時に、(3×4 - 9 != 0 )となっている

i	1	橋	2	橋	3	橋	4	橋	5	平均人数
0		-	9						6	3
1	3	-	6	-					6	3
2	3	-	3	-	3			-	6	3
3	3	-	3	-	3		3	-	3	3

	private void solveB() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		int sum = Arrays.stream(wk).sum();
		if (sum == 0) {
			out.println(0);
			return;
		}
		if (sum % numN != 0) {
			out.println(-1);
			return;
		}

		int avg = sum / numN;
		int cnt = 0;

		/*  ここまではどっちの実装方法でも同じ */

		//------------------------------------------------------------------------
		/*
		 * 累積和version
		 */
		int[] forW = new int[numN];
		for (int i = 0; i < numN; i++) {
			if (i == 0) {
				forW[i] = wk[i];
			} else {
				forW[i] += forW[i - 1] + wk[i];
			}

		}
		/*
		 * 最初は、0(i-1)から1(i)に橋が必要か否か？
		 * 　->なので、スタートは1から。橋の最大値がN-1なので0(or N)のどちらかは対象外
		 * 必要 -> 0(i-1)地点の人口が平均値と違う（多いか少ないかはどうでもよい）
		 * 不要 -> 0(i-1)地点の人口が平均値と同じ
		 *
		 * i-1からiに橋が必要か否か
		 * 必要 -> sum(i-1)と、(i-1)*平均値が違う（多いか少ないかはどうでもよい）
		 * 不要 -> sum(i-1)と、(i-1)*平均値が同じ
		 */
		for (int i = 1; i < numN; i++) {
			if (forW[i - 1] != i * avg) {
				cnt++;
			}
		}
		//------------------------------------------------------------------------
		/*
		 * 愚直実装version
		 */
		//		for (int i = 1; i < numN; i++) {
		//			int sumLeft = 0;
		//			for (int j = 0; j < i; j++) {
		//				sumLeft += wk[j];
		//			}
		//			int sumRight = 0;
		//			for (int j = i; j < numN; j++) {
		//				sumRight += wk[j];
		//			}
		//			if (sumLeft != i * avg || sumRight != (numN - i) * avg) {
		//				cnt++;
		//			}
		//		}
		//------------------------------------------------------------------------
		out.println(cnt);
	}

C問題

• 解法見ないと分からなかった。未だになんとなくしかわかっていない。
  • 図示できるのだけど、言葉で説明できない。。。
• 解法:P.16~

	private void solveC() {
		long numN = nextLong();

		/*
		 * 深さを調べる
		 */
		int depthCnt = 0;
		for (long n = numN; n > 0; n >>= 1) {
			depthCnt++;
		}

		long cnt = 1;

		/*
		 * 深さが偶数の場合は[ 2*n ]　からスタート
		 * 深さが奇数の場合は[ 2*n+1 ]　からスタート
		 */
		int adjust = depthCnt % 2;
		/*
		 * 最初の数字をカウント出来なかったらAokiの勝利
		 * これ以降は、
		 * AokiがカウントできなかったらTakahashiの勝利
		 * TakahashiがカウントできなかったらAokiの勝利
		 * を交互に勝つまで繰り返す。
		 * 多分、LongのMAXまでリピートしておけばいいんだろうけど、自信がないのでwhileで
		 */
		boolean who = true;
		while (true) {
			cnt = 2 * cnt + adjust;
			if (cnt > numN) {
				out.println(who ? "Aoki" : "Takahashi");
				return;
			}
			who = !who;
			adjust = 1 - adjust;

		}

	}