[PYTHON] AtCoder Beginner Contest 122 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Das letzte Problem war, dass ich wusste, dass Experimentieren wichtig ist, aber ich konnte die Lösung nicht einfacher machen.

Problem A

Entsprechend mit dem ternären Operator ausgeben.

answerA.py

b=input()
print("A" if b=="T" else "T" if b=="A" else "G" if b=="C" else "C")

B-Problem

Wenn eines der AGCT kommt, fügen Sie es hinzu, und wenn ein anderes Zeichen kommt, setzen Sie es wieder auf Null.

answerB.py

x=["A","G","C","T"]
ans=0
now=0
for i in input():
    if i in x:
        now+=1
    else:
        now=0
    ans=max(now,ans)
print(ans)

C-Problem

In diesem Fall verwenden wir die kumulative Summe, da wir die Abfrage für das Intervall am Ende verarbeiten müssen. Beachten Sie jedoch, dass Sie, wenn Sie AC finden, dem Index ** mit ** C +1 hinzufügen müssen.

answerC.py

n,m=map(int,input().split())
n,q=map(int,input().split())
s=input()
x=[0]*n

for i in range(n-1):
    if s[i:i+2]=="AC":
        x[i+1]=x[i]+1
    else:
        x[i+1]=x[i]
for i in range(q):
    l,r=map(int,input().split())
    print(x[r-1]-x[l-1])

D Problem

Hier, wenn die AGC-Zeichenfolge nicht bis zum i-ten Zeichen angezeigt wird, selbst wenn die beiden benachbarten Zeichen ausgetauscht werden, wenn die AGC-Zeichenfolge für die Zeichenfolge einschließlich des i + 1-ten Zeichens nicht angezeigt wird, bis zu i + 1 Es kann gesagt werden, dass die AGC-Zeichenfolge nicht angezeigt wird. Daher scheint es, dass die Antwort durch ** Denken in der Reihenfolge von vorne ** gesucht wird. Unter Berücksichtigung einer Zeichenkette, in der eine Unterzeichenfolge mit der Bezeichnung AGC erscheint, können hier fünf Muster ** AGC, ACG, GAC, A? GC, AG? C, ** berücksichtigt werden (die beiden letzteren sind blinde Flecken). Ta ...). Daher haben wir angefangen, von vorne zu denken, und als ein Teilstring erschien, der zu den 5 Mustern passt, haben wir ihn nicht in die Zählung einbezogen. Hier haben ** 5 Mustersubstrings alle eine Länge von 4 oder weniger. Wenn Sie also das i-te Zeichen berücksichtigen, müssen Sie nur die i-1, i-2, i-3 Zeichen ** kennen. Notieren Sie daher die Unterzeichenfolge der Zeichen i-3 bis i-1 im Wörterbuch und beim Hinzufügen jedes Zeichens von A, G, C, D zum Zeichen ** i die Unterzeichen, die für die 5 Muster gelten. Sie finden die richtige Antwort, indem Sie den Wert im Wörterbuch ** nur aktualisieren, wenn die Spalte nicht angezeigt wird. Zu diesem Zeitpunkt ist es außerdem erforderlich, einmal in einem anderen Wörterbuch anstelle des ursprünglichen Wörterbuchs aufzuzeichnen. (Ich habe versucht, 64 Wege zu schreiben, ohne ein Wörterbuch für dieses Problem zu verwenden ... ** Ich sollte abstrakter denken. **)

answerD.py

n=int(input())
alph=["A","C","G","T"]
a=[alph[i]+alph[j]+alph[k] for i in range(4) for j in range(4) for k in range(4)]
d1={l:0 for l in a}
for i in d1:
    if i!="AGC" and i!="ACG" and i!="GAC":
        d1[i]=1
d2={l:0 for l in a}
for i in range(n-3):
    for j in d1:
        next=[j+alph[k] for k in range(4)]
        for k in range(4):
            l=next[k]
            if l[1:]=="GAC" or l[1:]=="ACG" or l[1:]=="AGC":
                pass
            elif l[0]=="A" and l[3]=="C" and (l[1]=="G" or l[2]=="G"):
                pass
            else:
                d2[l[1:]]+=d1[j]
    for j in d1:
        d1[j]=d2[j]
        d2[j]=0
print(sum(d1.values())%1000000007)