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

AtCoder - 122

C problem could not break through the front and TLE ... Shouldn't it be processed together at the end? I noticed that I got stuck in a bug and ended. 2019/04/17 D postscript

2019/05/22 Add the problem name

A - Double Helix

ʻA C`` G T` bases are output. I remember my undergraduate days.

It doesn't matter if you switch, if else, or set the initial value in Map. If you think it's beautiful, is it a map?

	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

Extracts a substring from the string S and outputs the length of the longest substring. However, only ʻACGT` may be included in the substring. Either double for or recursion. I prefer recursion, so I answer with recursion.

Check the character string S character by character from the beginning. Feeling like below

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

** Recursive judgment ** If the next character is ʻACGT, add +1 to the total and search for the next character. If the next character is not ʻACGT, the substring ends there and returns the total at that point. This is useless if the character string is long. It can't be processed by for.

• Exit conditions --If the current index exceeds the length of the string

Looking back after it's over, charAt is faster than substring, isn't it? .. ..

	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 To put it simply, I thought that the following requirements would be easy to solve.

--Given the string S --Get a substring starting with li from string S and ending with ri ――How many floors does the character AC appear in the substring?

Unless the length of the character string is 10 ^ 5 and the acquisition condition of the substring is 10 ^ 5 ...

To speed up

――Count the places where they appear once and make a note of them. --li-> ri is judged by subtracting the number of occurrences, not by the character string.

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 of count-only array

--When ʻAC appears, count up at the position of C --After creating the above array, you can get the number of occurrences of ʻAC by doing ri-li. --Points should be counted up at the C position

** Example ** Count up at the C position

Count up at the position of ʻA`

		/*
		 *First prepare an array for counting
		 *The sequence you want to make has the following shape (the count changes between A and C)
		 * A  C  A  C  T  A  C  G
		 * 0, 1, 1, 2, 2, 2, 3, 3
		 *
		 *
		 *This is inconvenient.
		 *It is troublesome to judge when only C is caught at the start position and when only A is caught at the end position.
		 * 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"I'm looking for the string.
			 *What is changing the count between A and C is"AC"The count will change only when you get the set.
			 *If the end position is only A, the last AC is excluded.
			 *If the end position is hooked to C, the last AC is included.
			 *If the starting position is hooked from A, it looks like the first AC is not included, but in the last calculation+To be done (to be exact-Not done)
			 *If the starting position is only C, the first AC seems to be included, but in the last calculation-Will be done.
			 */

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

		}

At the end, just subtract. With this implementation, it takes less than a second to pass the test cases on the 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);
		}

	}

From here, the failure implementation collection of C problem

Implementation policy

--The substring is dutifully cut out from the string S, and it is determined how many ʻAC`s are included.

This method will not be in time for the time limit. ** 10 ^ 5 * 10 ^ 5 * Number of string operations **

The following is an implementation example that worked hard to "cut out a substring from the string S and determine how many ʻAC`s are included".

--In this case, "cut out a substring from the string S and determine how many ʻAC`s are included" will be executed up to 10 ^ 5 times.

** Cut out a partial character string from the character string S ** Implementation

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

	}

Pattern 1: Recurrence function

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

Pattern 2: Sequential processing with indexOf

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

Pattern 3: Exclude ʻAC` from the string with replace to get the length with the original string

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

Pattern 4: Convert the character string to an array with ʻAC` as the delimiter and count the number

It's a rough implementation, but a little more judgment is required.

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

Pattern 5: pattern matching

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

Pattern 6: Count quietly

				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

Number the letters and execute DP based on the numbers below

――Always what characters can be added this time? DP based on . ――Given from the above, ** What characters cannot be added this time? ** reduces the number of patterns to consider.

[NG pattern]

	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 length
		for (int strLength = 0; strLength < numN; strLength++) {
			//3 characters before the end
			for (int c3 = 0; c3 < 4; c3++) {
				//2 characters before the end
				for (int c2 = 0; c2 < 4; c2++) {
					//One character before the end
					for (int c1 = 0; c1 < 4; c1++) {

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

						//Characters I want to add this time
						for (int c0 = 0; c0 < 4; c0++) {

							/*
							 *If these are two characters before, no characters can be added this time
							 * ->Stop counting
							 *However, since it cannot be done, it will be set to 0 by not calculating it for the time being.
							 */
							if (c2 == 0 && c1 == 1 && c0 == 2)
								continue;
							if (c2 == 0 && c1 == 2 && c0 == 1)
								continue;
							if (c2 == 1 && c1 == 0 && c0 == 2)
								continue;
							/*
							 *The character to be added this time is C(=2)Only in the case of, the first 3 characters
							 *Cannot be added under the following conditions
							 */
							if (c3 == 0 && c1 == 1 && c0 == 2)
								continue;
							if (c3 == 0 && c2 == 1 && c0 == 2)
								continue;

							/*
							 *You can enter the number of the previous character string in this character
							 * ->This string holds
							 */
							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);
	}