[PYTHON] AtCoder Beginner Contest 161 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Das ABC der letzten Woche war eine Parade von Fehlern, aber diese Woche hat es funktioniert. Ich habe es wegen des D-Problems etwa 50 Minuten lang benutzt, und es schien, als würde ich mich auf meine übliche Leistung beschränken, also bin ich froh, dass ich meine Hartnäckigkeit zeigen konnte. Es gibt immer noch Probleme, wie zum Beispiel, dass ich das E-Problem nicht rechtzeitig lösen kann, deshalb würde ich gerne härter arbeiten.

Problem A

Sie müssen nur darüber nachdenken, wie sie ersetzt werden, wenn Sie die Vorgänge in der richtigen Reihenfolge ausführen. Ich entdeckte auch, dass es durch Setzen von `print (z, x, y)` möglich ist, mit einem Leerzeichen zwischen z, x, y auszugeben. Ich würde es von nun an gerne benutzen.

A.py

x,y,z=map(int,input().split())
print(z,x,y)

B-Problem

Da s die Gesamtzahl der Stimmen ist, reicht es aus zu beurteilen, ob die Anzahl von s / 4m oder mehr m oder mehr beträgt.

B.py

n,m=map(int,input().split())
b=list(map(int,input().split()))
s=sum(b)
a=[i for i in b if i>=s/(4*m)]
print("Yes" if len(a)>=m else "No")

C-Problem

Wenn n größer oder gleich k ist, ersetzen Sie n durch n-k. Wenn n kleiner oder gleich k ist, ersetzen Sie es durch k-n. Wenn n kleiner oder gleich k ist, bleibt n auch kleiner oder gleich k, selbst wenn es durch k-n ersetzt wird. Daher ändert sich der Rest der Division durch k während der ersten Operation nicht und ändert sich während der zweiten Operation nicht um n% k oder k-n% k. Daher können Sie `min (n% k, k-n% k)` ausgeben.

C.py

n,k=map(int,input().split())
n=n%k
print(min(n,k-n))

D Problem

Zuerst schrieb ich ein Dendrogramm. Beim Schreiben des Dendrogramms wurde mir klar, dass möglicherweise eine Beziehung zwischen der i-ten Ziffer und der i + 1-ten Ziffer ** besteht. Als ich mit ** experimentierte, was in der 1. bis 2. Stelle passiert **, wurde es wie folgt.

Wenn aus dem Ergebnis des Experiments die Run-Run-Nummer als Zeichenfolge behandelt wird, wird auf der Rückseite der i-stelligen Run-Run-Nummer die ** -Zahl "der absolute Wert der Differenz zwischen der i-stelligen Run-Run-Nummer und der i-ten Ziffer ist 1 oder weniger" hinzugefügt. ** Sie können sehen, dass Sie eine Run-Run-Nummer in der i + 1-Ziffer erstellen können. Wie Sie aus dem obigen Experiment sehen können, müssen ** wenn die i-te Ziffer 0 oder 9 ist, zwei Zahlen am Ende hinzugefügt werden, andernfalls gibt es drei Typen **. (✳︎) Führen Sie daher die obige Operation für jede Ziffer aus und speichern Sie sie im Array **, wenn die Gesamtzahl der im Array enthaltenen Elemente k überschreitet, beenden Sie die obige Operation ** und k darin. Fragen Sie einfach nach dem zweiten.

(✳︎)… Während des Wettbewerbs habe ich es auch auf der Vorderseite hinzugefügt, also habe ich die Duplikate mit set entfernt. Dies ist der erste Code. Der zweite Code ist der Code, der nur auf der Rückseite hinzugefügt wird.

answerD.py

k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        y=int(x[0])
        if y==1:
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        elif 2<=y<=8:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        else:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
        z=int(x[-1])
        if z==0:
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        elif 1<=z<=8:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        else:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
    ans[-1]=list(set(ans[-1]))
    d+=len(ans[-1])
l=len(ans[-1])
v=sorted([int(i) for i in ans[-1]])

print(v[k-(d-l)-1])

answerD_better.py

k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        z=int(x[-1])
        ans[-1].append(x+str(z))
        if z<=8:
            ans[-1].append(x+str(z+1))
        if z>=1:
            ans[-1].append(x+str(z-1))
    d+=len(ans[-1])
ans[-1].sort()
print(ans[-1][k-d-1])

E Problem

Ich sehe den Kommentar. Ich denke, es ist eine gute Frage zu lösen, wenn Sie es vergessen. Als ich dieses Problem sah, hatte ich eine kurzgeschlossene Vorstellung von Intervall → "Imos oder kumulative Summe". Ich denke, dass das Nachdenken darüber, wie man ein Problem löst, das sich auf solche ** Algorithmen konzentriert, eine Denkweise ist, die verhindert, dass man stärker wird **, deshalb möchte ich aufhören. Dieses Mal war es meines Erachtens ein Problem, das eine solche Idee warnte. Dies liegt daran, dass ** alle Grundlagen den Algorithmus verwenden, wenn Sie den Rechenaufwand durch die gierige Methode reduzieren möchten **. Hier werden wir die gierige Methode in Betracht ziehen. (✳︎) Nehmen wir an, wir werden die Tage berücksichtigen, an denen wir für dieses Problem von vorne arbeiten können. Zu diesem Zeitpunkt ** Was bedeutet der i-te gewählte Arbeitstag **? Wie in Antwort angegeben, ist dies der früheste Tag, den Sie auswählen können, wenn Sie den Arbeitstag von vorne auswählen. Mit anderen Worten, ** das i-te Auswahldatum erscheint erst nach diesem Datum **. Im Gegenteil, ** Denken Sie an die Tage, an denen Sie von hinten arbeiten können ** und der j-te ausgewählte Arbeitstag ** erscheint nur vor diesem Tag **. Beachten Sie auch, dass der j-te Tag, der von hinten zählt, der k-j + 1. Tag ist, der von vorne zählt, da er nur k Tage funktioniert. Aus dem oben Gesagten haben wir die Information erhalten, dass das i-te ausgewählte Datum von vorne ** x Tage oder später und y Tage oder früher ** sein muss. Wenn x <y, gibt es mehrere Kandidaten für den i-ten Tag, aber wenn ** x = y, gibt es keine anderen Kandidaten als x (= y) für den i-ten Tag **. Daher können Sie die Antwort finden, indem Sie die Tage zählen, an denen Sie von vorne und hinten in der richtigen Reihenfolge arbeiten können, und nur dann ausgeben, wenn der i-te Arbeitstag von vorne gleich ist. Ich bin von diesem Problem überzeugt, und wenn ein ähnliches Problem auftritt, scheint es reproduzierbar zu sein, aber es war ein Problem, das ich auf den ersten Blick angehen wollte. Ich hatte nach dem Wettbewerb nicht genug Zeit, um die Antwort zu sehen, und ich war enttäuscht. Deshalb möchte ich mich bemühen **, insgesamt zu beschleunigen **, damit ich die sechs Fragen fest lösen kann.

(✳︎)… Die gierige Methode ist kein Algorithmus.

answerE.py

n,k,c=map(int,input().split())
s=input()
l=[-1]*k
r=[-1]*k
nowl=0
indl=0
while nowl<n and indl<k:
    for i in range(nowl,n):
        if s[i]=="o":
            l[indl]=i
            nowl=i+c+1
            indl+=1
            break
nowr=n-1
indr=k-1
while nowr>=0 and indr>=0:
    for i in range(nowr,-1,-1):
        if s[i]=="o":
            r[indr]=i
            nowr=i-c-1
            indr-=1
            break
for i in range(k):
    if l[i]==r[i]:
        print(l[i]+1)

F Problem

Angenommen, $ k (\ neq $ 1) ist ein Bruchteil von ** n **. Hier wird ** n durch k geteilt, bis es nicht mehr durch k ** teilbar ist, und dann wird ** n durch nk ** ersetzt (n mod k bleibt unverändert $ \ leftrightarrow $ n bleibt durch k unteilbar). Werden. Wenn Sie also genauso denken wie das C-Problem, können Sie sagen, dass ** n mod k 1 ist und schließlich n 1 wird **. Wenn ** k kein Bruchteil von n ist, können Sie n nur durch n-k ** ersetzen, sodass Sie nur prüfen müssen, ob n mod k 1 ist. Außerdem wird n mod k zu 1, weil l * k + 1 = n $ \ linker rechter Pfeil $ l * k = n-1, wenn die Operation des Ersetzens von n durch nk l-mal ausgeführt wird. Sie können sehen, dass ** k ein Bruchteil von n-1 ** sein sollte. (✳︎) Beziehen Sie sich im obigen Code auf den Code von make_divisors (ich habe den Code für die Aufzählung der Anzahl der Zahlen nicht selbst vorbereitet, also dieser Artikel) Nachdem alle Fraktionen in () gefunden worden waren, wurde das obige n mod k mit jeder Fraktion als k überprüft. Als ich den Code, den ich während des Wettbewerbs geschrieben habe, noch einmal überprüfte, stellte ich fest, dass der Code ziemlich angemessen geschrieben war, daher möchte ich ihn ** sorgfältig prüfen, bevor ich den Code schreibe.

(✳︎)… Wenn k kein Bruchteil von n ist, kann durch Absurdität gezeigt werden, dass k ein Bruchteil von n-1 ist.

answerF.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=int(input())
x=make_divisors(n)
l=len(x)
ans=0
for i in range(l):
    k=n
    if x[i]==1:
        continue
    while k%x[i]==0:
        k//=x[i]
    if k%x[i]==1:
        ans+=1

y=make_divisors(n-1)
l2=len(y)
ans2=0
for i in range(l2):
    k=n
    if y[i]==1:
        continue
    while k%y[i]==0:
        k//=y[i]
    if k%y[i]==1:
        ans2+=1
print(ans+ans2)

answerF_better.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

def all_pattern(l):
    global n
    ans=0
    for ds in make_divisors(l)[1:]:
        k=n
        while k%ds==0:
            k//=ds
        ans+=(k%ds==1)
    return ans

n=int(input())
print(all_pattern(n)+all_pattern(n-1))