[PYTHON] AtCoder Anfängerwettbewerb 166 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Insgesamt war ich ungeduldig und auch diesmal war das Ergebnis nicht gut. Ich bin jedoch froh, dass ich glaube, ich war so klebrig wie es war. Außerdem kann ich mich nur auf die ersten 20 Minuten und die letzten 20 Minuten konzentrieren, deshalb möchte ich das verbessern. Ich wollte das F-Problem lösen ...

Ich persönlich denke, dass die Lösung des F-Problems natürlicher ist als Leitartikel.

Problem A

Gibt ABC oder ARC aus.

A.py

s=input()
print("ABC" if s=="ARC" else "ARC")

B-Problem

Sie müssen nur eine der Süßigkeiten haben. Wenn Sie also k Süßigkeiten in der richtigen Reihenfolge betrachten und diese Süßigkeiten haben, ändern Sie das Element der Anordnung, das jeder Person entspricht, in 1 ( Wenn Sie es nicht haben, lassen Sie es bei 0). Darunter reicht es aus, die Elemente des Arrays zu zählen, die nicht 1 sind, so dass es wie folgt wird.

B.py

n,k=map(int,input().split())
ans=[0]*n
for i in range(k):
    d=int(input())
    a=list(map(int,input().split()))
    for j in a:
        ans[j-1]=1
print(n-sum(ans))

C-Problem

Außerdem habe ich es mit dem C-Problem gemacht. Ich dachte, es wäre nicht so viel, aber ich löste das Problem erneut auf Algorithmusbasis ... **. In dem Moment, als ich es sah, war es Union Find !!!. Ich habe es nicht bemerkt, bis ich den Beispielfall ausprobiert und dachte, es sei Union Find und habe ihn implementiert. ** Lesen Sie die Problemstellung sorgfältig durch **.

Wenn Sie die Problemstellung richtig gelesen haben, wird es überhaupt nicht schwierig sein. Wenn es eine Straße j gibt, die $ A_j und B_j $ verbindet, wenn $ A_j \ leqq B_j $, ist $ A_j $ kein gutes Observatorium. Auch wenn $ B_j \ leqq A_j $, ist $ B_j $ kein gutes Observatorium. Nehmen Sie daher für jedes Observatorium zu Beginn ein gutes Observatorium (1) an. Wenn die Straßeninformationen zeigen, dass es sich nicht um ein gutes Observatorium handelt, setzen Sie es auf (0), und schließlich ist nur das gute Observatorium 1 Daher ist es ausreichend, die Summe zu berücksichtigen.

C.py

n,m=map(int,input().split())
h=list(map(int,input().split()))
x=[1]*n
for i in range(m):
    a,b=map(int,input().split())
    if h[a-1]>=h[b-1]:
        x[b-1]=0
    if h[a-1]<=h[b-1]:
        x[a-1]=0
print(sum(x))

D Problem

Ich dachte, dass es in ** A und B ** kein solches Muster geben würde, also versuchte ich, die Kandidaten für ** A und B ** einzugrenzen, aber der Wunsch nach O (1) kam heraus und ich begann zu faktorisieren. (Ich kehrte zu mir selbst zurück, als ich darüber nachdachte, wie die Zitate aussehen würden, nachdem ich sie heruntergerechnet hatte.)

Wenn hier A negativ und B positiv ist, ist $ A ^ 5-B ^ 5 <0 $ nicht gleich X (> 0). Wenn also A negativ ist, ist B immer negativ. .. Wenn sowohl A als auch B negativ sind und $ A ^ 5-B ^ 5 = X $, sind A und B positiv, wenn sowohl A als auch B vertauscht sind und sowohl A als auch B entgegengesetzt sind (positiv). ** A ist eine gute positive Zahl **, da sie als eine Reihe von Zahlen existiert. Sie können zu diesem Zeitpunkt auch $ A> B $ annehmen.

Wenn hier A aus $ B ^ 5 = A ^ 5-X $ bestimmt wird, kann B durch O (1) erhalten werden, also habe ich versucht, den Bereich von A herauszufinden.

Erstens, wenn A fest ist, ist der Minimalwert von $ A ^ 5-B ^ 5 $ $ B = A-1 und $ unter $ A> B $ (wenn $ , weil $ B das Maximum wird). gut). Außerdem ist $ A ^ 5- (A-1) ^ 5 $ ein monotoner Anstieg für A. Wenn hier beispielsweise $ A = 10 ^ 3 $ ist, dann ist $ B = 10 ^ 3-1 $ und $ A ^ 5-B ^ 5 = 4.999009990001 \ times 10 ^ {12} $. Wenn also $ A = 10 ^ 3 $, $ A ^ 5-B ^ 5> 10 ^ {12}> X $, muss A ** kleiner als $ 10 ^ 3 $ ** sein. Daher ist garantiert, dass es mindestens ein Paar von $ (A, B) $ gibt, das die Bedingungen erfüllt, sodass der Bereich von A unter Berücksichtigung von 1 bis 10 ^ 3 $ ** ausreichend ** ist.

Wenn darunter $ B = (A ^ 5-X) ^ {\ frac {1} {5}} $ ist, dann ist $ B ^ 5 = A ^ 5-X $, also jeweils $ A ^ 5 Nehmen Sie die 5. Wurzel von -X $, um B zu finden und festzustellen, ob die Zahl eine ganze Zahl ist. Um zu diesem Zeitpunkt einen Fehler zu vermeiden, wird $ (A ^ 5-X) ^ {\ frac {1} {5}} $, das von der int-Funktion in eine Ganzzahl konvertiert wurde, auf die 5. Potenz und das ursprüngliche $ A ^ erhöht Ich habe überprüft, ob es 5-X $ entspricht. Sie können das Paar (A, B) finden, indem Sie diesen Vorgang wiederholen und abbrechen, wenn ein passendes Paar (A, B) angezeigt wird.

answerD.py

x=int(input())
for A in range(10**3):
    k=A**5-x
    if k>=0:
        l=int(k**0.2)
        if l**5==k:
            print(A,l)
            break
    else:
        k=-k
        l=int(k**0.2)
        if l**5==k:
            print(A,-l)
            break

E Problem

Was ist, wenn ich mich für eine entscheide? Während ich das Experiment mit der Richtlinie durchführte (dieses Experiment dauerte ungefähr 15 Minuten), kam mir die Idee, es einmal zu formulieren, also den relationalen Ausdruck, der zwischen den beiden Personen im Paar gilt Wurde eingerichtet.

Mit anderen Worten, $ A_K + A_L = L-K $ gilt, wenn die Teilnehmer von Nummer K und Nummer L ($ K <L $ ist gut, weil sie die Kombination berücksichtigen) gepaart sind. Diese Formel kann weiter ** transformiert ** werden in $ A_K + K = L- A_L $.

Zu diesem Zeitpunkt ist die Höhe positiv, wenn also $ K \ geqq L $, $ A_K + K \ geqq A_K + L> -A_L + L = L-A_L $ und $ A_K + K = L-A_L $ Hält nicht. Daher werden $ A_i + i $ ($ i = 1,2,…, N $), $ j- A_j $ ($ j = 1,2,…, N $) berechnet und die Werte stimmen mit $ ($ () überein i, j) $ wird als ** Paar akzeptiert, das die Bedingungen ohne Vervielfältigung erfüllt **. Daher werden $ A_i + i $ ($ i = 1,2,…, N $), $ j- A_j $ ($ j = 1,2,…, N $) im Wörterbuch verwaltet und in beiden enthalten Sie müssen nur berechnen, wie viele es für die Nummer gibt.

answerE.py

n=int(input())
a=list(map(int,input().split()))
c,d=dict(),dict()
for i in range(n):
    if i+1-a[i] in c:
        c[i+1-a[i]]+=1
    else:
        c[i+1-a[i]]=1
    if i+1+a[i] in d:
        d[i+1+a[i]]+=1
    else:
        d[i+1+a[i]]=1
ans=0
for i in c:
    if i in d:
        ans+=(c[i]*d[i])
print(ans)

F Problem

Es sollte mit einem Berechnungsbetrag durchgeführt werden, der eindeutig nicht rechtzeitig war, wie DP und DFS. Ich fühle, dass ** sich einmal beruhigen zu können ** die wahre Kraft hier ist ...

Wenn wir auf dieses Problem zurückblicken, können wir sehen, dass A + B + C konstant ist. Außerdem ist es ein Problem, das Spiel zu spielen, daher ist es gut, ** auf den Zustand zu achten **. Da ** alle Grundlagen die gierige Methode ** sind, werden wir auch Experimente unter Berücksichtigung der oben genannten Aspekte durchführen.

Dann können Sie sich gierig (intuitiv) für jede Wahl entscheiden (hier kam ich zu der unlogischen Idee, dass ** es keinen gierigen Grund gibt **). Mit anderen Worten, die Idee ist, dass ** kleine Zahlen nicht und große Zahlen so weit wie möglich subtrahiert werden **. Auf diese Weise können Sie ** bei jeder Auswahl ** vermeiden **.

Wenn Sie so weit denken können, wird die Antwort einen Schritt weiter gehen, aber es sollte beachtet werden, dass es Muster ** gibt, die ** 0 nicht vermeiden können. Das heißt, ein Muster **, bei dem beide auswählbaren Zahlen 0 sind. Daher möchten wir nicht nur Nullen vermeiden, sondern auch dieses Muster bei der nächsten Auswahl vermeiden. Unter der Annahme, dass die aktuelle Auswahl das X. Mal ist, "ist die Zahl, die in der X. Zeitauswahl nicht ausgewählt werden kann, 0 (①)" und "Die für die X + 1. Zeitauswahl verwendete Zeichenfolge ist das für die X. Zeitauswahl verwendete Zeichen". Das Muster von "verschieden von der Spalte (②)" und "die sowohl in der X. Auswahl als auch in der X + 1. Auswahl ausgewählte Nummer ist 1 (③) und die X. Operation ist -1 für diese Nummer" ist ** Da beide Zahlen, die zum X + 1. Mal ausgewählt werden können, 0 Muster ** sind, wird im Fall von ①, ② und ③ das X. Mal mit der Zahl verglichen, die sowohl durch die X. Zeitauswahl als auch durch die X + 1. Zeitauswahl ausgewählt wurde. Alles was Sie tun müssen, ist +1 zu bedienen.

answerF.py

n,a,b,c=map(int,input().split())
s_=input().split()
ans=""
for i in range(n):
    s1,s2=s_[i]
    if s2=="B":
        if i!=n-1:
            if s_[i+1]=="AC" and c==0 and a==1:
                a,b,ans=(a+1,b-1,ans+"A")
            elif s_[i+1]=="BC" and c==0 and b==1:
                a,b,ans=(a-1,b+1,ans+"B")
            else:
                a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        else:
            a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        if min(a,b)==-1:
            print("No")
            break
    elif s1=="A":
        if i!=n-1:
            if s_[i+1]=="AB" and b==0 and a==1:
                a,c,ans=(a+1,c-1,ans+"A")
            elif s_[i+1]=="BC" and b==0 and c==1:
                a,c,ans=(a-1,c+1,ans+"C")
            else:
                a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        else:
            a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        if min(a,c)==-1:
            print("No")
            break
    else:
        if i!=n-1:
            if s_[i+1]=="AB" and a==0 and b==1:
                b,c,ans=(b+1,c-1,ans+"B")
            elif s_[i+1]=="AC" and a==0 and c==1:
                b,c,ans=(b-1,c+1,ans+"C")
            else:
                b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        else:
            b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        if min(b,c)==-1:
            print("No")
            break
else:
    print("Yes")
    for j in range(n):
        print(ans[j])