diverta 2019 Programming Contest A&B&C&D diverta 2019 Programming Contest

[Explanatory Broadcast: diverta 2019 Programming Contest Commentary Broadcast]

There is no link on the site, so put it here.

――Since you can't get your hands after E, once you reach D

-(Added on May 13, 2019) Problem D: Added a reference site, which is typical of junior high school entrance exams

A problem

--Combination problem ――How many sets can you make with K consecutive numbers?

Example: N = 6, k = 2

$ N-K + 1 $ pair

	1	2	3	4	5	6
1st set	1	2
2nd set		2	3
3rd group			3	4
4th group				4	5
5th group					5	6

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

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

--Note: Why did you submit this?

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

B problem

--A guy like the number of COINs -Since $ O (N ^ 3) $ was TLE, what would happen if the calculation of b was simplified? So --Since n is fixed, b should be decided if r and g are decided - $(i * r + j * g) > n $ ――In this case, no matter how many b you buy, it is NG (it has exceeded n in the first place) - $(i * r + j * g) \leqq n $ --In this case, if the next calculation result is a multiple of b, you can purchase exactly n pieces. - 　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 Problem: Recursive Version

--The basic idea is in the commentary broadcast or the commentary PDF.

--Classify strings --B XXXX A (Pattern A) --Starts with B and ends with A --B XXXX (Pattern B) --Starts with B and ends with a non-A character --XXXX A (Pattern C) --Starts with a letter other than B and ends with A - XXXX --Does not start with B and does not end with A

For the time being, it counts whether AB is included in the input character.
Think of a string with a first B and a last A
B XXXX A and B XXXX
XXXX A and B XXXX A
XXXX A and B XXXX
B XXXX A and B XXXX A
Contents of the combination
B XXXX A and B XXXX-> Pattern B can be created by combining pattern A and pattern B.
In this combination, only pattern A is consumed.
XXXX A and B XXXX A-> Pattern C can be created by combining pattern C and pattern A.
Only pattern A is consumed in this combination.
XXXX A and B XXXX-> Disappear when pattern B and pattern C are combined
This combination consumes pattern B and pattern C
B XXXX A and B XXXX A-> Combining pattern A and pattern A creates pattern A
Consume one pattern A
The combination method can be done above, but pay attention only to the consumption method of pattern A.
Pattern A can be combined if there are two or more, but cannot be combined if there is one
Therefore, if there is only pattern A in the character string (no patterns B and C), the last one cannot be used up.
However, if there is one or more patterns B or C, the following combinations are possible, so the last one can be used up.
Pattern C + Pattern A + Pattern B (XXXX A + B XXX A + B XXX)
Pattern C + Pattern A (XXXX A + B XXX A)
Pattern A + Pattern B (B XXX A + B XXX)

――During the contest, I couldn't think of a case and solved it recursively. --It's a memo, but it was in time without it --Memoization, I did it with an array at first, but when I entered the maximum value expected, it became OOM, so I changed it to 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;
		}

		/*
		 *First solved by recursion
		 * [][][]I tried to make it memo, but changed to Map because OOM may occur
		 *
		 *Less than,[][][]But memo code
		 * 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 and C made a pair or A and B,I made a pair with A and C
	 *Therefore, the pair>If 0, patternA can be used up to the last one
	 * @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)) {
			/*
			 * [No pair=Consists of only a]If a cannot be used up to the end
			 *However,[pair>0=Since b and c or a and b, a and c are combined, there is a destination for a]If you can use it to the end
			 */
			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));
	}

Problem C: Simple case classification (result of reading and organizing the solution)

――If you organize the contents that were done by the above recursion, it will be shortened by this much. .. .. --If pattern A is 0 and pattern B and pattern C are greater than 0, then a combination of B and C --If pattern A is greater than 0 and pattern B or pattern C is also greater than 0, then the combination of B and C + the number of A --A can be sandwiched between B and C, or it can be attached to either, so all A can be used up. --If pattern A is greater than 0 and pattern B and pattern C are 0, then only the combination of A --The last one of A cannot be used up

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

		/*
		 *I was able to go only by case
		 */
		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 problem

--Solution PDF and delivery are good -[A lot of explanations that are easy to understand if you google because the quotient is equal to the remainder](https://www.google.com/search?q=%E5%95%86%E3%81%A8%E4%BD%99% E3% 82% 8A% E3% 81% 8C% E7% AD% 89% E3% 81% 97% E3% 81% 84 & oq =% E3% 81% 97% E3% 82% 87% E3% 81% 86% E3 % 81% A8% E3% 81% 82% E3% 81% BE% E3% 82% 8A & aqs = chrome.1.69i57j35i39j0l4.7025j0j4 & sourceid = chrome & ie = UTF-8)

\lfloor n/m \rfloor \equiv n (\mod m) --If the result of each expression is K, then $ n = m * k + k $ - \lfloor (m*k+k) / m \rfloor = k - (m*k+k) \mod m = k

-Transform $ n = m * k + k $ to $ n = k (m + 1) $ -$ k * (m + 1) $ is a multiple of N -$ (m + 1) $ is a divisor of N --That is, a divisor of $ m = N-1 $

--List the divisors of N and verify that $ n = k ((divisor of N-1) + 1) $ holds.

	/*
	 * 
	 * n = m*k+k
	 *   = k(m+1)
	 *
	 * (m+1)If is a divisor of N, then k*(m+1)Is a multiple of N
	 *   -> m=Divisor of N-If 1,(m+1)はDivisor of Nになる
	 *
	 */
	private void solveD() {
		long numN = nextLong();

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

		/*
		 *List of divisors
		 */
		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);
		});

		/*
		 *divisor-Take out 1 and judge the following
		 * floor(n/divisor-1) == n % divisor-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);

	}

Problem D: This is what I want to do. Although it will be TLE.

The one I tried on the table

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