ABC - 122 - A&B&C&D

[AtCoder - 122](https://atcoder.jp/contests/abc122)

C問題が正面突破できずずっとTLE...
最後の方でまとめて処理すればいいのでは？と気づいたけどバグにはまり終了。
**2019/04/17**
　D追記

**2019/05/22**
　問題名を追記

#A - Double Helix

　`A` `C` `G` `T`の塩基に対応した塩基を出力する。
　学部生時代を思い出す。

switchでもif elseでもMapに初期値設定してでもどれでもいい。
奇麗にと考えたらMapかな？

```java
	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

文字列Sの中から部分文字列を抽出し、部分文字列の内最長な文字列の長さを出力
ただし、部分文字列には`ACGT`のみ含んでよい。
2重forか再帰のどちらでも。
再帰の方がスキなので再帰で回答。

文字列Sを頭から1文字ずつ確認していく。
下みたいな感じ

 - ATCODER
 - TCODER
 - CODER
 - ODER
 - DER
 - ER
 - R

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

```

**再帰で判定する処理**
次の文字が`ACGT`なら合計に+1して次の文字を探索。
次の文字が`ACGT`ではない場合は部分文字列はそこで終了するのでその時点の合計を返す。
これ、文字列が長いと駄目だな。forでの処理にもなれないと。

 - 終了条件
    - 文字列の長さを現在のindexが超えたら

終わった後見直すと、、、substringよりもcharAtの方が速いよね。。。


```java
	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
単純に考えると、以下の要件であり簡単に解けると思った。

 - 文字列Sが与えられる
 - 文字列Sからliを開始、riを終端とする部分文字列を取得
 - 部分文字列の中にACという文字は何階出現するのか

文字列の長さが10^5でなく、部分文字列の取得条件が10^5でなければ・・・


---
####
速度を出すには、

 - 一回出現箇所を別途数えておいてメモをしておく
 - li -> ri　の判定は文字列ではなく出現回数の引き算で行う



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

カウント専用配列のイメージ

| A | C | A | C | T | A | C | G |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |

 - `AC`が出現したら`C`の位置でカウントアップ
    - 上記の配列を作ったら、`ri-li`をすれば`AC`の出現回数が取れる。
    - ポイントは`C`の位置でカウントアップすること

**例**
`C`の位置でカウントアップする

| A | C | A | C | T | A | C | G | 説明 |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 0 | 1 | 1 | 2 | 2 | 2 | 3 | 3 |   |
| li|   |   |   |   |ri |   |   |  liが`A`の位置。riも`A`の位置。出現回数はri-li=2 |
| li|   |   |   |   |   |ri |   |  liが`A`の位置。riは`C`の位置。出現回数はri-li=3 |
| 　|li |   |   |   |ri |   |   |  liが`C`の位置。riは`A`の位置。出現回数はri-li=1 |
| 　|li |   |   |   |   |ri |   |  liが`C`の位置。riは`C`の位置。出現回数はri-li=2 |
| 　|li |ri |   |   |   |   |   |  liが`C`の位置。riは`A`の位置。出現回数はri-li=0 |


`A`の位置でカウントアップする

| A | C | A | C | T | A | C | G | 説明 |`ACに掛かったときの判定` | 
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |   |   |
| li|   |   |   |   |ri |   |   |  liが`A`の位置。riも`A`の位置。計算はri-li=2 | 開始が`AC`の`A`を含んでいるので+1。終端が`AC`の`A`を含んでいる(Cを含んでいない)ので-1して合計：2 |
| li|   |   |   |   |   |ri |   |  liが`A`の位置。riは`C`の位置。計算はri-li=2 | 開始が`AC`の`A`を含んでいるので+1。終端が`AC`の`C`を含んでいる何もしないので合計：3 |
|   |li |   |   |   |ri |   |   |  liが`C`の位置。riは`A`の位置。計算はri-li=2 | 開始が`AC`の`C`から始まっているので何もしない。終端が`AC`の`A`を含んでいる(Cを含んでいない)ので-1して合計:1 |
|   |li |   |   |   |   |ri |   |  liが`C`の位置。riは`C`の位置。計算はri-li=2 | 開始が`AC`の`C`から始まっているので何もしない。終端が`AC`の`C`を含んでいる何もしないので合計:2 |
|   |li |ri |   |   |   |   |   |  liが`C`の位置。riは`A`の位置。計算はri-li=1 | 開始が`AC`の`C`から始まっているので何もしない。終端が`AC`の`A`を含んでいる(Cを含んでいない)ので-1して合計:0 |


```java

		/*
		 * 最初にカウント用の配列を用意
		 * 作りたい数列は以下のような形（AとCの間でカウントが変わる）
		 * A  C  A  C  T  A  C  G
		 * 0, 1, 1, 2, 2, 2, 3, 3
		 *
		 *
		 * こちらだと都合が悪い。
		 * 開始位置でCのみひっかけた場合と、終端位置でAのみひっかけた場合の判定が面倒。
		 * 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"という文字列を探している。
			 * AとCの間でカウントを変えているのは、"AC"をセットで取得したときのみカウントが変わるように。
			 * 終端位置がAのみひっかけた場合、最後のACは除外される。
			 * 終端位置がCまでひっかけた場合、最後のACは含まれる。
			 * 開始位置がAからひっかけた場合、最初のACは含まれていないように見えるが、最後の計算で+される（正確には-されない）
			 * 開始位置がCのみひっかけた場合、最初のACは含まれるように見えるが、最後の計算で-される。
			 */

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

		}
```

最後は引き算するだけ。
この実装だとサイトのテストケースを通すのに1秒掛かりません。

```java

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

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

			System.out.println(total);
		}

	}
```

---
###ここからはC問題の失敗実装集

実装方針

  - 律儀に文字列Sから部分文字列を切り出し、`AC`が何個含まれているのかを判定している。

この方法だと制限時間内に間に合いません。
**10^5*10^5*文字列操作回数**

以下、「文字列Sから部分文字列を切り出し、`AC`が何個含まれているのかを判定」を頑張った実装例。

 - この場合、「文字列Sから部分文字列を切り出し、`AC`が何個含まれているのかを判定」するのを最大で10^5回実行することになります。


**文字列Sから部分文字列を切り出す**　実装

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

	}

```

#####パターン1：再起関数

```java

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

#####パターン2：indexOfで順次処理
```java

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

####パターン3：文字列から`AC`をreplaceで除外して元の文字列との長さを取得

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

####パターン4：文字列を`AC`を区切り文字として配列に変換し個数をカウント
実装雑だけどもう少し判定必要です。

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

####パターン5：パターンマッチ

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


####パターン6：おとなしく数える

```java
				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

文字に番号を振っておき、DPは下記番号を元に実行

||A|G|C|T|
|:-:|:-:|:-:|:-:|:-:|
|添え字|0|1|2|3|

 - 常に、`今回追加することのできる文字はなにか？`をもとにDPしていく。
 - 上記から考えると、**`今回付け加えられない文字はなにか？`**とすると、検討するパターンが減る。

[NGパターン]

||3個前|2個前|1個前|今回付け加える文字|
|:-:|:-:|:-:|:-:|:-:|
|NG|?|A|G|C|
|NG|?|G|A|C|
|NG|?|A|C|G|
|NG<br>3個前と2個前を入れ替えられるため|A|?|C|G|
|NG<br>2個前と1個前を入れ替えられるため|A|C|?|G|
|上記以外は全てOK|||||


```java
	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;

		//文字列長
		for (int strLength = 0; strLength < numN; strLength++) {
			//最後から3文字前
			for (int c3 = 0; c3 < 4; c3++) {
				//最後から2文字前
				for (int c2 = 0; c2 < 4; c2++) {
					//最後から1文字前
					for (int c1 = 0; c1 < 4; c1++) {

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

						//今回付け加えたい文字
						for (int c0 = 0; c0 < 4; c0++) {

							/*
							 * 2文字前がこれらだったら今回は何も文字を付け加えられない
							 * -> 数え上げ中止
							 * が、出来ないのでとりあえず計算しないことで0にしてしまう。
							 */
							if (c2 == 0 && c1 == 1 && c0 == 2)
								continue;
							if (c2 == 0 && c1 == 2 && c0 == 1)
								continue;
							if (c2 == 1 && c1 == 0 && c0 == 2)
								continue;
							/*
							 * 今回付け加える文字がC(=2)の場合限定で、前3文字
							 * 以下の条件だと付け加えられない
							 */
							if (c3 == 0 && c1 == 1 && c0 == 2)
								continue;
							if (c3 == 0 && c2 == 1 && c0 == 2)
								continue;

							/*
							 * 今回の文字には一つ前の文字列の数を入れることが出来る
							 * ->この文字列は成立している
							 */
							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);
	}

```