LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@shihou22

ABC - 122 - A&B&C&D

Last updated at Posted at 2019-03-25

AtCoder - 122

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

2019/05/22
　問題名を追記

A - Double Helix

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

switchでもif elseでもMapに初期値設定してでもどれでもいい。
奇麗にと考えたら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

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

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

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

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

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

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

	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　の判定は文字列ではなく出現回数の引き算で行う
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 

		/*
		 * 最初にカウント用の配列を用意
		 * 作りたい数列は以下のような形（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秒掛かりません。


		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^510^5文字列操作回数

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

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

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

	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：再起関数

	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で順次処理

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

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

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

パターン4：文字列をACを区切り文字として配列に変換し個数をカウント

実装雑だけどもう少し判定必要です。

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

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

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

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

				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
3個前と2個前を入れ替えられるため		 A ? C G
NG
2個前と1個前を入れ替えられるため		 A C ? G
上記以外は全てOK 
	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);
	}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?