Benötigte Zeit

Impressionen

Dieses Mal war ich mit dem C-Problem festgefahren und konnte die Probleme danach nicht einmal mehr herausfordern ... Ich hielt es für wichtig, die Richtlinien zu klären **, denn wenn ich ungeduldig wäre, würde ich entsprechende Experimente wiederholen. Wenn ich als nächstes ein Problem mit einem Muster habe, das ich nie gelöst habe, möchte ich es fest in Betracht ziehen, um das Obige nicht zu vergessen.

Problem A

Es ist nicht schwierig, wenn Sie auf den Unterschied zwischen H und M achten.

`answerA.py`


h1,m1,h2,m2,k=map(int,input().split())
print((h2-h1)*60+(m2-m1)-k)

B-Problem

Ich habe einen Moment an DP gezweifelt, aber am Ende ist es gut darüber nachzudenken, um wie viel sich der "Doctor / PD-Index" erhöhen wird, je nachdem, ob Sie sich ändern? Zu P oder D **. Wenn Sie zu P wechseln, erhöht es sich nur dann um 1, wenn das Zeichen unmittelbar nach D steht. Wenn Sie jedoch zu D wechseln, erhöht es sich um 1, indem Sie das Zeichen selbst ändern. Wenn sich das Zeichen unmittelbar vor P befindet, erhöht es sich um 1, also alle? Sie können sehen, dass es am besten ist, es in D zu ändern.

`answerB.py`


t=input()
t=t.replace("?","D")
print(t)

C-Problem

Wenn ich darüber nachdachte, fand ich es schwierig, aber als ich mir die Antwort ansah, war es eine natürliche Antwort, und ich dachte, es sei notwendig, sich zu beruhigen und etwas Zeit zu haben, um die Richtlinien festzulegen.

In erster Linie besteht die Richtlinie darin, ** die Anzahl der Scheitelpunkte in jeder Tiefe aufzuzeichnen **. Wenn Sie dies nicht einrichten, können Sie es nicht einmal an der Startlinie einrichten, aber ich denke nicht, dass es schwierig ist, da das Problem darin besteht, dass die Anzahl der Blätter für jede Tiefe festgelegt wird.

Auf dieser Grundlage ** bestimmen Sie die Anzahl der Scheitelpunkte in der Reihenfolge von derjenige, die der Wurzel am nächsten liegt **, und da es sich um einen dichotomisierten Baum handelt, beträgt die maximale Anzahl von Scheitelpunkten in jeder Tiefe $ d $ ** Tiefe $ d-1 $ Sie können sehen, dass es doppelt so viele Eckpunkte minus Blätter gibt. Sie können jedoch im zweiten Beispiel sehen, dass, wenn Sie es auf diese Weise erhöhen, Sie ein Muster von ** erhalten, das schließlich zu viele wird und mehr Blätter hinterlässt **. … ①

Daher habe ich versucht, es so anzupassen, dass es nicht zu viel ist, aber ich konnte es nicht lösen, weil ich es richtig gemacht habe, ohne zu versuchen, diese Anpassung zu verbalisieren.

Während der Diskussion konnte ich auch eine Richtlinie formulieren, um aus dem Gegenteil zu entscheiden, aber ich konnte es nicht herausfinden. Wie Sie aus dem zweiten Beispiel (siehe unten) sehen können, ** muss die Anzahl der Eckpunkte in der Tiefe $ d $ kleiner oder gleich der Summe der Blätter unter $ d $ Tiefe ** sein. Wie in der folgenden Abbildung gezeigt, gibt es für einen Scheitelpunkt, der kein Blatt in einer Tiefe von $ d $ ist, immer ein Blatt in einer bestimmten Tiefe, wenn Sie einem Scheitelpunkt mit einer Tiefe von $ d + 1 $ oder mehr folgen, und verschiedene Pfade zeigen nicht auf denselben Scheitelpunkt. Es kann wie oben gesagt werden. … ②

Wenn Sie ① und ② berücksichtigen können, erhöhen Sie die Anzahl der Scheitelpunkte so weit wie möglich gemäß ① innerhalb der Obergrenze von ② in der Reihenfolge von der nächsten zur Wurzel, basierend auf der kumulierten Summe des Arrays, das die Anzahl der Scheitelpunkte mit einer Tiefe von d oder weniger beibehält. Das ist gut.

Auch in Bezug auf die Betrachtung von (2) denke ich, dass es nicht schwierig ist, weil ** ich es so weit wie möglich erhöhen möchte, aber wenn ich das Gefühl habe, dass ich es nicht erhöhen kann, kann ich nur überlegen, was die Obergrenze ist **. (Schließlich ist es wichtig, beim Organisieren ** zu berücksichtigen, aber wenn Sie an ABC gewöhnt sind, gibt es viele Probleme, die leicht zu berücksichtigen sind, also vergesse ich es ...)

Ich war frustriert, dass ich es während des Wettbewerbs nicht lösen konnte, aber ich fand, dass es eine gute Frage war, die ich in Betracht ziehen konnte, wenn ich mich beruhigte.

`answerC.py`


from itertools import accumulate
n=int(input())
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)
def f():
    global n,a,b
    for i in range(n+1):
        if i==0:
            b[0]=min(c[n]-c[0],1)
        else:
            b[i]=min(2*(b[i-1]-a[i-1]),c[n]-c[i-1])

    if n==0:
        if a[0]!=1:
            print(-1)
        else:
            print(1)
    elif b[n]!=a[n]:
        print(-1)
    else:
        print(sum(b))
f()

`answerC_shortest.py`


p=print;n,*a=map(int,open(0).read().split());t=sum(a);p(sum([w:=1]+[exit(p(-1))if(w:=min(2*(w-q),t:=t-q))<0 else w for q in a]))

Nach D Problem

Da es sich um ARC handelt und es an Fähigkeiten mangelt, wird beurteilt, dass die Priorität niedrig ist und in diesem Artikel nicht erläutert wird.

[PYTHON] Rückblick auf den NOMURA-Programmierwettbewerb 2020