ABC - 121- A&B&C&D

#AtCoder ABC 121 A&B&C&D
[AtCoder - 121](https://atcoder.jp/contests/abc121)

**2019/05/22**
　問題名を追記

#A - White Cells

3行2列の表を、2行1列塗る場合

|---|---|
|:-:|:-:|
|●|●|
|●|●|
||●|


```java
	private void solveA() {
		Scanner scanner = null;
		int numH = 0;
		int numW = 0;
		int h = 0;
		int w = 0;

		try {
			scanner = new Scanner(System.in);
			numH = scanner.nextInt();
			numW = scanner.nextInt();
			h = scanner.nextInt();
			w = scanner.nextInt();

			int total = numH * numW;
			int col = h * numW;
			int row = w * (numH - h);
			System.out.println(total - col - row);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}
```

#B - Can you solve this?

 - 問題文通りに実装
    - $i個$のソースコードについて次の操作を行う
        - $A_{11}×B_{11}+A_{12}×B_{12}+$  -------  $+A_{1M}×B_{1M} + C > 0$
        - 上記がtrueとなるソースコードの個数を求める

```java
	private void solveB() {
		Scanner scanner = null;
		int numN = 0;
		int numM = 0;
		int numC = 0;

		try {
			scanner = new Scanner(System.in);
			numN = scanner.nextInt();
			numM = scanner.nextInt();
			numC = scanner.nextInt();
			int[] bArray = new int[numM];
			int[][] aArray = new int[numN][numM];

			for (int i = 0; i < bArray.length; i++) {
				bArray[i] = scanner.nextInt();

			}
			for (int i = 0; i < aArray.length; i++) {
				for (int j = 0; j < aArray[i].length; j++) {
					aArray[i][j] = scanner.nextInt();
				}
			}
			int cnt = 0;

			for (int i = 0; i < aArray.length; i++) {
				int res = 0;
				for (int j = 0; j < aArray[i].length; j++) {
					res += (aArray[i][j] * bArray[j]);
				}
				if (res + numC > 0) {
					cnt++;
				}
			}

			System.out.println(cnt);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}
```

#C - Energy Drink Collector

 - M本買うために必要な最小の資金
 - まず安い順にお店を並べる
    - 安いお店から順に買っていく
        - 残り必要な栄養ドリンクが在庫よりも多いなら、在庫全部購入し次のお店へ
        - 残り必要な栄養ドリンクが在庫よりも少ないなら、必要数分だけ買っておしまい

```java
	private void solveC() {
		Scanner scanner = null;
		int numN = 0;
		long numM = 0;

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

			Long[][] wk = new Long[numN][2];

			for (int i = 0; i < numN; i++) {
				wk[i][0] = scanner.nextLong();
				wk[i][1] = scanner.nextLong();
			}

			Arrays.sort(wk, new LComp());

			long resNumM = numM;
			long res = 0;
			for (int i = 0; i < wk.length; i++) {
				if (resNumM <= 0) {
					break;
				}
				long key = wk[i][0];
				long value = wk[i][1];
				if (resNumM >= value) {
					res += (key * value);
					resNumM -= value;
				} else {
					res += (key * resNumM);
					resNumM = 0;
				}

			}

			System.out.println(res);

		} finally {
			if (scanner != null) {
				scanner.close();
			}
		}
	}

	public static class LComp implements Comparator<Long[]> {

		@Override
		public int compare(Long[] o1, Long[] o2) {
			return Long.compare(o1[0], o2[0]);
		}

	}
```

#D - XOR World

 - 解説はコードにインラインで記載

一応、2進数の0-10までを記載しておく

|10進数||2進数5桁目|2進数4桁目|2進数3桁目|2進数2桁目|2進数1桁目|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|10||0|1|0|1|0|
|9||0|1|0|0|1|
|8||0|1|0|0|0|
|7||0|0|1|1|1|
|6||0|0|1|1|0|
|5||0|0|1|0|1|
|4||0|0|1|0|0|
|3||0|0|0|1|1|
|2||0|0|0|1|0|
|1||0|0|0|0|1|
|0||0|0|0|0|0|

```java
	private void solveD3() {
		long numA = 0;
		long numB = 0;

		try (Scanner scanner = new Scanner(System.in)) {
			numA = scanner.nextLong();
			numB = scanner.nextLong();
			long res = calcD3(numB) ^ calcD3(numA - 1);
			System.out.println(res);
		}
	}

	/**
	 * この関数は0-numまでxorした結果の値
	 * @param num
	 * @return
	 */
	private long calcD3(long num) {
		if (num <= 0) {
			return 0;
		}
		/*
		 * 4の時に、0,1,2,3,4までになるので、これは5つの整数まで
		 * なので、帳尻合わせで1足してあげる。
		 */
		num++;
		/*
		 * 10^3 <= 2^10
		 * 1000 <= 1024
		 * 10^12 <= 2進数 40桁くらい
		 */

		long res = 0;

		//i桁目の偶奇を調べる
		for (int i = 0; i < 50; i++) {
			/*
			 * 01の切り替わる周期を指定
			 * 2進数の1桁目    2桁目   3桁目
			 *  1                1      1
			 *  0                1      1
			 *                   0      1
			 *                   0      1
			 *                          0
			 *                          0
			 *                          0
			 *                          0
			 *
			 * 0桁目　→(2進数の1桁目)                 2
			 * 1                                       4
			 * 2                                       8
			 */
			long loop = ((long) 1 << (long) (i + 1));

			/*
			 * ここで求めているのはnumを周期で割って何周期か？
			 * (num / loop)= 何周期でてくるのか？
			 * 例：num=8(+1)　2進数の2桁目(周期4)
			 * 　　9 / 4 = 2(余り1)
			 *
			 * そして、その中に何回1がでてくるのか？
			 * (loop / 2)=周期の中の1の個数
			 * 例：2進数の2桁目(周期4)の時の周期当たりの1の個数
			 *     4 / 2 = 2
			 *
			 *
			 *  num=8(+1)　2進数の2桁目(周期4)の場合、
			 *  ( 9 / 4 ) * ( 4 / 2 ) = 4
			 *  となる。
			 *  ただし、端数はここでは気にしない。
			 *
			 *  num=8(+1)の2進数2桁目だけ抜き出すと以下になる。
			 *  8  0
			 *  7  1
			 *  6  1
			 *  5  0
			 *  4  0
			 *  3  1
			 *  2  1
			 *  1  0
			 *  0  0
			 *  このうち、ここで抜き出しているのは0～7まで。
			 *  8(+1)の0は1回で抜き出せないので後回し。
			 */
			long cnt = (num / loop) * (loop / 2);
			//00000.....0011111.....11

			/*
			 * 端数をカウントする
			 *
			 * numを周期で割った際の端数を計算
			 * (num % loop) =端数
			 * 例：num=8(+1)の2進数の余り部分を求める
			 * 下記の数値はnum=8(+1)の2進数2桁目だけ抜き出した時の値
			 * 今回求めるのは、周期の途中で終わっているものを抜き出す作業
			 *  8  0
			 *  7  1
			 *  6  1
			 *  5  0
			 *  4  0
			 *  3  1
			 *  2  1
			 *  1  0
			 *  0  0
			 *
			 * 端数が0だったら除外しないといけないので0を除外するため0分の数を引く
			 * (loop / 2)=0の個数
			 * 周期4の場合以下のように01が出現する
			 *  1
			 *  1
			 *  0
			 *  0
			 * そのため、loop/2が0の出現個数となる
			 *
			 * (num % loop) - (loop / 2)=端数から0の個数を引くと残るのは1の個数
			 * ただし、1が出現しない場合この個数は<=0となる。
			 * そのため、0より下の場合は0に戻している。
			 *
			 * 例１：NUM=8(+1)の2進数2桁目の場合
			 * (9 % 4) = 1 端数1
			 * 4 /2 = 2　0の個数2
			 * 1-2 = -1 < 0なので端数側の1の個数は0
			 *
			 * 例２：NUM=10(+1)の場合
			 * (11 % 4) = 2
			 * 4 /2 = 2
			 * 2 -2 = 0なので端数側の1の個数は1
			 *
			 * 本体の1の個数（端数ではないほう）
			 * (11 / 4) * (4 / 2) = 5
			 *
			 * 本体+端数
			 * 5 + 0 = 0
			 *
			 * 例示：11の2進数2桁目
			 *  10   1
			 *   9   0
			 *   8   0
			 *   7   1
			 *   6   1
			 *   5   0
			 *   4   0
			 *   3   1
			 *   2   1
			 *   1   0
			 *   0   0
			 */
			cnt += Math.max(0, (num % loop) - (loop / 2));
			/*
			 * その桁の1の数が奇数だったら足し算
			 * とはいってもこれは10進数の足し算ではなくて2進数の足し算
			 * 例1：
			 * i=0
			 * 1 << 0 = 0 (  00)
			 * i=1
			 * 1 << 1 = 2 (  10)
			 * i=2
			 * 1 << 2 = 4 ( 100)
			 * i=3
			 * 1 << 3 = 8 (1000)
			 *
			 * 全部足すと
			 *
			 *         14 (1110)
			 *
			 * 例2：
			 * i=0
			 * 1 << 0 = 0 (  00)
			 * i=1
			 * 1 << 1 = 2 (  10)
			 * i=2
			 * 1が偶数なのでなし
			 * i=3
			 * 1 << 3 = 8 (1000)
			 *
			 * 全部足すと
			 *
			 *         10 (1010)
			 * シフト演算の結果、返り値は0-numまでxorした結果の値
			 */

			if (cnt % 2 == 1) {
				res += (long) 1 << i;
			}
		}
		return res;
	}

```