ABC - 046- A&B&C

AtCoder ABC 046 A&B&C

AtCoder - 046

A問題

• 面倒だったのでMapで調べた。setでも良かった。

	private void solveA() {

		Map<Integer, Integer> wk = IntStream.range(0, 3).collect(() -> new HashMap<Integer, Integer>(),
				(t, i) -> {
					t.merge(nextInt(), 1, (oldV, newV) -> oldV + newV);
				},
				(t, u) -> {
					t.putAll(u);
				});

		out.println(wk.size());
	}

B問題

• 次のボールにぬれる色は何か？

  • 最初のボールは$(K)$の中から選べる
  • 次のボールは$(K-1)$の中から選べる（選べる色は一色少ない）
  • その次のボールは$(K-1)$の中から選べる（選べる色は一色少ない）
  • 　以下、$(N-1)$まで同じ
    • 　$(N-1)$なのは、最初の1つは$(K)$の中から選んでいるので

• $(K)*(K-1)^{N-1}$　通りの選び方がある

	/*
	 * 10個 8色
	 *  8 7(8-1：隣の色を抜く) 7(8-1：隣の色を抜く)  7(8-1：隣の色を抜く) 7(8-1：隣の色を抜く) 7(8-1：隣の色を抜く) ・・・・
	 */
	private void solveB() {
		long numN = nextLong();
		long numK = nextLong();

		long res = (long) numK * (long) Math.pow(numK - 1, numN - 1);

		out.println(res);
	}

C問題

回数	比率A	比率B	票数A	票数B	合計
1	2	3	2	3	5
2	1	1	3	3	6
3	3	2	6	4	10

• 常に前の票数以上にならないといけない
• 前の票数が $A:B$　であり、 次の比率が $x:y$ の場合 $A ≤ nx ∧ B ≤ ny $　を満たす $整数n$ を求める
• $整数n=max(⌈A/x⌉, ⌈B/y⌉)$

/*
	 * 床関数 x 以下の最大整数を表す
	 * 天井関数
	 */
	private void solveC() {
		int numN = nextInt();

		long[][] wk = IntStream.range(0, numN).collect(() -> new long[numN][2],
				(t, i) -> {
					t[i][0] = nextLong();
					t[i][1] = nextLong();
				}, (t, u) -> {
					Stream.concat(Arrays.stream(t), Arrays.stream(u));
				});

		/*
		 * 得票数を保持する配列
		 */
		long[][] memo = new long[numN][2];
		/*
		 * 最初の値はそのまま得票数
		 */
		memo[0][0] = wk[0][0];
		memo[0][1] = wk[0][1];
		chkC(wk, memo, 1);

		out.println(memo[numN - 1][0] + memo[numN - 1][1]);
	}

	private void chkC(long[][] wk, long[][] memo, int currentI) {

		if (currentI >= wk.length) {
			return;
		}

		/*
		 * 今回の比率
		 */
		long x = wk[currentI][0];
		long y = wk[currentI][1];

		/*
		 * 前回の得票数
		 */
		long a = memo[currentI - 1][0];
		long b = memo[currentI - 1][1];

		/*
		 * 前回の得票数A <= n * 今回の比率A
		 * 前回の得票数B <= n * 今回の比率B
		 * 上記を満たす最小のn（ただし整数）を求める
		 *
		 * 式としては下記
		 * 前回の得票数A / 今回の比率A <= n
		 * 前回の得票数B / 今回の比率B <= n
		 * 普通に割ると小数が出てしまうのでBigDecimalでRoundUpしている
		 */
		long p13 = new BigDecimal(a).divide(new BigDecimal(x), RoundingMode.UP).longValue();
		long p24 = new BigDecimal(b).divide(new BigDecimal(y), RoundingMode.UP).longValue();

		/*
		 * nを求める
		 * 小さい方のnだと片側の条件を満たさないため、大きい方
		 */
		long base = Math.max(p13, p24);

		/*
		 * nを求めたので今回の投票数が決まる
		 */
		memo[currentI][0] = base * x;
		memo[currentI][1] = base * y;

		chkC(wk, memo, currentI + 1);
	}