AtCoder Beginner Contest 122 A~D問題メモ

AtCoder Beginner Contest 122

謎の核酸塩基回、そして部分文字列回。

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)

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2019/0324_abc122.txt · 最終更新: 2019/03/25 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0