ABC - 124- A&B&C&D

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

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

#A - Buttons

 - 大きい方をカウントする
 - 大きい方は-1される
 - 上記を2回

```java
	private void solveA() {
		int numA = nextInt();
		int numB = nextInt();

		int cnt = 0;
		for (int i = 0; i < 2; i++) {
			if (numA > numB) {
				cnt += numA;
				numA--;
			} else {
				cnt += numB;
				numB--;
			}
		}

		out.println(cnt);
	}
```

 - よりも、、、以下のソースの方がわかりやすい。
 - パターンは3パターンしかないので列挙すれだけ

```java
	ans = max(ans, A + A - 1);
	ans = max(ans, A + B);
	ans = max(ans, B + B - 1);
```

#B - Great Ocean View

海を見ることが出来るのは赤い位置のみ
![case1.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/365572/28e833fd-4241-acfb-f292-4b6ad4c6e2a1.jpeg)

![case3.JPG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/365572/fead8e41-7e42-898c-8797-bf16515362d9.jpeg)

 - 今見ている山が、今までに出現した一番高い山より高いなら海が見える

```java
	private void solveB() {
		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		int cnt = 1;
		int baseHeight = wk[0];
		for (int i = 1; i < wk.length; i++) {
			if (baseHeight <= wk[i]) {
				cnt++;
			}
			baseHeight = Math.max(baseHeight, wk[i]);
		}

		out.println(cnt);
	}

```

#C - Coloring Colorfully

 並び替えるパターンは2つしかない

  - 黒白黒白黒白黒白
  - 白黒白黒白黒白黒

どちらのパターンが並び替えるときに一番手数が少ないかを比較する


```java
	private void solveC() {
		String[] wk = next().split("");

		int bC = 0;//奇数を白から黒くする
		int wC = 0;//奇数を黒から白くする
		int bC2 = 0;//偶数を白から黒くする
		int wC2 = 0;//偶数を黒から白くする

		for (int i = 0; i < wk.length; i++) {

			if (i % 2 != 0) {
				if (wk[i].equals("0")) {
					//奇数を白くするときの回数
					wC++;
				} else {
					//奇数を黒くするときの回数
					bC++;
				}
			} else {
				if (wk[i].equals("0")) {
					//偶数を白くするときの回数
					wC2++;
				} else {
					//偶数を黒くするときの回数
					bC2++;
				}

			}
		}

		int val1 = bC + wC2;
		int val2 = bC2 + wC;
		out.println(Math.min(val1, val2));
	}
```

#D問題:複数の解法を記載

 - 解説のyoutubeを見るのが一番わかりやすい
 - 解説を基にした内容をコードにインラインで記述

 - どの解法も以下の作業を前提にしている
    - 1(2個)-0(1個)-1(1個)-0(..個)-1(..個) という1が何個続いて、0が何個続いて...という形に変換するところは共通
    - 上記の様な配列を生成し、その後どうやってカウントするのか？で分かれる

##D - Handstand:全探索

```java
/*
	 * 実行時間が長い版
	 */
	private void solveD3() {
		int numN = nextInt();
		int numK = nextInt();
		String[] wk = next().split("");

		List<Integer> oneZeroList = new ArrayList<Integer>();
		//今見ている数
		int now = 1;
		//いくつこの数が続いているのか
		int cnt = 0;
		/*
		 * 1-0-1-0-1
		 */
		for (int i = 0; i < wk.length; i++) {

			/*
			 * iが0か1かを判定している
			 * wk[i].charAt(0) == (char) ('0' + now)
			 */
			if (wk[i].charAt(0) == (char) ('0' + now)) {
				cnt++;
			} else {
				oneZeroList.add(cnt);
				cnt = 1;
				/*
				 * 0と1を切り替えるテクニック
				 * now ^=1でのおｋ
				 */
				now = 1 - now;
			}

		}
		/*
		 * 0のまま、または、1のまま終わった場合の処理
		 */
		if (cnt != 0) {
			oneZeroList.add(cnt);
		}
		/*
		 * 1-0-1-0-1-0-1の配列が欲しい
		 * 1-0-1-0-1-0 で終わっていたら1を足す
		 */
		if (oneZeroList.size() % 2 == 0) {
			oneZeroList.add(0);
		}

		//ここより上は全処理共通------------------------------------------------
		int countRange = 2 * numK + 1;
		int res = 0;

		/*
		 * 1-0-1-0-1....と詰まっているのを数え上げていく
		 * なので、奇数番しか使わない
		 *
		 * テストケース1の
		 * 14 2
		 * 11101010110011
		 * を例に取ると、1,0の配列は以下になる。
		 * 3 1 1 1 1 1 2 2 2
		 * 1 0 1 0 1 0 1 0 1
		 * 上記の様な1-0リストを以下の様にループしてカウントする
		 * 3+1+1+1+1
		 *     1+1+1+1+2
		 *         1+1+2+2+2
		 */
		for (int i = 0; i < oneZeroList.size(); i += 2) {

			int temp = 0;
			int left = i;
			int right = Math.min(i + countRange, oneZeroList.size());
			/*
			 * 選択位置から、countRange内の個数を数える
			 */
			for (int j = left; j < right; j++) {
				temp += oneZeroList.get(j);
			}
			res = Math.max(res, temp);
		}

		out.println(res);

	}

```

##D - Handstand:累積和

```java
/*
	 * 実行時間が短い版
	 * 累積和
	 */
	private void solveD() {
		int numN = nextInt();
		int numK = nextInt();
		String[] wk = next().split("");

		List<Integer> oneZeroList = new ArrayList<Integer>();
		int now = 1;
		int cnt = 0;
		for (int i = 0; i < wk.length; i++) {
			if (wk[i].charAt(0) == (char) ('0' + now)) {
				cnt++;
			} else {
				oneZeroList.add(cnt);
				cnt = 1;
				now = 1 - now;
			}
		}
		if (cnt != 0) {
			oneZeroList.add(cnt);
		}
		if (oneZeroList.size() % 2 == 0) {
			oneZeroList.add(0);
		}

		int countRange = 2 * numK + 1;

		//ここより上は全処理共通------------------------------------------------
		//累積和用の配列
		int[] resList = new int[oneZeroList.size() + 1];

		/*
		 * 累積和用配列に詰めていく
		 * テストケース1の
		 * 14 2
		 * 11101010110011
		 * を例に取ると、1,0の配列は以下になる。
		 * 3 1 1 1 1 1 2 2 2
		 * 1 0 1 0 1 0 1 0 1
		 * 上記の様な1-0リストだとしたら
		 * 累積和用配列には以下の様に詰められる
		 * resListのindex  0 1 2 3 4 5 6  7  8  9
		 * resListのvalue  0 3 4 5 6 7 8 10 12 14
		 * 0->1に変換可能な回数は2回
		 * なので、5この幅を取りたい
		 */
		for (int j = 0; j < oneZeroList.size(); j++) {
			resList[j + 1] = resList[j] + oneZeroList.get(j);
		}

		int res = 0;
		for (int i = 0; i < oneZeroList.size(); i += 2) {

			//次のleft,rightを計算する[left,right)
			int left = i;
			int right = Math.min(i + countRange, oneZeroList.size());
			int temp = resList[right] - resList[left];
			res = Math.max(res, temp);
		}

		out.println(res);

	}

```

##D - Handstand:しゃくとり法

 - よくわかってない

```java
/*
	 * 実行時間が短い版
	 * 尺取り法
	 */
	private void solveD2() {
		int numN = nextInt();
		int numK = nextInt();
		String[] wk = next().split("");

		List<Integer> oneZeroList = new ArrayList<Integer>();
		int now = 1;
		int cnt = 0;
		for (int i = 0; i < wk.length; i++) {

			if (wk[i].charAt(0) == (char) ('0' + now)) {
				cnt++;
			} else {
				oneZeroList.add(cnt);
				cnt = 1;
				now = 1 - now;
			}

		}
		if (cnt != 0) {
			oneZeroList.add(cnt);
		}
		if (oneZeroList.size() % 2 == 0) {
			oneZeroList.add(0);
		}

		//ここより上は全処理共通------------------------------------------------
		int countRange = 2 * numK + 1;
		int res = 0;

		/*
		 * forループの外側にleft/rightを持つ
		 */
		int left = 0;
		int right = 0;

		/*
		 *  [left, right) のsum
		 *  ->半開区間
		 *  left以上、right未満
		 *  ()　より大きい、より小さい -> 両端を含まない
		 *  []　以上、以下 -> 両端を含む
		 */
		int temp = 0;

		/*
		 * 1-0-1-0-1....と詰まっているのを数え上げていく
		 * なので、奇数番しか使わない
		 */
		for (int i = 0; i < oneZeroList.size(); i += 2) {

			/*
			 * 次のleft,rightを計算する
			 */
			int nextLeft = i;
			int nextRight = Math.min(i + countRange, oneZeroList.size());

			//左端を移動する
			while (nextLeft > left) {
				temp -= oneZeroList.get(left);
				left++;

			}

			//右端を移動する
			while (nextRight > right) {
				temp += oneZeroList.get(right);
				right++;
			}
			res = Math.max(res, temp);
		}

		out.println(res);

	}
```