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

AtCoder - 122

C Problem konnte nicht vorne durchbrechen und TLE ... Sollte es am Ende nicht zusammen verarbeitet werden? Ich bemerkte, dass ich in einem Fehler steckte und endete. 2019/04/17 D Nachschrift

2019/05/22 Fügen Sie den Problemnamen hinzu

A - Double Helix

Gibt die Basis aus, die der Basis von A`` C`` G`` T entspricht. Ich erinnere mich an meine Studienzeit.

Es spielt keine Rolle, ob Sie wechseln oder den Anfangswert in Map festlegen. Wenn Sie denken, dass es schön ist, ist es Karte?

	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

Extrahiert einen Teilstring aus dem String S und gibt die längste Länge des Teilstrings aus Es darf jedoch nur "ACGT" in der Teilzeichenfolge enthalten sein. Entweder doppelt für oder rekursiv. Ich bevorzuge eine Wiederholung, also antworte ich durch Rekursion.

Überprüfen Sie die Zeichenfolge S von Anfang an zeichenweise. Ich fühle mich wie unten

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

** Verarbeitung nach rekursiv zu beurteilen ** Wenn das nächste Zeichen "ACGT" ist, addieren Sie +1 zur Summe und suchen Sie nach dem nächsten Zeichen. Wenn das nächste Zeichen nicht "ACGT" ist, endet der Teilstring dort und gibt die Summe zu diesem Zeitpunkt zurück. Dies ist nutzlos, wenn die Zeichenfolge lang ist. Es kann nicht von für verarbeitet werden.

• Ausgangsbedingungen
• Wenn der aktuelle Index die Länge der Zeichenfolge überschreitet

Rückblickend ist charAt schneller als Teilzeichenfolgen, nicht wahr? .. ..

	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 Einfach ausgedrückt dachte ich, dass die folgenden Anforderungen leicht zu lösen sind.

--Gegeben Sie die Zeichenfolge S.

• Holen Sie sich Teilzeichenfolgen, die mit li aus String S beginnen und mit ri enden ――Wie viele Stockwerke erscheint das Wort AC in der Teilzeichenfolge?

Wenn die Länge der Zeichenfolge nicht 10 ^ 5 beträgt und die Erfassungsbedingung der Unterzeichenfolge nicht 10 ^ 5 ist ...

Beschleunigen

――Zählen Sie die Stellen, an denen sie einmal erscheinen, und notieren Sie sie. --li-> ri wird durch Subtrahieren der Anzahl der Vorkommen beurteilt, nicht durch die Zeichenkette.

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

Bild eines Nur-Zähl-Arrays

• Wenn "AC" erscheint, zählen Sie an der Position "C" hoch
• Sobald Sie das obige Array erstellt haben, können Sie die Anzahl der Vorkommen von "AC" ermitteln, indem Sie "ri-li" ausführen. --Punkte sollten an der Position "C" hochgezählt werden

** Beispiel ** Zählen Sie an der Position "C" hoch

Zählen Sie an der Position "A" hoch

		/*
		 *Bereiten Sie zuerst ein Array zum Zählen vor
		 *Die Zahlenfolge, die Sie erstellen möchten, hat die folgende Form (die Anzahl ändert sich zwischen A und C).
		 * A  C  A  C  T  A  C  G
		 * 0, 1, 1, 2, 2, 2, 3, 3
		 *
		 *
		 *Dies ist unpraktisch.
		 *Es ist schwierig zu beurteilen, wann nur C an der Startposition und nur A an der Endposition gefangen wird.
		 * 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"Ich suche die Schnur.
			 *Was die Anzahl zwischen A und C ändert, ist"AC"Die Anzahl ändert sich erst, wenn Sie das Set erhalten.
			 *Wenn die Endposition nur A ist, wird der letzte Wechselstrom ausgeschlossen.
			 *Wenn die Endposition mit C verbunden ist, ist der letzte Wechselstrom enthalten.
			 *Wenn die Startposition von A abhängt, sieht es so aus, als ob der erste Wechselstrom nicht enthalten ist, sondern in der letzten Berechnung+Zu tun (um genau zu sein-Nicht durchgeführt)
			 *Wenn die Startposition nur C ist, scheint der erste Wechselstrom enthalten zu sein, jedoch in der letzten Berechnung-Getan werden.
			 */

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

		}

Am Ende einfach subtrahieren. Mit dieser Implementierung dauert es weniger als eine Sekunde, um den Testfall auf der Site zu bestehen.

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

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

			System.out.println(total);
		}

	}

Von hier aus eine Sammlung fehlgeschlagener Implementierungen des C-Problems

Implementierungsrichtlinie

• Die Unterzeichenkette wird pflichtbewusst aus der Zeichenkette S herausgeschnitten, und es wird beurteilt, wie viele "AC" enthalten sind.

Diese Methode wird nicht rechtzeitig zum Zeitlimit sein. ** 10 ^ 5 * 10 ^ 5 * Anzahl der Zeichenfolgenoperationen **

Das Folgende ist ein Implementierungsbeispiel, das hart gearbeitet hat, um "eine Teilzeichenfolge aus der Zeichenfolge S auszuschneiden und zu bestimmen, wie viele ACs enthalten sind".

• In diesem Fall wird "Schneiden Sie einen Teilstring aus der Zeichenfolge S aus und bestimmen Sie, wie viele" AC "enthalten sind" "bis zu 10 ^ 5 Mal ausgeführt.

** Schneiden Sie eine Teilzeichenfolge aus der Zeichenfolge S aus. ** Implementierung

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

	}

Muster 1: Wiederholungsfunktion

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

Muster 2: Sequentielle Verarbeitung mit indexOf

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

Muster 3: Schließen Sie "AC" von der Zeichenfolge mit Ersetzen aus, um die Länge mit der ursprünglichen Zeichenfolge zu erhalten

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

Muster 4: Konvertieren Sie die Zeichenfolge in ein Array mit "AC" als Trennzeichen und zählen Sie die Zahl

Es ist eine grobe Implementierung, aber ein wenig mehr Urteilsvermögen ist erforderlich.

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

Muster 5: Musterübereinstimmung

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

Muster 6: Leise zählen

				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

Nummerieren Sie die Buchstaben und führen Sie DP basierend auf den folgenden Zahlen aus

―― Immer welche Zeichen können dieses Mal hinzugefügt werden? DP basiert auf . ――Gegeben von oben, ** Welche Zeichen können dieses Mal nicht hinzugefügt werden? `** reduziert die Anzahl der zu berücksichtigenden Muster.

[NG-Muster]

	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;

		//String-Länge
		for (int strLength = 0; strLength < numN; strLength++) {
			//3 Zeichen vor dem Ende
			for (int c3 = 0; c3 < 4; c3++) {
				//2 Zeichen vor dem Ende
				for (int c2 = 0; c2 < 4; c2++) {
					//Ein Zeichen vor dem Ende
					for (int c1 = 0; c1 < 4; c1++) {

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

						//Zeichen, die ich dieses Mal hinzufügen möchte
						for (int c0 = 0; c0 < 4; c0++) {

							/*
							 *Wenn dies zuvor zwei Zeichen waren, können diesmal keine Zeichen hinzugefügt werden
							 * ->Hör auf zu zählen
							 *Da dies jedoch nicht möglich ist, wird es auf 0 gesetzt, indem es vorerst nicht berechnet wird.
							 */
							if (c2 == 0 && c1 == 1 && c0 == 2)
								continue;
							if (c2 == 0 && c1 == 2 && c0 == 1)
								continue;
							if (c2 == 1 && c1 == 0 && c0 == 2)
								continue;
							/*
							 *Das diesmal hinzuzufügende Zeichen ist C.(=2)Nur bei den ersten 3 Zeichen
							 *Kann unter den folgenden Bedingungen nicht hinzugefügt werden
							 */
							if (c3 == 0 && c1 == 1 && c0 == 2)
								continue;
							if (c3 == 0 && c2 == 1 && c0 == 2)
								continue;

							/*
							 *Sie können die Nummer der vorherigen Zeichenfolge in dieses Zeichen eingeben
							 * ->Diese Zeichenkette gilt
							 */
							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);
	}