[PYTHON] AtCoder Beginner Contest 162 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Es ist nicht schlecht in Bezug auf die Leistung, aber es tut mir sehr leid, weil ich sowohl E als auch F nicht lösen konnte (obwohl es eine Stunde gedauert hat). Vorerst möchte ich noch einmal überprüfen, was E und F fehlten.

Problem A

Ob 7 enthalten ist oder nicht, kann als Zeichenfolge behandelt werden. Warum konvertieren Sie in eine Liste? Ich bin zu verrückt

A.py

n=list(input())
print("Yes" if "7" in n else "No")

B-Problem

Sie sollten über die Gesamtheit der Dinge nachdenken, die nicht brechen, selbst wenn 3 oder 5. Es hat ein paar Minuten gedauert, weil ich `` `i% 3 == 0 und i% 5 == 0``` gesetzt habe. ** Wenn es nicht funktioniert, funktioniert es nicht von Anfang an **. Ich möchte es ab dem nächsten Wettbewerb beheben.

B.py

ans=0
n=int(input())
for i in range(1,n+1):
    if i%3!=0 and i%5!=0:
        ans+=i
print(ans)

C-Problem

Ich habe WA ausgestellt ... Sie können verstehen, dass es nicht vergehen wird, wenn Sie nicht ruhig denken und ein wenig überlegen. ** Sie können das Ergebnis von gcd (i, j) zum Zeitpunkt der äußeren Doppelschleife sehen **. Wenn Sie also gcd (i, j) in der innersten Schleife berechnen, wird es mehr berechnet und pünktlich zum Zeitlimit nicht. (Ich war während des Wettbewerbs zu ungeduldig und habe es in C ++ bestanden, aber es wird auch normal in Python bestanden.)

C_TLE.py

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            ans+=gcd(gcd(i,j),l)
print(ans)

C.py

from math import gcd
k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans_=gcd(i,j)
        for l in range(1,k+1):
            ans+=gcd(ans_,l)
print(ans)

D Problem

Ich habe das D-Problem auch mit viel Ungeduld gelöst. Schließlich kann es sein, dass ** wenn Sie sich zu viel Mühe geben, es im Gegenteil fehlschlägt **. Das erste, was aus diesem Problem leicht zu verstehen ist, ist, dass die drei zu wählenden Buchstaben ** R, G bzw. B ** sind. Da die Beziehung zwischen den Indizes der einzelnen Zeichen zu einem Problem wird, habe ich beschlossen, die Indizes der ** Zeichen R, G und B separat in einem Array ** zu speichern. Wenn Sie darunter am kürzesten denken, sollten Sie sich in der Reihenfolge r → g → b entscheiden und überlegen, ob der Index dem Thema entspricht. ** Wenn jedoch nichts unternommen wird, führt N <= 4000 zu O ($ N ^ 3 ) und endet nicht innerhalb des Zeitlimits **. Da die Operation zur Bestimmung des Index von R und G O ( N ^ 2 $) ist, dachte ich, dass ** die verbleibenden Indexkandidaten von B durch O (1) ** bestimmt werden sollten. Wenn dann der kleinere Index von R und G x und der größere Index y ist, sind die verbleibenden ** Indizes, die keine Kandidaten für den Index von B ** sind, "x- (yx)", "". Sie können sehen, dass es drei Möglichkeiten gibt: x + (yx) , (x + y) / 2 (die Gleichmäßigkeit von x und y ist gleich) `` Es wurde gefunden, indem die Beziehung zwischen den beiden veranschaulicht wurde.) Sobald Sie dies wissen, können Sie die Antwort finden, indem Sie den Index von B mit set verwalten und nur den Index subtrahieren, der kein Kandidat ist.

answerD.py

n=int(input())
s=input()
r,g,b=[],[],[]
for i in range(n):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    else:
        b.append(i)
b=set(b)
lb=len(b)
ans=0
for i in r:
    for j in g:
        x,y=min(i,j),max(i,j)
        ans_=lb
        if x-(y-x) in b:
            ans_-=1
        if y+(y-x) in b:
            ans_-=1
        if (x%2==y%2) and (y-x)//2+x in b:
            ans_-=1
        ans+=ans_
print(ans)

E Problem

Nach dem letzten Mal waren die E- und F-Probleme sehr lehrreich, daher lohnt es sich, sie zu studieren. Wenn dieses Pegelband (hellblau, blau) stabil gelöst werden kann, scheinen die Ergebnisse stabil zu sein, daher möchte ich die Probleme in diesem Pegelband so weit wie möglich lösen. In diesem Problem betrachten wir gcd der Kombination von $ K ^ N $, so dass wir sehen können, dass ** alles zählen nicht rechtzeitig ** ist. Betrachten wir daher, wie viele ** gcd-Werte ** es gibt. Da der Wert von gcd gemäß der Definition von gcd 1 ~ k ist, suchen Sie nach der Sequenz $ A_1, A_2,…, A_n , wobei gcd x ist ( 1 \ leqq x \ leqq k $). Hier ist die notwendige und ausreichende Bedingung ** für ** gcd ein Vielfaches von x ** $ A_1, A_2,…, A_n $ ist ein Vielfaches von x **, also $ (k // x) ^ Es gibt n $ Straßen. Die notwendige und ausreichende Bedingung ** für ** gcd, um genau x zu sein, ist jedoch, dass es ein Vielfaches von ** x ist und nicht 2x, 3x,… **. Um die Anzahl der Fälle zu ermitteln, in denen gcd x ist, müssen wir daher die Fälle subtrahieren, in denen gcd 2x, 3x, ... von $ (k // x) ^ n $ ist. Wenn Sie jedoch x von 1 nach k verschieben, müssen Sie überprüfen, ob 2x, 3x, ... kleiner oder gleich k ist, und in diesem Fall die Zahl subtrahieren. In diesem Fall ** 2x, 3x, Die Anzahl der Fälle von ... ist nicht immer festgelegt **. Eine effektive Idee ist hier, an ** x in umgekehrter Reihenfolge von k → 1 anstelle von 1 → k ** zu denken. In diesem Fall kann es berechnet werden, indem zuerst berechnet wird, wie viele Zahlenfolgen so sind, dass gcd 2y, 3y, ... ist, und von den Kandidaten der Zahlenfolge subtrahiert wird, so dass gcd y ist. Da wir auch y betrachten wollen, für das $ x = l \ mal y (l \ geqq 1) $ gilt, ist es leicht zu erkennen, dass ** y ein Bruchteil von x ** ist. Aus dem Obigen ist es in Bezug auf die Anzahl der Kandidaten in der Zahlenfolge, wenn gcd ungefähr $ x_1, x_2, ..., x_m $ von y ohne y selbst ist, ausreichend, die Anzahl der Kandidaten in der Zahlenfolge von y zu subtrahieren. Bei der Implementierung sieht es so aus: Die Antwort ist auch, dass Sie den Rest von $ 10 ^ 9 + 7 $ finden müssen und beim Initialisieren des Memo-Arrays $ 10 ^ 9 + 7 $ als drittes Argument von pow für $ 10 ^ 9 + 7 $ angeben müssen. Es ist auch wichtig zu beachten, dass die Berechnung beschleunigt werden kann, indem zu viel verlangt wird.

answerE.py

def make_divisors(n):
    divisors=[]
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n//i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

n,k=map(int,input().split())
mod=10**9+7
memo=[pow(k//i,n,mod) for i in range(1,k+1)] #gcd ist 1~Notieren Sie sich, wann es k wird
for i in range(k-1,-1,-1):
    x=make_divisors(i+1)
    for j in x:
        if j!=i+1:
            memo[j-1]-=memo[i]
ans=0
for i in range(k):
    ans+=(memo[i]*(i+1))
    ans%=mod
print(ans)

F Problem

Ich war so an die Form des Rucksack-DP gewöhnt, dass ich den Zustandsübergangs-DP nicht bemerkte (es ist nicht der offizielle Name, weil ich ihn einfach so nenne). ** Ich habe versucht, es wie ein Rätsel in den dunklen Wolken zu lösen ** und ich habe es nicht verstanden. Probleme wie diese können mit ein wenig Abstraktion überraschend sichtbar sein. Erstens, da die Obergrenze der Zahl, die ausgewählt werden kann, n // 2 ist, gibt es nicht eine Obergrenze für die Zahl, die bis zum ** i-ten (i = 1,2, ..., n) ausgewählt werden kann? Es ist wichtig, die Frage zu haben **. Basierend auf dieser Frage kann daher ** die Anzahl benachbarter Nummern nicht ausgewählt werden **, so dass ersichtlich ist, dass die Nummer, die vom 1. bis zum i-ten ausgewählt werden kann, (i + 1) // 2 oder weniger ist. Darüber hinaus ist die Zahl, die von i + 1 bis n gewählt werden kann, (n-i + 1) // 2 oder weniger, und nur n // 2 wird von 1 bis n ausgewählt, so dass die Zahl, die von 1 bis i gewählt werden kann, ist Erfordert auch die Bedingung, dass n // 2- (n-i + 1) // 2 = (i-1) // 2 oder mehr. Daher wird die Bedingung erhalten, dass ** die Anzahl der bis zum i-ten zu wählenden Zahlen (i-1) // 2 oder mehr (i + 1) // 2 oder weniger ** sein muss. Jetzt, da wir wissen, dass die Anzahl der Nummern, die bis zum i-ten ausgewählt werden können, begrenzt ist, ** die Beziehung zwischen der Anzahl der Nummern, die bis zum i-ten ausgewählt werden können, und der Anzahl, die bis zum i-ten ausgewählt werden kann ** und ** Es erscheint natürlich, auf die Idee zu kommen, die Beziehung zwischen der Anzahl der bis zum i-ten ausgewählten Zahlen und der Anzahl der bis zum i + 1 ** ausgewählten Zahlen zu berücksichtigen.

Abbildung 1

Figur 2

Figur 3

Die obigen Abbildungen 1 bis 3 basieren auf dieser Idee. Zunächst wird in Fig. 1 die Anzahl der Zahlen, die im i-ten ausgewählt werden können, in der Reihenfolge von der ersten geschrieben (Fig. 2 ist in der Reihenfolge von der zweiten). Ich habe versucht, eine DP-Sequenz zu erstellen, die die beiden Zustände so wie sie ist beibehält, aber da sie nicht aus dem Beispielfall passte, habe ich genau hingeschaut und festgestellt, dass nur diese beiden Zustände ** außer wenn zwei Zahlen aufeinander folgen * * Ich konnte nicht. Das heißt, in Fig. 1 bewegt sich der rote Pfeil von 0 nach 1 nach 1, jedoch nicht von 0 nach 1 nach 2. Umgekehrt können Sie für den blauen Pfeil sowohl in 1 → 1 → 1 als auch in 1 → 1 → 2 fortfahren. Gleiches gilt für Abb. 2. Für den roten Pfeil können sowohl 1 → 1 → 1 als auch 1 → 1 → 2 vorgerückt werden, für den gelben Pfeil jedoch nur 0 → 1 → 1, aber 0 → 1 → 2 Ich kann nicht weitermachen. Daher erhöhen Sie in 1 für die zweite 0,1 ** den Zustand um eins ** auf 0,1,1 und die erste 1 ist die zweite, wenn die zweite Zahl nicht ausgewählt ist. 1 sollte der Fall sein, wenn Sie die zweite Nummer wählen. In Fig. 2 ist die dritte 1,2 1,1,2, die erste 1 ist, wenn die dritte Nummer nicht ausgewählt ist, und die zweite 1 ist, wenn die dritte Nummer ausgewählt ist. Du kannst es schaffen. Abbildung 3 fasst das Obige zusammen. Wenn Sie sich Abbildung 3 genauer ansehen, sehen Sie, dass ** der Pfeil auf verschiedene Punkte zeigt, je nachdem, ob der Index gerade oder ungerade ist **. Wenn Sie jedoch zu diesem Zeitpunkt die i-te Nummer nicht auswählen, wird sie als 1 geschrieben, wenn Sie sie mit $ \ pm $ 0 auswählen, und Sie müssen überprüfen, ob → gemäß dieser Notation geschlossen ist. Durch gehorsames Implementieren der obigen Schritte wird es wie folgt. Bitte beachten Sie, dass die Ausgabe unterschiedlich ist, wenn n gerade und ungerade ist.

Um noch einmal zu wiederholen, was Sie bisher denken müssen,

(1) Achten Sie darauf, welche Art von Einschränkung (Obergrenze) es gibt, wie viele Zahlen bis zum i-ten

(2) Leiten Sie ab, dass die Anzahl der Zahlen, die bis zum i-ten ausgewählt werden können, zwei beträgt.

(3) Experimentieren Sie, indem Sie auf die Beziehung zwischen vor und nach dem i-ten (i-1. Und i + 1.) Achten.

(4) Beachten Sie, dass es bis zum i-ten 2 verschiedene Zahlen gibt, aber 3 verschiedene Zustände.

(5) Die Art des Zustandsübergangs unterscheidet sich je nach Gleichmäßigkeit des Index

Es wird angenommen, dass es fünf gibt. Persönlich dachte ich, dass (1) schwer zu bemerken ist, aber ** wenn man bedenkt, dass die Begrenzung der Anzahl der Teile bis zum n-ten n // 2 oder weniger beträgt, denke ich, dass es keine Barriere ist, die nicht überschritten werden kann. Ich möchte mich widmen und es sinnlich erfassen.

answerF.py

n=int(input())
a=list(map(int,input().split()))
minf=-10000000000000
x=[[0,0,0] for i in range(n)]
x[0]=[0,0,a[0]]
for i in range(n-1):
    if i%2==0:
        x[i+1]=[max(x[i][0],x[i][1]),x[i][2],x[i][0]+a[i+1]]
    else:
        x[i+1]=[max(x[i][1],x[i][2]),x[i][0]+a[i+1],x[i][1]+a[i+1]]
print(max(x[-1][1],x[-1][2]) if n%2==0 else max(x[-1][0],x[-1][1]))