[JAVA] ABC --122 --A & B & C & D

AtCoder - 122

Le problème C n'a pas pu percer le devant et TLE ... Ne devrait-il pas être traité ensemble à la fin? J'ai remarqué que je me suis retrouvé coincé dans un bug et que j'ai fini. 2019/04/17 Post-scriptum D

2019/05/22 Ajoutez le nom du problème

A - Double Helix

La base ʻA C G T` est sortie. Je me souviens de mes années de premier cycle.

Peu importe si vous changez, sinon, ou définissez la valeur initiale dans Map. Si vous pensez que c'est beau, est-ce la carte?

	private void solveA() {
		String wk = next();
		if (wk.equals("A")) {
			System.out.println("T");
		} else if (wk.equals("T")) {
			System.out.println("A");
		} else if (wk.equals("G")) {
			System.out.println("C");
		} else if (wk.equals("C")) {
			System.out.println("G");
		}

	}

B - ATCoder

Extrait une sous-chaîne de la chaîne S et génère la plus longue longueur de la sous-chaîne Cependant, seul «ACGT» peut être inclus dans la sous-chaîne. Soit double pour soit récursif. J'aime la récurrence, alors je réponds par récursivité.

Vérifiez la chaîne de caractères S caractère par caractère depuis le début. Se sentir comme ci-dessous

• ATCODER
• TCODER
• CODER
• ODER
• DER
• ER
• R

	private void solveB() {
		String s = next();
		int res = 0;
		for (int i = 0; i < s.length(); i++) {
			int wkRes = getLength(s, i, 0);
			res = Math.max(wkRes, res);
		}

		out.println(res);
	}

** Traitement à juger par récursif ** Si le caractère suivant est ʻACGT, ajoutez +1 au total et recherchez le caractère suivant. Si le caractère suivant n'est pas ʻACGT, la sous-chaîne s'arrête là et renvoie le total à ce moment. Ceci est inutile si la chaîne de caractères est longue. Il ne peut pas être traité par pour.

• Conditions de sortie --Si l'index actuel dépasse la longueur de la chaîne

En regardant en arrière, carAt est plus rapide que sous-chaîne, n'est-ce pas? .. ..

	private int getLength(String wk, int currentI, int total) {
		if (currentI >= wk.length()) {
			return total;
		}
		String wkS = wk.substring(currentI, currentI + 1);
		if (wkS.equals("A") || wkS.equals("T") || wkS.equals("G") || wkS.equals("C")) {
			return getLength(wk, currentI + 1, total) + 1;
		} else {
			return total;
		}
	}

C - GeT AC Pour faire simple, je pensais que les exigences suivantes seraient faciles à résoudre.

--Selon la chaîne S

• Obtenir des sous-chaînes commençant par li à partir de la chaîne S et se terminant par ri ―― Combien d'étages le mot AC apparaît-il dans la sous-chaîne?

Si la longueur de la chaîne de caractères n'est pas 10 ^ 5 et que la condition d'acquisition de la chaîne de caractères secondaire n'est pas 10 ^ 5 ...

Accelérer

―― Comptez les endroits où ils apparaissent une fois et notez-les. --li-> ri est jugé en soustrayant le nombre d'occurrences, pas par la chaîne de caractères.

private void solveC3() {
		int numN = nextInt();
		int numQ = nextInt();
		String strS = next();
		int[][] wk = new int[numQ][2];

		for (int i = 0; i < wk.length; i++) {
			wk[i][0] = nextInt();
			wk[i][1] = nextInt();
		}

Image du tableau de comptage uniquement

--Lorsque ʻAC apparaît, compter à la position de C --Une fois que vous avez créé la séquence ci-dessus, vous pouvez obtenir le nombre d'occurrences de ʻAC en faisant ri-li.

• Les points doivent être comptés à la position C

** Exemple ** Compter à la position «C»

Compter à la position «A»

		/*
		 *Préparez d'abord un tableau pour le comptage
		 *La séquence de numéros que vous souhaitez créer a la forme suivante (le compte change entre A et C)
		 * A  C  A  C  T  A  C  G
		 * 0, 1, 1, 2, 2, 2, 3, 3
		 *
		 *
		 *Cela n'est pas pratique.
		 *Il est difficile de juger quand seul C est attrapé en position de départ et quand seul A est attrapé en position finale.
		 * A  C  A  C  T  A  C  G
		 * 1, 1, 2, 2, 2, 3, 3, 3
		 */
		int[] wkA = new int[strS.length()];
		char[] wkL = strS.toCharArray();
		int cnt = 0;
		for (int i = 1; i < strS.length(); i++) {
			/*
			 * "AC"Je cherche la ficelle.
			 *Ce qui change le nombre entre A et C est"AC"Le décompte ne changera que lorsque vous recevrez l'ensemble.
			 *Si la position finale est uniquement A, le dernier AC est exclu.
			 *Si la position finale est accrochée à C, le dernier courant alternatif est inclus.
			 *Si la position de départ est accrochée à A, il semble que le premier AC n'est pas inclus, mais dans le dernier calcul+À faire (pour être exact-Pas fini)
			 *Si la position de départ est seulement C, le premier AC semble être inclus, mais dans le dernier calcul-Sera fait.
			 */

			if (wkL[i] == 'C' && wkL[i - 1] == 'A') {
				cnt++;
			}
			wkA[i] = cnt;

		}

À la fin, il suffit de soustraire. Avec cette implémentation, il faut moins d'une seconde pour réussir le cas de test sur le site.

		for (int[] is : wk) {
			int start = is[0];
			int last = is[1];

			int total = wkA[last - 1] - wkA[start - 1];

			System.out.println(total);
		}

	}

À partir de là, une collection d'implémentations ayant échoué du problème C

Politique de mise en œuvre

• La chaîne de sous-caractères est soigneusement coupée de la chaîne de caractères S, et le nombre d'AC inclus est déterminé.

Cette méthode ne sera pas à temps pour le délai. ** 10 ^ 5 * 10 ^ 5 * Nombre d'opérations de chaîne **

Ce qui suit est un exemple d'implémentation qui a travaillé dur pour "découper une chaîne de caractères partielle de la chaîne de caractères S et déterminer combien de ʻAC`s sont inclus".

• Dans ce cas, "découper une sous-chaîne de la chaîne S et déterminer combien de ʻAC` sont inclus" sera exécuté jusqu'à 10 ^ 5 fois.

** Découpez une chaîne de caractères partielle dans la chaîne de caractères S ** Implémentation

	private void solveC() {
		int numN = nextInt();
		int numQ = nextInt();
		String strS = next();
		int[][] wk = new int[numQ][2];

		for (int i = 0; i < wk.length; i++) {
			wk[i][0] = nextInt();
			wk[i][1] = nextInt();
		}

		for (int[] is : wk) {
			String wkS = strS.substring(is[0] - 1, is[1]);
			int res = 0;
			for (int i = 0; i < wkS.length(); i++) {
				String firstS = wkS.substring(i, i + 1);
				boolean isNextA = firstS.equals("A");
				int wkRes = 0;
				if (isNextA) {
					wkRes = getLengthC(wkS, i, 0);
				}
				res = Math.max(wkRes, res);
			}
			System.out.println(res);
		}

	}

Modèle 1: fonction de récurrence

	private int getLengthC(String wk, int currentI, int total) {
		if (currentI >= wk.length() - 1) {
			return total;
		}
		String wkS = wk.substring(currentI, currentI + 2);
		if (wkS.equals("AC")) {
			return getLengthC(wk, currentI + 2, total) + 1;
		} else {
			return getLengthC(wk, currentI + 1, total);
		}
	}

Motif 2: traitement séquentiel avec indexOf

				int num = 0;
				while (num != -1) {
					num = wk.indexOf("AC");
					if (num != -1) {
						total++;
						wk = wk.substring(2, wk.length());
					}
				}

Motif 3: Obtenez la longueur avec la chaîne d'origine en excluant ʻAC` de la chaîne avec remplacer

				total = (wk.length() - wk.replace("AC", "").length()) / 2;

Motif 4: Convertissez la chaîne de caractères en un tableau avec ʻAC` comme délimiteur et comptez le nombre

C'est une mise en œuvre approximative, mais un peu plus de jugement est nécessaire.

				if (wk.lastIndexOf("AC") == 3) {
					total = wk.split("AC").length;
				} else {
					total = wk.split("AC").length - 1;
				}

Motif 5: correspondance de motif

				Pattern p = Pattern.compile("AC");
				Matcher m = p.matcher(wk);
				int s = 0;
				while (m.find(s)) {
					total++;
					s = m.end();
				}

Modèle 6: comptez tranquillement

				String[] wkL = wk.split("");
				for (int i = start + 1; i < last;) {
					if (wkL[i].equals("C") && wkL[i - 1].equals("A")) {
						total++;
						i += 2;
					} else {
						i++;
					}
				}

DD - We Like AGC

Numérotez les lettres et exécutez DP en fonction des chiffres ci-dessous

――Toujours quels personnages peuvent être ajoutés cette fois? DP basé sur . ―― Compte tenu de ce qui précède, ** Quels caractères ne peuvent pas être ajoutés cette fois? Si vous le définissez sur **, le nombre de modèles à considérer diminuera.

[Modèle NG]

	private void solveD() {
		int numN = nextInt();

		final long CONST_RES = (long) (Math.pow(10, 9) + 7);

		int[][][][] wk = new int[101][4][4][4];
		wk[0][3][3][3] = 1;

		//Longueur de chaine
		for (int strLength = 0; strLength < numN; strLength++) {
			//3 caractères avant la fin
			for (int c3 = 0; c3 < 4; c3++) {
				//2 caractères avant la fin
				for (int c2 = 0; c2 < 4; c2++) {
					//Un personnage avant la fin
					for (int c1 = 0; c1 < 4; c1++) {

						if (wk[strLength][c3][c2][c1] == 0)
							continue;

						//Personnages que je veux ajouter cette fois
						for (int c0 = 0; c0 < 4; c0++) {

							/*
							 *S'il s'agit de deux caractères avant, aucun caractère ne peut être ajouté cette fois
							 * ->Arrête de compter
							 *Cependant, comme cela ne peut pas être fait, il sera mis à 0 en ne le calculant pas pour le moment.
							 */
							if (c2 == 0 && c1 == 1 && c0 == 2)
								continue;
							if (c2 == 0 && c1 == 2 && c0 == 1)
								continue;
							if (c2 == 1 && c1 == 0 && c0 == 2)
								continue;
							/*
							 *Le caractère à ajouter cette fois est C(=2)Uniquement dans le cas de, les 3 premiers caractères
							 *Ne peut pas être ajouté dans les conditions suivantes
							 */
							if (c3 == 0 && c1 == 1 && c0 == 2)
								continue;
							if (c3 == 0 && c2 == 1 && c0 == 2)
								continue;

							/*
							 *Vous pouvez entrer le numéro de la chaîne de caractères précédente dans ce caractère
							 * ->Cette chaîne de caractères contient
							 */
							wk[strLength + 1][c2][c1][c0] += wk[strLength][c3][c2][c1];
							wk[strLength + 1][c2][c1][c0] %= CONST_RES;
						}
					}
				}
			}
		}
		long res = 0;
		for (int c3 = 0; c3 < 4; c3++) {
			for (int c2 = 0; c2 < 4; c2++) {
				for (int c1 = 0; c1 < 4; c1++) {
					res += wk[numN][c3][c2][c1];
					res %= CONST_RES;
				}
			}
		}

		out.println(res);
	}