[JAVA] Concours de programmation diverta 2019 A & B & C & D

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

[Diffusion des commentaires: diffusion des commentaires du concours de programmation diverta 2019]

• Il n'y a pas de lien sur le site, alors mettez-le ici.

• Puisque vous ne pouvez pas mettre la main dessus après E, une fois jusqu'à D

• (Ajouté le 13 mai 2019) Problème D: Ajout d'un site de référence, qui est typique des examens du premier cycle du secondaire

Un problème

--Problème de combinaison ――Combien d'ensembles pouvez-vous créer avec K nombres consécutifs?

Exemple: N = 6, k = 2

$ N-K + 1 $ paire

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

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

--Remarque: Pourquoi avez-vous soumis cela?

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

Problème B

• Un gars comme le nombre de COIN -Comme $ O (N ^ 3) $ était TLE, que se passerait-il si le calcul de b était simplifié? Alors
• Puisque n est fixé, b doit être décidé si r et g sont décidés - $(i * r + j * g) > n $ ―― Dans ce cas, peu importe le nombre de b que vous achetez, c'est NG (il a dépassé n en premier lieu) - $(i * r + j * g) \leqq n $
• Dans ce cas, si le résultat du prochain calcul est un multiple de b, vous pouvez acheter exactement n pièces. - 　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);
	}

Problème C: version récursive

• L'idée de base est un commentaire diffusé ou un commentaire PDF

--Classifier les chaînes --B XXXX A (modèle A)

• Commence par B et se termine par A -B XXXX (modèle B)
• Commence par B et se termine par une lettre autre que A --XXXX A (modèle C)
• Commence par une lettre autre que B et se termine par A
  • XXXX --Ne commence pas par B et ne se termine pas par A

1. Pour le moment, comptez si AB est inclus dans le caractère d'entrée
2. Pensez à une chaîne avec un premier B et un dernier A
3. B XXXX A et B XXXX
4. XXXX A et B XXXX A
5. XXXX A et B XXXX
6. B XXXX A et B XXXX A
7. Contenu de la combinaison
8. B XXXX A et B XXXX-> Le motif B peut être créé en combinant le motif A et le motif B.
9. Avec cette combinaison, seul le motif A est consommé
10. XXXX A et B XXXX A-> Le motif C peut être créé en combinant le motif C et le motif A.
11. Seul le motif A est utilisé dans cette combinaison
12. XXXX A et B XXXX-> disparaît lorsque le motif B et le motif C sont combinés
13. Cette combinaison utilise le modèle B et le modèle C
14. B XXXX A et B XXXX A-> La combinaison du motif A et du motif A crée le motif A
15. Consommez un motif A
16. La méthode de combinaison peut être effectuée ci-dessus, mais ne faites attention qu'à la méthode de consommation du modèle A.
17. Le motif A peut être combiné s'il y en a deux ou plus, mais ne peut pas être combiné s'il y en a un.
18. Par conséquent, s'il n'y a que le motif A dans la chaîne de caractères (pas de motifs B et C), le dernier ne peut pas être utilisé.
19. Cependant, s'il y a un ou plusieurs motifs B ou C, les combinaisons suivantes sont possibles, de sorte que le dernier peut être utilisé.
20. Motif C + Motif A + Motif B (XXXX A + B XXX A + B XXX)
21. Motif C + Motif A (XXXX A + B XXX A)
22. Motif A + Motif B (B XXX A + B XXX)

«Pendant le concours, je ne pouvais pas penser à un cas et je l'ai résolu de manière récursive.

• C'est un mémo, mais c'était à temps sans ça --Mémo, au début je l'ai fait avec un tableau, mais quand j'ai mis la valeur maximale attendue, il est devenu OOM, donc je l'ai changé en 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;
		}

		/*
		 *Résolu d'abord par récursif
		 * [][][]J'ai essayé d'en faire un mémo, mais je suis passé à Map car un MOO peut se produire
		 *
		 *Moins que,[][][]Mais le code mémo
		 * 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
	 * @la paire de paramètres B et C fait une paire ou A et B,J'ai fait une paire avec A et C
	 *Par conséquent, la paire>Si 0, patternA peut être utilisé jusqu'au dernier
	 * @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)) {
			/*
			 * [Pas de paire=Se compose uniquement d'un]Si a ne peut pas être utilisé jusqu'à la fin
			 *cependant,[pair>0=Puisque b et c ou a et b, a et c sont combinés, il y a une destination pour a]Si vous pouvez l'utiliser jusqu'au bout
			 */
			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));
	}

Problème C: classification simple des cas (résultat de la lecture et de l'organisation de la solution)

――Si vous organisez le contenu qui a été fait par la récurrence ci-dessus, il sera raccourci d'autant. .. .. --Si le motif A est égal à 0 et que le motif B et le motif C sont supérieurs à 0, alors une combinaison de B et C --Si le motif A est supérieur à 0 et le motif B ou le motif C est également supérieur à 0, alors la combinaison de B et C + le nombre de A -A peut être pris en sandwich entre B et C, ou il peut être attaché à l'un ou l'autre, de sorte que tout A peut être utilisé. --Si le motif A est supérieur à 0 et que le motif B et le motif C sont 0, seule la combinaison de A

• Le dernier de A ne peut pas être utilisé

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

		/*
		 *Je n'ai pu y aller que par cas
		 */
		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);
	}

Problème D

• La solution PDF et la livraison sont bonnes

• [Beaucoup d'explications qui sont faciles à comprendre si vous google car le quotient est égal au reste](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) --Si le résultat de chaque expression est K, alors $ n = m * k + k $ - \lfloor (m*k+k) / m \rfloor = k - (m*k+k) \mod m = k

-Transformer $ n = m * k + k $ en $ n = k (m + 1) $

• $ k * (m + 1) $ est un multiple de N

• $ (m + 1) $ est une fraction de N

• Autrement dit, une fraction de $ m = N-1 $

• Lister les fractions de N et vérifier si $ n = k ((fraction de N-1) + 1) $ est

	/*
	 * 
	 * n = m*k+k
	 *   = k(m+1)
	 *
	 * (m+1)Si est une fraction de N, alors k*(m+1)Est un multiple de N
	 *   -> m=Fait de N-Si 1,(m+1)はFait de Nになる
	 *
	 */
	private void solveD() {
		long numN = nextLong();

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

		/*
		 *Liste d'environ
		 */
		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);
		});

		/*
		 *diviseur-Retirez 1 et jugez ce qui suit
		 * floor(n/diviseur-1) == n % diviseur-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);

	}

Problème D: C'est ce que je veux faire. Bien que ce soit TLE.

Celui que j'ai essayé sur la 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);
	}