diverta 2019 Programming Contest A&B&C&D

diverta 2019 Programming Contest

【解説放送：diverta 2019 Programming Contest 解説放送】
※サイトにリンクがないためここに貼っておく

E以降は手が出ないので一旦Dまで
(2019/05/13追記)
D問題：中学受験で典型らしく、参考サイトを追加

A問題

組み合わせの問題
- K個の連続する数値で何組作れるか？

例：N=6 , k=2

$N-K+1$組

	1	2	3	4	5	6
1組目	1	2
2組目		2	3
3組目			3	4
4組目				4	5
5組目					5	6

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

		out.println(numN - numK + 1);
	}

備忘:なんでこれ提出したんだ？

		long res = 0;
		for (int i = 0; i < numN - numK + 1; i++) {
			res++;
		}
		out.println(res);

B問題

COINの枚数のような奴
- $O(N^3)$がTLEだったので bの計算を簡略化すればどうにかなるのでは？ ということで
  - nが固定なので、rとgが決まればbは決まる はず
    - $(i * r + j * g) > n $
      - この場合はbを何個買ってもNG(そもそもnを超えてしまっている)
    - $(i * r + j * g) \leqq n $
      - この場合は、次の計算結果がbの倍数であるならちょうどn個購入可能
        
        　$n - (i * r + j * g)$

	private void solveB() {
		int r = nextInt();
		int g = nextInt();
		int b = nextInt();
		int n = nextInt();

		long res = 0;
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				int wk = i * r + j * g;
				if ((n - wk) >= 0 && (n - wk) % b == 0) {
					res++;
				}
			}
		}

		out.println(res);
	}

C問題:再帰Version

基本的な考え方は解説放送か解説PDFで
文字列を分類する
- B XXXX A (パターンA)
  - Bで始まり、Aで終わる
- B XXXX (パターンB)
  - Bで始まり、Aではない文字で終わる
- XXXX A (パターンC)
  - Bではない文字で始まり、Aで終わる
- XXXX
  - Bで始まらず、Aで終わらない

とりあえず、入力文字についてABが含まれるかをカウントしてしまう
最初のBと最後のAを持つ文字列について考える
3. B XXXX A と B XXXX
4. XXXX A と B XXXX A
5. XXXX A と B XXXX
6. B XXXX A と B XXXX A
組み合わせの内容
4. B XXXX A と B XXXX 　->　パターンAとパターンBを組み合わせると、パターンBができる
5. この組み合わせの時はパターンAのみ消費する
6. XXXX A と B XXXX A 　->　パターンCとパターンAを組み合わせると、パターンCができる
7. この組み合わせの時はパターンAのみ消費する
8. XXXX A と B XXXX 　->　パターンBとパターンCを組み合わせると消滅
9. この組み合わせの時はパターンBとパターンCを消費する
8. B XXXX A と B XXXX A -> パターンAとパターンAを組み合わせると、パターンAができる
9. パターンAを1つ消費する
組み合わせ方は上記で行けるが、パターンAの消費方法だけ注意する
5. パターンAは2つ以上ある場合は組み合わせられるが、1つの場合は組み合わせることができない
6. そのため、文字列の中でパターンAのみあった（パターンB,Cがない）場合は最後の1つを使い切ることができない
7. ただし、1つ以上パターンBまたはCがあった場合、以下のような組み合わせが可能なので最後の一つを使い切ることができる
8. パターンC + パターンA + パターンB ( XXXX A + B XXX A + B XXX)
9. パターンC + パターンA ( XXXX A + B XXX A)
10. パターンA + パターンB (B XXX A + B XXX)

コンテスト中は場合分けが思いつかず再帰で解いていた
memo化していますが、しなくても間に合いました
- memo化、最初は配列でやったけど、想定される最大値を入れたらOOMになってしまったのでMapに変更している

	private void solveC() {
		int numN = nextInt();
		String[] wk = new String[numN];
		long res = 0;
		int patternA = 0;
		int patternB = 0;
		int patternC = 0;
		for (int i = 0; i < wk.length; i++) {
			wk[i] = next();
			if (wk[i].charAt(0) == 'B' && wk[i].charAt(wk[i].length() - 1) == 'A') {
				patternA++;
			} else if (wk[i].charAt(0) == 'B' && wk[i].charAt(wk[i].length() - 1) != 'A') {
				patternB++;
			} else if (wk[i].charAt(0) != 'B' && wk[i].charAt(wk[i].length() - 1) == 'A') {
				patternC++;
			}
			String[] resA = wk[i].split("AB");
			res += resA.length - 1;
		}

		/*
		 * 最初、再帰で解いた
		 * [][][]でmemo化してみたけどOOM発生することがあるためMapに変更
		 *
		 * 以下、[][][]でもmemoコード
		 * int max = Integer.max(Integer.max(patternA, patternB), patternC) + 1;
		 * long[][][] memo = new long[max + 1][max + 1][max + 1];
		 * res += saikiC(patternA, patternB, patternC, 0, memo);
		 */
		Map<String, Long> memo = new HashMap<String, Long>();
		res += saikiC(patternA, patternB, patternC, 0, memo);

		out.println(res);
	}


	/**
	 *
	 * @param a patteernA
	 * @param b patteernB
	 * @param c patteernC
	 * @param pair BとCでpairを作ったまたは、AとB,AとCでpairを作った
	 *         そのため、pairが>0の場合は、patternAを最後の1つまで使い切ることができる
	 * @param memo
	 * @return
	 */
	//	private long saikiC(int a, int b, int c, int pair, long[][][] memo) {
	private long saikiC(int a, int b, int c, int pair, Map<String, Long> memo) {
		if (a <= 0 && (b <= 0 || c <= 0)) {
			return 0;
		} else if (b <= 0 && a <= 0 && c <= 0) {
			return 0;
		}
		String key = a + ":" + b + ":" + c;
		if (memo.containsKey(key)) {
			return memo.get(key);
		}
		long val1 = 0;
		long val2 = 0;
		long val3 = 0;

		if (b > 0 && c > 0) {
			val1 = saikiC(a, b - 1, c - 1, pair + 1, memo) + 1;
		} else if (a > 1 || (a > 0 && pair > 0)) {
			/*
			 * [pairがない=aのみで構成されている]場合は、aを最後まで使い切ることができない
			 * ただし、[pair>0=bとcまたは、aとb、aとcで組み合わせを行ったのでaのくっつけ先がある]場合は最後まで使い切ることができる
			 */
			val2 = saikiC(a - 1, b, c, pair, memo) + 1;
		} else if (a > 0 && (b > 0 || c > 0)) {
			val3 = saikiC(a - 1, b, c, pair + 1, memo) + 1;
		}
		long res = Long.max(val1, Long.max(val2, val3));
		memo.put(key, res);
		return res;
		//		return memo[a][b][c] = Long.max(val1, Long.max(val2, val3));
		//		return Long.max(val1, Long.max(val2, val3));
	}

C問題：単純な場合分け（解法を読んで整理した結果）

上の再帰でやっていた内容を整理するとこれだけ短くなる。。。
パターンAが0で、パターンBとパターンCが0よりも大きいなら、BとCの組み合わせ
パターンAが0より大きく、パターンBまたはパターンCも0より大きいなら、BとCの組み合わせ＋Aの個数
- AはBとCの間に挟むか、どちらかにつければよいのでAはすべて使い切れる
パターンAが0より大きく、パターンBとパターンCが0なら、Aの組み合わせのみ
- Aの最後の一つは使い切れない

	private void solveC() {
		int numN = nextInt();
		String[] wk = new String[numN];
		long res = 0;
		int patternA = 0;
		int patternB = 0;
		int patternC = 0;
		for (int i = 0; i < wk.length; i++) {
			wk[i] = next();
			if (wk[i].charAt(0) == 'B' && wk[i].charAt(wk[i].length() - 1) == 'A') {
				patternA++;
			} else if (wk[i].charAt(0) == 'B' && wk[i].charAt(wk[i].length() - 1) != 'A') {
				patternB++;
			} else if (wk[i].charAt(0) != 'B' && wk[i].charAt(wk[i].length() - 1) == 'A') {
				patternC++;
			}
			String[] resA = wk[i].split("AB");
			res += resA.length - 1;
		}

		/*
		 * 場合分けのみで行けた
		 */
		if (patternA == 0) {
			res += Long.min(patternB, patternC);
		} else if (patternA > 0 && (patternB > 0 || patternC > 0)) {
			res += patternA + Long.min(patternB, patternC);
		} else if (patternA > 0 && (patternB == 0 && patternC == 0)) {
			res += patternA - 1;
		}

		out.println(res);
	}

D問題

解法PDFと配信が良い
商と余りが等しいでググると分かりやすい解説がたくさん
$\lfloor n/m \rfloor \equiv n (\mod m)$
- それぞれの式の結果をKとすると $n = m*k+k$　となる
  - $\lfloor (m*k+k) / m \rfloor = k$
  - $(m*k+k) \mod m = k$
- $n = m*k+k$ を変形して、$n = k(m+1)$
  - $k*(m+1)$はNの倍数
  - $(m+1)$はNの約数
    - つまり、$m=Nの約数-1$
- Nの約数をリストアップして、$n=k((Nの約数-1)+1)$がなり立つか検証する

	/*
	 * 
	 * n = m*k+k
	 *   = k(m+1)
	 *
	 * (m+1)がNの約数なら、k*(m+1)はNの倍数
	 *   -> m=Nの約数-1なら、(m+1)はNの約数になる
	 *
	 */
	private void solveD() {
		long numN = nextLong();

		if (numN < 2) {
			out.println(0);
			return;
		}

		/*
		 * 約数のリストアップ
		 */
		long max = (long) Math.sqrt(numN);
		List<Long> wk = LongStream.range(1, max + 1).collect(() -> new ArrayList<Long>(), (t, i) -> {
			if (numN % i == 0) {
				t.add(i);
				if (i != numN / i) {
					t.add(numN / i);
				}
				//				if (i * i != numN && i <= numN / 2) {
				//					wk.add(numN / i);
				//				}
			}
		}, (t, u) -> {
			t.addAll(u);
		});

		/*
		 * 約数-1をとり出して以下を判定
		 * floor(n/約数-1) == n % 約数-1)
		 */
		long res = wk.stream().reduce(0L, (sum, i) -> {
			long tmp = i - 1;
			if (tmp > 0 && numN / tmp == numN % tmp) {
				sum += tmp;
			}
			return sum;
		});
		out.println(res);

	}

D問題：やりたいことはこれ。TLEになるけど。

表にしてみたやつ

	private void solveD2() {
		int numN = nextInt();
		long res = 0;

		for (int i = 1; i < numN; i++) {
			if (numN / i == numN % i) {
				res += i;
			}
		}

		out.println(res);
	}