[PYTHON] AtCoder Beginner Contest 099 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Das Schreiben eines normalen DP (C-Problem) dauerte ungewöhnlich lange, und ich habe den Problemsatz (D-Problem) falsch verstanden. Ich kann mir keine andere Lösung vorstellen, als mich zu beruhigen ... Heute verlief der Ablauf des Wettbewerbs → der Überprüfung relativ reibungslos, daher werde ich mein Bestes geben, um den Wettbewerb zu lösen und jeden Tag zu überprüfen.

Problem A

Es hat lange gedauert, weil ich dachte, ich müsste die Zahlen danach ausgeben, obwohl ich nur ABD oder ACD ausgeben musste.

answerA.py

n=int(input())
x=n-999 if n>999 else n
if n>999:
    print("ABD")
else:
    print("ABC")

B-Problem

In Anbetracht des Unterschieds zwischen benachbarten Türmen beträgt der Unterschied zwischen dem i + 1. Turm und dem i-ten Turm i + 1, also subtrahieren Sie b von der Höhe des Badturms oder des ba-1. Turms. Subtrahieren Sie einfach a von der Höhe.

answerB.py

a,b=map(int,input().split())
k=b-a
print(((1+k)*k)//2-b)

C-Problem

Erstens, wenn es die Mindestanzahl von Operationen ** gibt, bleibt die Anzahl der Operationen das Minimum **, selbst wenn die Operation ersetzt wird **, so dass die Operation zum Abheben von 1 Yen zur Anpassung bis zu N Yen verwendet wird. Hier beträgt die Operation zum Herausziehen der Potenz von 6 aus n <= 100000 $ 6 ^ 1… 6 ^ 6 $, und die Operation zum Herausziehen der Potenz von 9 beträgt auf 6 Arten $ 9 ^ 1… 9 ^ 5 $ ($ 6 ^ 7> 100000 ). Es gibt 5 Möglichkeiten ( 9 ^ 6> 100000 $). Daher habe ich darüber nachgedacht, wie die Operation durch Zulassen der Duplizierung ausgewählt werden soll, und wenn sie kleiner als n ist, habe ich gedacht, dass sie durch 1 kompensiert wird. Daher kann es durch O (n) erhalten werden, indem ** nur DP **, die Operation des Ziehens der Potenz von 6 → die Operation des Ziehens der Potenz von 9 berücksichtigt wird. Wenn der Mindestwert mit DP ermittelt wird, wird inf als Anfangswert in das vorbereitete Array eingegeben, aber k Yen (k <= n) kann durch Verwendung von k 1-Yen-Bällen als Anfangswert ausgedrückt werden Der Anfangswert i wird zugewiesen, wobei der Index i ist.

answerC.py

import math
n=int(input())
l1=math.floor(math.log(n,6))
l2=math.floor(math.log(n,9))
dp=[i for i in range(n+1)]
for i in range(1,l1+1):
    for j in range(n):
        if j+6**i<n+1:
            dp[j+6**i]=min(dp[j]+1,dp[j+6**i])
for i in range(1,l1+1):
    for j in range(n):
        if j+9**i<n+1:
            dp[j+9**i]=min(dp[j]+1,dp[j+9**i])
print(dp[-1])

D Problem

Zunächst dachte ich, ich könnte eine Zelle mehrmals neu streichen (da ich das Problem sah, dass das Neulackieren im Neulackierproblem mehrmals durchgeführt werden kann), aber dieses Mal ist es nicht möglich, mehrere Male neu zu streichen. Beachten Sie, dass Sie nicht ** (der Kommentar aus Teil). ** Bitte beachten Sie, dass es einen so schlechten Effekt gibt, wenn Sie ihn mit dem Problem oder Algorithmus verbinden, den Sie zuvor gelöst haben **. Mit anderen Worten, für das Gitter (i, j) haben die Quadrate mit demselben Mod3 von i + j dieselbe Farbe, aber die Quadrate mit unterschiedlichen Mod3 von i + j haben unterschiedliche Farben. Um Fälle mit mod3 von i + j zu trennen, speichere ** jeden Wert von mod3 von i + j im Array g **. (1) Auf dieser Grundlage werden die Farben der Quadrate der Reihe nach neu geschrieben. Wenn Sie jedoch die Farbe für das Umschreiben der Quadrate für jedes der drei Arrays im Array g festlegen, gibt es $ 30 \ times29 \ times28 , also jedes von ihnen Wenn Sie die Farbe der Quadrate neu schreiben ( 500 \ times500 $), werden Sie feststellen, dass Sie es nicht innerhalb des Zeitlimits schaffen können. Hier haben wir uns entschlossen, eine Vorverarbeitung durchzuführen, um vorab zu berechnen, wie unangenehm es insgesamt sein wird, wenn jede ** quadratische Farbe von 1 auf C ** geändert wird. (2) Darüber hinaus gibt es $ 30 \ times29 \ times28 $ Möglichkeiten, aber ** es ist nicht erforderlich, eine Farbe neu zu schreiben, die sich beim Umschreiben unangenehm anfühlt **, sodass es drei Möglichkeiten gibt, bei denen die Unannehmlichkeiten für jedes der drei in Array g enthaltenen Arrays am geringsten sind. Wählen Sie die Farbe von (3) und finden Sie das Minimum der $ 3 \ times3 \ times3 $ Möglichkeiten, die das Minimum der Summe (4) sein können.

answerD.py

n,c=map(int,input().split())
d=[list(map(int,input().split())) for i in range(c)]
c_=[list(map(int,input().split())) for i in range(n)]

#(1)
g=[[] for i in range(3)]
for i in range(n):
    for j in range(n):
        g[(i+j+2)%3].append(c_[i][j]-1)

'''
for i in range(c):
    for j in range(c):
        for k in range(c):
            d[i][j]=min(d[i][j],d[i][k]+d[k][j])
print(d)
'''

#(2)
f=[[] for i in range(3)]
for i in range(3):
    for j in range(c):
        x=0
        for k in g[i]:
            x+=d[k][j]
        f[i].append((j,x))
    #(3)
    f[i]=sorted(f[i],key=lambda x:x[1])[:3]

#(4)
ans=[]
for i in f[0]:
    for j in f[1]:
        for k in f[2]:
            if i[0]!=j[0] and k[0]!=j[0] and i[0]!=k[0]:
                ans.append(i[1]+j[1]+k[1])
print(min(ans))