ABC - 066- A&B&C

#AtCoder ABC 066 B&C
[AtCoder - 066](https://atcoder.jp/contests/abc066)

#A問題

 - 金額をソートして、最小と最大の差分をとる

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

		Arrays.sort(wk);

		out.println(wk[0] + wk[1]);
	}
```

#B問題

 - 文字列Sの最後から1文字削除することがスタート
 - 残りの文字で偶文字列がつくれなければ、最終文字を1文字削除する（実際に削除すると遅くなりそうなので削除はしないが）
 - 偶文字列は必ず偶数なので、残り文字列の半分が最大の文字列長となる
 - 最大文字列長から-2していき偶文字列かどうかを判断する
    - `ABBABBABBABC`とあった場合、
        - `ABBABBABBAB` 基準文字列
        - `ABBABBABBAB` 文字列長が奇数なので偶文字列は作れないので1文字削除
        - `ABBABBABBA`　文字列長が偶数なので偶文字列か判定
            - `ABBABBABBA` -> `ABBAB`と'BABBA'に分割して判定
        - `ABBABBAB`　マッチしなかったので-2削除
            - `ABBABBAB` -> `ABBA`と`BBAB`に分割して判定
        - `ABBABB`　マッチしなかったので-2削除  
            - `ABBABB` -> `ABB`と`ABB`に分割して判定
        - マッチしたので`ABB`の文字列長を2倍して出力


```java
	private void solveB() {
		String s = next();
		//後ろ1文字削除
		String wkS = s.substring(0, s.length() - 1);

		/*
		 * 半分にしてしまい、そこから同じ文字列が出現するかを調査
		 */
		for (int i = wkS.length() / 2; i > 0; i--) {
			//比較用文字列（前半分）
			String tmp = wkS.substring(0, i);
			//比較用文字列（後ろ半分。tmpと同じ文字列が、tmpの直後に出現するかの確認）
			String tmp2 = wkS.substring(i, i * 2);
			if (tmp.equals(tmp2)) {
				//0-iの文字列を二つ並べるので*2
				out.println(i * 2);
				return;
			}
		}

	}
```

#C問題

相変わらずTLEに悩んだ。。。
**ここにたどり着くまでの経過は、このページの下部にあるTLE実装集をしたからおってみるとわかりやすい**

 - 最初と最後にappendするから遅くなると考えたので、append対象をはじめから選択すればよいと考えた。

 - {$a_1 - a_4$}->{$1,2,3,4$}を考えてみる

 1. {$1$} ->$a_1$を空リストへ
 2. {$1$} ->前後を入れ替え
 3. {$1,2$} ->$a_2$をリストへ
 4. {$2,1$} ->前後を入れ替え
 5. {$2,1,3$} ->$a_3$をリストへ
 6. {$3,1,2$} ->前後を入れ替え
 7. {$3,1,2,4$} ->$a_4$をリストへ
 8. {$4,2,1,3$} ->前後を入れ替え

>奇数番目の要素{$a_i$}を操作した結果は、
**`偶数番の要素が先頭から降順に並び、奇数番の要素が偶数番の要素が並んだ後に昇順に並ぶ`**

>偶数番目の要素{$a_i$}を操作した結果は、
**`奇数番の要素が先頭から降順に並び、偶数番の要素が奇数番の要素が並んだ後に昇順に並ぶ`**

ことがわかる。

実際には、最終の要素が偶数番目か奇数番目かで切り替わる。（最終操作次第なので）

 - 実装は、昇順に追加するところを`文字列長が奇数だったら配列の1から、文字列長が偶数だったら配列の0から`と切り替えるだけでよい。
 - 逆順に追加するところは、文字列の最終から順次処理しているので`文字列長が偶数なら偶数番から、奇数なら奇数番からとなっている`

```java
	private void solveC() {
		int numN = nextInt();
		//		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
		int[] wk = new int[numN];
		for (int i = 0; i < wk.length; i++) {
			wk[i] = nextInt();
		}

		/*
		 * Ai番目が偶数なら偶数の逆順に追加
		 */
		StringBuilder builder = new StringBuilder();
		int start = wk.length % 2 == 0 ? 0 : 1;
		for (int i = wk.length - 1; i >= 0; i -= 2) {
			builder.append(wk[i]);
			builder.append(" ");
		}
		/*
		 * Ai番目が奇数なら奇数の昇順に追加
		 */
		for (int i = start; i < wk.length; i += 2) {
			builder.append(wk[i]);
			builder.append(" ");
		}
		out.println(builder.toString().trim());

	}
```
#C問題:TLE実装集

##Listに受けるのを止めて、直接StringBuilderを使ってみる

- Listに入れるから遅くなるのかと思ってBuilderに直接appendした
    - 結論として、変らなかった

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

		List<Integer> resList = new ArrayList<Integer>();
		int cnt = 1;
		StringBuilder builder = new StringBuilder();
		/*
		 * Ai番目が奇数なら先頭に追加、偶数なら最後に追加
		 *
		 */
		for (int i = 0; i < wk.length; i++) {
			if (cnt % 2 == 1) {
				builder.insert(0, wk[i]);
			} else {
				builder.append(wk[i]);
			}
			cnt++;
		}

		/*
		 * 奇数の場合はひっくりかえす
		 * 前後の空白文字列をtrim()で削除
		 */
		if (cnt % 2 == 1) {
			out.println(builder.reverse().toString().trim());
		} else {
			out.println(builder.toString().trim());
		}
	}

```

##再帰をやめてforで実装

 - 再帰が遅かったので速くなるかなって。。
 - Listにaddした後に順番を入れ替えるのをやめて、前後に挿入するようにした
 - 最後に奇数か偶数かで文字列をひっくり返した

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

		List<Integer> resList = new ArrayList<Integer>();
		int cnt = 1;
		/*
		 * Ai番目が奇数なら先頭に追加、偶数なら最後に追加
		 *
		 */
		for (int i = 0; i < wk.length; i++) {
			if (cnt % 2 == 1) {
				resList.add(0, wk[i]);
			} else {
				resList.add(wk[i]);
			}
			cnt++;
		}

		StringBuilder builder = new StringBuilder();
		for (Integer integer : resList) {
			builder.append(integer);
			builder.append(" ");
		}
		/*
		 * 奇数の場合はひっくりかえす
		 * 前後の空白文字列をtrim()で削除
		 */
		if (cnt % 2 == 1) {
			out.println(builder.reverse().toString().trim());
		} else {
			out.println(builder.toString().trim());
		}
	}
```

##一番最初の実装（再帰）

 - 問題文どおりに実装。再帰を使う。

```java
	private void solveC2() {

		int numN = nextInt();
		int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();

		List<Integer> resList = new ArrayList<Integer>();
		for (int i : wk) {
			resList = getList(i, resList);
		}

		StringBuilder builder = new StringBuilder();
		for (Integer integer : resList) {
			builder.append(integer);
			builder.append(" ");
		}
		out.println(builder.toString());
	}

	private List<Integer> getList(int tmp, List<Integer> wkList) {
		wkList.add(tmp);
		List<Integer> resList = new ArrayList<Integer>();
		for (int i = wkList.size() - 1; i >= 0; i--) {
			resList.add(wkList.get(i));
		}
		return resList;
	}
```