u++の備忘録

AtCoder Beginner Contest 122をPythonで解く

python 競プロ

「AtCoder Beginner Contest 122」に出て、全完でした。A問題で誤読して2WAして号泣スタートでしたが、最後が精進していたDP問題だったので何とか取り戻せた形です。

atcoder.jp

f:id:upura:20190324222417p:plain

A - Double Helix（100点）

  • 4通りの場合分け
  • 対応を空目して2WAしたので、明日メガネを購入しに行きます
b = input()

if b == 'A':
    ans = 'T'
elif b == 'C':
    ans = 'G'
elif b == 'G':
    ans = 'C'
elif b == 'T':
    ans = 'A'

print(ans)

B - ATCoder（200点）

  • 部分文字列を全列挙し、ACGT文字列か否かを判定
  • ACGT文字列か否かの判定は愚直に（どうすれば改善できた？）
  • もっと綺麗に書ける気もするが、Aでしくじった余波で汚いコードに
S = input()
N = len(S)

alp = 'BDEFHIJKLMNOPQRSUVWXYZ'

cnt = []

for i in range(0, N):
    for j in range(i, N+1):
        tmp = S[i:j]
        flg = 1
        for a in alp:
            if a in tmp:
                flg = 0
        if flg:
            cnt.append(len(tmp))

print(max(cnt))

C - GeT AC（300点）

  • TLE①：部分文字列を全列挙し、str.count('AC')
  • TLE②：先にSのどの2文字が'AC'に一致するかを調べてフラグを立てておき、l, rの値に応じてフラグを合計する
  • l, rの値に応じてフラグを合計する部分を累積和で高速化
from itertools import accumulate


N, Q = list(map(int, input().split()))
S = input()
A = [list(map(int, input().split())) for i in range(Q)]

flg = []
for i in range(N-1):
    tmp_S = S[i:i+2]
    if tmp_S == 'AC':
        flg.append(1)
    else:
        flg.append(0)

flg2 = [0] + flg
flg2 = list(accumulate(flg2))

for a in A:
    print(flg2[a[1]-1] - flg2[a[0]-1])

D - We Like AGC（400点）

  • Cの時点でTLEしたので、最初から全探索は頭になかった
  • 「ABCのD問題はDPのD」らしい
  • 愚直に全パターンを走査していき、違反したら0にする
N = int(input())
M = 10**9 + 7

dp = [
    [[[1 if i==0 else 0 for i in range(N-2)] for j in range(4)] for k in range(4)] for l in range(4)
]

dp[0][1][2][0] = 0
dp[0][2][1][0] = 0
dp[1][0][2][0] = 0

for m in range(N-3):
    for i in range(4):
        for j in range(4):
            for k in range(4):
                for l in range(4):
                    dp[j][k][l][m+1] += dp[i][j][k][m]
                    dp[j][k][l][m+1] %= M
                    dp[0][1][2][m+1] = 0
                    dp[0][2][1][m+1] = 0
                    dp[1][0][2][m+1] = 0

                    if (i==0):
                        for o in range(4):
                            dp[o][1][2][m+1] = 0
                            dp[1][o][2][m+1] = 0

total = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            total += dp[i][j][k][N-3]
            total %= M
print(total)

復習

B問題


S = input()
N = len(S)

alp = 'ATCG'
cnt = []

for i in range(0, N):
    for j in range(i, N+1):
        tmp = S[i:j]
        if set(alp) >= set(tmp):
            cnt.append(len(tmp))

print(max(cnt))