AtCoder Beginner Contest 122の解説 - private-yusuke’s diary

A - Double Helix

入力: $b$
出力: 塩基 $b$ と対になる塩基
制約:

$b$ は文字 'A', 'C', 'G', 'T' のいずれかである。

サンプルに全ての答えが書いてありますね…

switch(b) {
	case "A": writeln("T"); break;
	case "T": writeln("A"); break;
	case "G": writeln("C"); break;
	case "C": writeln("G"); break;
	default: break;
}

感想: かなりA問題らしい問題で好き

B - ATCoder

入力: $S$
出力: $S$ の部分文字列のうち最長のACGT文字列の長さ
制約:

$1 \le |S| \le 10$

部分文字列の意味を考えて実装します。

ulong res;
ulong tmp;
foreach(i; S) {
	if(i == 'A' || i == 'T' || i == 'C' || i == 'G') {
		tmp++;
	} else {
		res = max(res, tmp);
		tmp = 0;
	}
}
res = max(res, tmp);
res.writeln;

感想: ループ後のmaxをとる処理を忘れて1WA…とてもかなしい凡ミスをした。

C - GeT AC

入力:
$N\ Q$
$S$
$l_1\ r_1$
$\vdots$
$l_Q\ r_Q$
出力: $S$ の先頭から $l_i$ 文字目から $r_i$ 文字目までの部分文字列の中に含まれる 'AC' の数
制約:

$2 \le N \le 10^5$
$1 \le Q \le 10^5$
$|S| = N$
$1 \le l_i < r_i \le N$
$S$ はACGT文字列

$Q$ 個のクエリが与えられるので、毎回 'AC' を数えていると $O(NQ)$ となりTLEします。

したがって、「先に 'AC' が出てくる回数を数えておいて、各クエリで記憶しておいた回数を使おう！」という方針を考えます。俗にいう累積和です。

arr[i] を「左から $i$ 番目までの $S$ に出現した 'AC' の数」とします。

foreach(i; 0..S.length-1) {
	if(S[i] == 'A' && S[i+1] == 'C') {
		arr[i+1] = arr[i] + 1;
	} else arr[i+1] = arr[i];
}

そして、 $S$ の $l$ から $r$ までの 'AC' の数は「arr[r] - arr[l]」で求めることができました。

auto arr = new int[](N);
foreach(i; 0..S.length-1) {
	if(S[i] == 'A' && S[i+1] == 'C') {
		arr[i+1] = arr[i] + 1;
	} else arr[i+1] = arr[i];
}

foreach(i; 0..Q) {
	auto ip2 = readAs!(int[]), l = ip2[0]-1, r = ip2[1]-1;
	writeln(arr[r] - arr[l]);
}

感想: まさに「累積和をやれ」と言わんばかりの問題でした。

D - We Like AGC

入力: $N$
出力: 条件を満たす文字列の数を $10^9+7$ で割った余り
制約:

$3 \le N \le 100$

条件を満たさない文字列は、"."を任意の文字として

AGC.
GAC.
ACG.

と

A.GC
AG.C
.AGC
.GAC
.ACG

の形で表すことができます。

愚直に全探索すると $O(4^N)$ になって間に合わないので、DPで $O(N)$ にします。

dp[n][t1][t2][t3] を「0-indexedでn-4, n-3, n-2番目の文字がt1, t2, t3と並ぶような、長さnの条件を満たす文字列の数」とします。

[t1, t2, t3]が条件を満たさない文字列になるときはdp[n][t1][t2][t3]==0ですから、その場合はすぐにcontinueします。(上で挙げた条件を満たさない文字列の前半ですね！)

そのあと、上で挙げた条件を満たさない文字列の後半にあたるところも同様にします。

条件を満たす文字列のときは、[t1, t2, t3, a]の並びが大丈夫であることがわかっているので、 dp[n+1][t2][t3][a] += dp[n][t1][t2][t3] として遷移を書きます。( $10^9 + 7$ で割ることを忘れずに)

最終的な答えは、dp[N]の内側にある値の総和になります。

auto dp = new long[][][][](N+1, 4, 4, 4);
dp[0][3][3][3] = 1;

foreach(n; 0..N) foreach(t1; 0..4) foreach(t2; 0..4) foreach(t3; 0..4) {
	if(dp[n][t1][t2][t3] == 0) continue;
	foreach(a; 0..4) {
		char c1 = t1.t, c2 = t2.t, c3 = t3.t, c4 = a.t;
		if([c1, c3, c4] == "AGC") continue;
		if([c1, c2, c4] == "AGC") continue;
		if([c2, c3, c4] == "AGC") continue;
		if([c2, c3, c4] == "GAC") continue;
		if([c2, c3, c4] == "ACG") continue;
		dp[n+1][t2][t3][a] += dp[n][t1][t2][t3];
		dp[n+1][t2][t3][a] %= MOD;
	}
}
long res;
foreach(t1; 0..4) foreach(t2; 0..4) foreach(t3; 0..4) {
	res += dp[N][t1][t2][t3];
	res %= MOD;
}
res.writeln;

感想: これDPだろということだけわかって、その後は椅子を温めた。

A: Submission #4685262 - AtCoder Beginner Contest 122
B: Submission #4688713 - AtCoder Beginner Contest 122
C: Submission #4687776 - AtCoder Beginner Contest 122
D: Submission #4710256 - AtCoder Beginner Contest 122