ABC - 027 - A&B&C

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

#A問題

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

```java
	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難しい

```java
	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|

```java
	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~](https://www.slideshare.net/chokudai/abc027)

```java
	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;

		}

	}
```