[PYTHON] AtCoder Grand Contest 044 Bewertung

Eindrücke dieser Zeit

A Das Problem war schwierig (ich konnte den Rechenaufwand nicht analysieren), und als ich mich fragte, wie ich es implementieren sollte, war die Zeit abgelaufen. Vielleicht ist es in Ordnung, es zu bestehen, also ist es vielleicht eine gute Idee, es zu werfen. Infolgedessen wurde NoSub zurückgezogen ... Außerdem möchte ich diese Woche in meiner Freizeit das B-Problem lösen.

Problem A

Zunächst möchte ich die während des Wettbewerbs berücksichtigten Methoden erwähnen. Ich dachte, dass +1 und -1 zur Anpassung dienen, und ich dachte, dass dies eindeutig bestimmt werden könnte, indem ** eines von 2 Mal, 3 Mal und 5 Mal wiederholt wird. Daher dachte ich, dass $ n $ als $ k $ ($ \ in $ {$ 2,3,5 $}) Basisnummer betrachtet werden sollte, aber natürlich wird dies nicht anhand der Stichprobe entschieden (1 ohne dies zu bemerken). Es schmolz länger als eine Stunde. Wenn Sie sich beeilen, können Sie nicht logisch denken ...).

Wie auch immer, wenn Sie es nicht lösen können, nehmen Sie den Mut, Ihre Politik zu ändern! !!

Bevor ich mich an diese Richtlinie hielt, versuchte ich übrigens, an DP ** zu denken, das die Anzahl der erforderlichen Münzen von ** $ n $ bis 0 notierte, und entschied, dass dies unmöglich war, da die Anzahl der DP-Elemente $ n $ beträgt. Es war. ** Sie können DP beschleunigen, indem Sie ein Wörterbuch anstelle eines Arrays verwenden **, sodass Sie es mit dieser Methode (in der Nähe von) lösen können, die Sie sich ausgedacht haben ...

Verwenden Sie nun $ n $ bis +1, -1, ÷ 2, ÷ 3, ÷ 5, um 0 zu erhalten. Wenn Sie die Anzahl der Münzen kennen, die Sie für ein bestimmtes $ l $ benötigen, verwenden Sie zunächst +1, -1, ÷ 2, ÷ 3, ÷ 5, um die Anzahl der Ziele einzugrenzen ** (** state) Begrenzt ** sind die Grundlagen wie DP). Angenommen, Sie möchten $ l $ ÷ 5 ausführen. Da $ l $% 5 = 0 erforderlich ist, damit diese Antwort eine Ganzzahl ist, lassen Sie $ l $ +1, -1 handeln, um sie durch 5 teilbar zu machen.

Wenn Sie hier +6 oder mehr oder -6 oder weniger auf $ l $ anwenden, verwenden Sie zu diesem Zeitpunkt Münzen von $ 6 \ mal D $ oder mehr, in diesem Fall jedoch ** 6 oder mehr oder -6 oder weniger. Es ist klar, dass es effizienter ist, es zu brechen, bevor es gebrochen wird, nachdem es funktioniert hat **. 11 → 10 → 1 ("-1" × 1 → "÷ 5" → "-1" × 1) ist besser als (z. B. 11 → 5 → 1 ("-1" × 6 → "÷ 5")) Sie werden weniger Münzen ausgeben.) (Sie können es wahrscheinlich beweisen, indem Sie etwas Ähnliches tun, aber ich werde es hier weglassen.)

In ähnlicher Weise wird die Mindestanzahl von Münzen erhalten, wenn die Anzahl der Münzen, die erforderlich sind, um ein bestimmtes l herzustellen, und die Anzahl der zu teilenden $ k $ ($ \ in $ {$ 2,3,5 $}) bestimmt werden. Bewegen Sie sich in einer solchen Operation zu einem Vielfachen der Zahl, die Sie teilen möchten (2,3,5), in der Nähe von ** $ l $ ** (← Beachten Sie, dass es zwei gibt, die im Code als * am nächsten * geschrieben sind). Teilen Sie dann und führen Sie die nächste Berechnung durch. Zu diesem Zeitpunkt wird eine rekursive Struktur (fraktale Struktur) angezeigt, sodass Sie eine Wiederholung implementieren und eine Erinnerungs-DFS (auch als DP betrachtet) implementieren können.

Beachten Sie auch, dass es in einigen Fällen am besten ist, nur -1 zu tun und von $ l $ auf $ 0 $ zu wechseln, ohne Division zu verwenden. (← Wenn Sie bis zu diesem Punkt mit ** ÷ 2, ÷ 3, ÷ 5 auf 0 zielen möchten, denken Sie nur an **. Wenn Sie also mit ** -1 auf 0 zielen möchten, müssen Sie ** berücksichtigen Natürlich.)

A.py

def dfs(n):
    global b,check,d
    #ttf ist 235, cha ist abc
    #2,3,Bei 5 jeweils
    for ttf,cha in zip([2,3,5],b):
        #-Wenn man eins nach dem anderen geht
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        #Zum nächsten-Wenn Sie tun
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #Zum nächsten+Wenn ich komme
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])