ABC - 067- A&B&C

AtCoder ABC 067 A&B&C

AtCoder - 067

A問題

• A,B,A+B が 3の倍数かどうかを調べる
• 3の倍数であれば3匹で分けることができる

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

		if (numA % 3 == 0 || numB % 3 == 0 || (numA + numB) % 3 == 0) {
			out.println("Possible");
		} else {
			out.println("Impossible");
		}

	}

B問題

• 与えられた棒のうち、長いほうからN個とってつなげるのが一番長くなる
• 入力をソートして長いほうから入力値を合算

	private void solveB() {
		int numN = nextInt();
		int numK = nextInt();

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

		Arrays.sort(wk);

		int res = IntStream.range(0, numN).filter(i -> i >= numN - numK).reduce(0, (sum, i) -> {
			sum += wk[i];
			return sum;
		});

		out.println(res);
	}

C問題

• カードの山の上から順にX枚とって、残りをアライグマに渡す
  • すぬけが$\sum_{a_0}^{a_i}$
  • あらいぐまが$\sum_{a_{i+1}}^{a_N}$
  • $|\sum_{a_o}^{a_i}-\sum_{a_{i+1}}^{a_N}|$が一番小さい値を求める

山の上から順に取るのでソートなどという行為はしてはいけません。読解力が足りないと時間が溶けます。

	private void solveC() {
		int numN = nextInt();
		int[] wk = new int[numN];
		long raccoon = 0;
		for (int i = 0; i < wk.length; i++) {
			wk[i] = nextInt();
			raccoon += wk[i];
		}
		/**
		 * 「山の上からとる」という記述を見逃していた、、、
		 * 山の上からなので、先頭から順に取っていかないといけない。
		 */
		//		Arrays.sort(wk);

		long res = Long.MAX_VALUE;
		long sunuke = 0;
		//最後の1個まで計算するとsunukeにすべての数字が偏ってしまうので1個だけraccoonに残す
		for (int i = 0; i < wk.length - 1; i++) {
			sunuke += wk[i];
			raccoon -= wk[i];
			res = Math.min(res, Math.abs(raccoon - sunuke));
		}
		out.println(res);

	}

C問題：TLE実装

問題をよく読まなかったので上からではなくランダムに取得すると考えてしまった。
そのため、再帰を利用して実装した。
一応解答としてはあっているのだが、TLEとなってしまう。

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

		Arrays.sort(wk);

		if (wk.length == 2) {
			out.println(Math.abs(wk[0] - wk[1]));
		} else {
			out.println(saikiC(wk, 0, 0, 0, 0, 0));
		}
	}

	private long saikiC(int[] wk, int currentI, long sunuke, long raccoon, int sunukeCnt, int raccoonCnt) {
		if (currentI > wk.length - 1) {
			if (sunukeCnt == 0 || raccoonCnt == 0) {
				return Integer.MAX_VALUE;
			} else {
				return Math.abs(sunuke - raccoon);
			}
		}

		//今回のはすぬけ
		long val1 = saikiC(wk, currentI + 1, sunuke + wk[currentI], raccoon, sunukeCnt + 1, raccoonCnt);

		//今回のはあらいぐま
		long val2 = saikiC(wk, currentI + 1, sunuke, raccoon + wk[currentI], sunukeCnt, raccoonCnt + 1);

		return Math.min(val1, val2);
	}