ABC - 129- A&B&C&D

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

Bで50分以上溶かして途中泣きそうでしたまる

EとFは解法みて今月中に更新する！

#A - Airplane

入力例を見て混乱したが、まぁ普通に読めば以下を問われているのがわかるよね。。。

 - A-BとB-CとC-Aを移動するのに必要な時間が与えられるから、A-B-C全て回ることができる最短時間を求める

```java
	private void solveA() {
		int p = nextInt();
		int q = nextInt();
		int r = nextInt();

		out.println(Math.min(q + r, Math.min(p + q, p + r)));
	}
```

#B - Balance

入力例２がなぜそうなるのか理解できなくて大分溶かしました。。。
理由？何故か、入力したのをソートするべき！と思い込んだからですね。
自戒のためにコメントアウトでソートを残してる。。。

解法としては、以下

 - iを1 - N-1まで動かして、0-i番目迄の合計とi+1 - N番目迄の合計の差が一番小さい値を出す

で、本番では累積和使いました（入力例2が理解できなくて「全探索じゃないよね？」的な思い込みが、、、）がやりすぎ。。

###累積和

```java
	private void solveB() {
		int n = nextInt();
		int[] wk = IntStream.range(0, n).map(i -> nextInt()).toArray();
		//	sortedなんて入れるから...　int[] wk = IntStream.range(0, n).map(i -> nextInt()).sorted().toArray();

		int[] rui = new int[n];
		//0-Nの累積和を行う
		rui[0] = wk[0];
		for (int i = 1; i < rui.length; i++) {
			rui[i] = rui[i - 1] + wk[i];
		}
		long res = Integer.MAX_VALUE / 10;
		/*
		 * 実際にT候補の数値を探すためにiを1からn-1まで移動させる
		 * 2グループに分けるためには、一番最初または最後まで行ってはいけない
		 * (rui[n - 1] - rui[i]) -> i+1からNまでの和
		 * rui[i] -> 0からiまでの和
		 */
		for (int i = 1; i < n - 1; i++) {
			res = Math.min(res, Math.abs((rui[n - 1] - rui[i]) - rui[i]));
		}

		out.println(res);
	}
```

###全探索版

 - sum1とsum2のところ、もっときれいに書けると思うんですがちょっと思いついてません。

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

		long res = Integer.MAX_VALUE / 10;
		for (int i = 1; i < n - 1; i++) {
			int sum1 = 0;
			int sum2 = 0;
			for (int j = 0; j < n; j++) {
				if (j <= i) {
					sum1 += wk[j];
				} else {
					sum2 += wk[j];
				}
			}
			res = Math.min(res, Math.abs(sum1 - sum2));
		}

		out.println(res);
	}
```

#C - Typical Stairs

 - 問題名通り、本当にTypicalなDP
    - DPのサイズを`n+1`ではなくて`n+3`にすれば、`i + 2 <= n`や`i + 1 <= n`の判定いらない

###参考
自分も全部終わらせていない(高配点問題全然解けない！)けど以下のコンテストがお役に立ちます。

[AtCoder - Educational DP Contest / DP まとめコンテスト](https://atcoder.jp/contests/dp/)
[AtCoder - Typical DP Contest](https://atcoder.jp/contests/tdpc)
[drkenさんの記事：動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集](https://qiita.com/drken/items/dc53c683d6de8aeacf5a)
[drkenさんの記事：Educational DP Contest の F ～ J 問題の解説と類題集](https://qiita.com/drken/items/03c7db44ccd27820ea0d)

※今回は配る方で実装。後で貰う方でも実装してみる

```java
	private void solveC() {
		int n = nextInt();
		int m = nextInt();
		Set<Integer> key = new HashSet<Integer>();
		for (int i = 0; i < m; i++) {
			key.add(nextInt());
		}

		long[] dp = new long[n + 1];
		dp[0] = 1;
		long CONST_MOD = (long) (Math.pow(10, 9) + 7);
		for (int i = 0; i <= n; i++) {
			if (key.contains(i)) {
				continue;
			}
			if (i + 2 <= n) {
				dp[i + 2] = dp[i + 2] % CONST_MOD + dp[i] % CONST_MOD;
			}
			if (i + 1 <= n) {
				dp[i + 1] = dp[i + 1] % CONST_MOD + dp[i] % CONST_MOD;
			}
		}

		out.println(dp[n] % CONST_MOD);
	}
```

#D - Lamp

 - 結構典型的な累積和の問題だった気がする

 - 縦と横でそれぞれ累積和をとって最後に重ね合わせるイメージ
    - 縦に何マス照らせるのか？横に何マス照らせるのか？を最初に作っておく
    - コード途中にコメントで入力例1をもとにどんな操作をしているかを記載
 - 累積をしておくことによって、[i][j]を見た際、Hの累積和の結果とWの累積和の結果を足すことができる

コンテスト中にコメント入れながら書いているからコード書くの遅いんだろうな

```java
	private void solveD2() {
		int h = nextInt();
		int w = nextInt();
		char[][] wk = new char[h][w];
		for (int i = 0; i < wk.length; i++) {
			wk[i] = next().toCharArray();
		}
		int[][] rui1 = new int[h][w];
		/*
		 * Wについて累積和を作成
		 */
		for (int i = 0; i < h; i++) {
			int cnt = 0;
			/*
			 * 入力例1だと、以下みたいな感じ(横並び)
			 * 012012
			 * 123450
			 * 123401
			 * 010123
			 */
			for (int j = 0; j < w; j++) {
				if (wk[i][j] == '.') {
					cnt++;
				} else {
					cnt = 0;
				}
				rui1[i][j] = cnt;
			}
			/*
			 * 累積した結果をならす(横並び)
			 * 012012
			 * 123450
			 * 123401
			 * 010123
			 * を
			 * 022022
			 * 555550
			 * 444401
			 * 010333
			 * に変換
			 */
			for (int j = w - 1; j > 0; j--) {
				if (rui1[i][j - 1] != 0 && rui1[i][j] != 0) {
					rui1[i][j - 1] = rui1[i][j];
				}
			}
		}

		int[][] rui2 = new int[h][w];
		/*
		 * Hについて累積和を作成
		 */
		for (int j = 0; j < w; j++) {
			int cnt = 0;
			/*
			 * 入力例1だと、以下みたいな感じ(縦並び)
			 * 011011
			 * 122120
			 * 233201
			 * 040312
			 */
			for (int i = 0; i < h; i++) {
				if (wk[i][j] == '.') {
					cnt++;
				} else {
					cnt = 0;
				}
				rui2[i][j] = cnt;
			}
			/*
			 * 累積した結果をならす(縦並び)
			 * 011011
			 * 122120
			 * 233201
			 * 040312
			 * を
			 * 043021
			 * 243320
			 * 243302
			 * 040312
			 * に変換
			 */
			for (int i = h - 1; i > 0; i--) {
				if (rui2[i - 1][j] != 0 && rui2[i][j] != 0) {
					rui2[i - 1][j] = rui2[i][j];
				}
			}
		}

		/*
		 * 累積してあるので全てなめる
		 * ただし、上下左右が重なっている中央部分を-1する
		 */
		long res = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				long cnt = rui1[i][j] + rui2[i][j] - 1;
				res = Math.max(res, cnt);
			}
		}

		out.println(res);
	}
```