目次
AtCoder Beginner Contest 122 A～D問題メモ
A - Double Helix
問題
- 塩基を表す文字 'A','C','G','T' のどれか1文字が与えられるので、対になる塩基を出力せよ
- アデニンはチミンと、シトシンはグアニンと対になる
解法
こういうのがパッと出るとどう書いたらいいか迷った挙げ句、何故か記述量の多い方法を選んじゃう。
print({'A': 'T', 'T': 'A', 'C': 'G', 'G': 'C'}[input()])
こちらの方がスマートか。
print('ATCG'['TAGC'.index(input())])
簡潔に書けるかと思ったら文字と文字コードの変換が発生してあまり簡潔にならなかった。str.maketrans()
print(chr(str.maketrans('ATCG', 'TAGC')[ord(input())]))
B - ATCoder
問題
- 文字列 $S$ が与えられる
- $S$ の部分文字列で、'A','C','G','T' のみからなるもので、最長のものの長さを求めよ
- $1 \le |S| \le 10$
- $S$ の部分文字列とは、$S$ から連続する部分を切り出した文字列である
- 飛び飛びで拾ってきた文字列は含まない（'ATCODER' から 'AC' などは含まない）
解法
左端と右端を全探索。
s = input()
ans = 0
for l in range(len(s)):
for r in range(l, len(s)):
t = s[l:r + 1]
if all(c in 'ACGT' for c in t):
ans = max(ans, len(t))
print(ans)
もしくは、先頭から1文字ずつ「今までで'A','C','G','T'が連続している個数カウント」を持ちながら見ていく。
ACGTのどれかだったらカウントを1増やし、どれでもなかったら0にリセットする。途中経過を含めたカウントの最大値が答え。
s = input()
ans = 0
tmp = 0
for c in s:
if c in 'ACGT':
tmp += 1
ans = max(ans, tmp)
else:
tmp = 0
print(ans)
C - GeT AC
問題
- 'A','C','G','T' のみからなる文字列 $S$ が与えられる
- 問いが $Q$ 個与えられるので、全てに答えよ
- $i$ 番目の問い:
- $l_i,r_i$ が与えられる
- $S$ の $l_i～r_i$ 文字目（両端含む）の部分文字列に、'AC' は何回現れるか？
- $1 \le |S| \le 10^5$
- $1 \le Q \le 10^5$
解法
クエリが一杯あるので、毎回、文字列を切り出してカウントしては間に合わない。
以下を事前計算する。
- $calc[i]$: 先頭から $i$ 文字目までの部分文字列に、'AC' が現れる個数
S AC_A_CA__ACACC__ ... calc 0111111111223333 ...
'C' の時に1増やすようにする。
こうすると、$l～r$ 文字目を見たとき、$calc[r]-calc[l]$ で、その間の個数が求められる。
i 01234567890123456 S AC_A_CA__ACACC__ ... calc 00111111111223333 ... l=2, r=14 S[l:r] C_A_CA__ACACC calc 1 3 → 3 - 1 = 2 個含まれる
元の文字列 $S$ では 'AC' の一部だった 'C' でも、そこを左端に切り出された場合は数えないことに注意。
from itertools import accumulate
n, q = list(map(int, input().split()))
s = input()
calc = [0] * n
prev = None
for i, c in enumerate(s):
if prev == 'A' and c == 'C':
calc[i] = 1
prev = c
calc = [0] + list(accumulate(calc))
ans = []
for _ in range(q):
l, r = list(map(int, input().split()))
ans.append(calc[r] - calc[l])
print('\n'.join(map(str, ans)))
D - We Like AGC
問題
- 整数 $N$ が与えられる
- 次の条件を満たす長さ $N$ の文字列の数を、$10^9+7$ で割った余りを求めよ
- $3 \le N \le 100$
- 条件
- 'A','C','G','T' のみからなる
- 'AGC' を部分文字列として含まない
- 隣接する2文字をどこか1箇所だけ入れ替えても、'AGC' を部分文字列として含むような文字列にすることはできない
解法
以下のDPで解く。
- 'A'=0, 'C'=1, 'G'=2, 'T'=3 と対応づける
- $dp[h][i][j][k]=$ 末尾から3文字目が $i$、2文字目が $j$、1文字目が $k$ であるような長さ $h$ の文字列の個数
初期状態を考える。最初から3文字目までは作成した状態（$h=3$）とする。
以下の組み合わせは禁止されているので0通り、他は1通りとなる。
i j k A G C ←そのままアウト A C G ←jとkの入れ替えでアウト G A C ←iとjの入れ替えでアウト
遷移を考える。
'AGC' を含まないなどの制約が無ければ、$l$ を新規に末尾に付け加える文字として、各 $i,j,k,l$ （それぞれ0～3）につき、以下のように更新できる。
- $dp[h+1][j][k][l]+=dp[h][i][j][k]$
さて、ここでアウトになるようなパターンを探して、それを更新から省く。
i j k l A G C ←そのままアウト A C G ←kとlの入れ替えでアウト G A C ←jとkの入れ替えでアウト A G C ←iとjの入れ替えでアウト A G C ←kとlの入れ替えでアウト
空白の部分は任意の文字が当てはまる。$(i,j,k,l)$ がこれらの条件を満たす場合の遷移は行わないようにする。
$h=N$ まで埋めたら、$dp[N]$ の数字を全て合計した値が答え。
実装の上では、$h$ は1つ前の情報しか必要で無いので、ループ時に直前の状態を引き継ぐようにすると省略できる。
MOD = 10 ** 9 + 7
n = int(input())
dp = [[[1] * 4 for _ in [0] * 4] for _ in [0] * 4]
dp[0][2][1] = 0
dp[0][1][2] = 0
dp[2][0][1] = 0
for _ in range(n - 3):
ndp = [[[0] * 4 for _ in [0] * 4] for _ in [0] * 4]
for i in range(4):
for j in range(4):
for k in range(4):
for l in range(4):
if (i, k, l) == (0, 2, 1) or (i, j, l) == (0, 2, 1):
pass
else:
ndp[j][k][l] += dp[i][j][k]
dp = ndp
dp[0][2][1] = 0
dp[0][1][2] = 0
dp[2][0][1] = 0
for j in range(4):
for k in range(4):
for l in range(4):
dp[j][k][l] %= MOD
print(sum(z for x in dp for y in x for z in y) % MOD)
