ABC - 066- A&B&C

AtCoder ABC 066 B&C

AtCoder - 066

A問題

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

	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倍して出力

	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からと切り替えるだけでよい。
• 逆順に追加するところは、文字列の最終から順次処理しているので文字列長が偶数なら偶数番から、奇数なら奇数番からとなっている

	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した
  • 結論として、変らなかった

	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した後に順番を入れ替えるのをやめて、前後に挿入するようにした
• 最後に奇数か偶数かで文字列をひっくり返した

	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());
		}
	}

一番最初の実装（再帰）

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

	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;
	}