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

Benötigte Zeit

スクリーンショット 2020-04-11 10.34.05.png

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))

Recommended Posts

AtCoder Beginner Contest 102 Rückblick auf frühere Fragen
AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 085 Rückblick auf frühere Fragen
AtCoder Beginner Contest 062 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 051 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 070 Rückblick auf frühere Fragen
AtCoder Beginner Contest 112 Rückblick auf frühere Fragen
AtCoder Beginner Contest 076 Rückblick auf frühere Fragen
AtCoder Beginner Contest 089 Rückblick auf frühere Fragen
AtCoder Beginner Contest 069 Rückblick auf frühere Fragen
AtCoder Beginner Contest 079 Rückblick auf frühere Fragen
AtCoder Beginner Contest 067 Rückblick auf frühere Fragen
AtCoder Beginner Contest 093 Rückblick auf frühere Fragen
AtCoder Beginner Contest 046 Rückblick auf frühere Fragen
AtCoder Beginner Contest 123 Überprüfung früherer Fragen
AtCoder Beginner Contest 049 Rückblick auf frühere Fragen
AtCoder Beginner Contest 078 Rückblick auf frühere Fragen
AtCoder Beginner Contest 081 Rückblick auf frühere Fragen
AtCoder Beginner Contest 047 Rückblick auf frühere Fragen
AtCoder Beginner Contest 060 Rückblick auf frühere Fragen
AtCoder Beginner Contest 104 Rückblick auf frühere Fragen
AtCoder Beginner Contest 057 Rückblick auf frühere Fragen
AtCoder Beginner Contest 126 Rückblick auf frühere Fragen
AtCoder Beginner Contest 090 Rückblick auf frühere Fragen
AtCoder Beginner Contest 103 Rückblick auf frühere Fragen
AtCoder Beginner Contest 061 Rückblick auf frühere Fragen
AtCoder Beginner Contest 059 Rückblick auf frühere Fragen
AtCoder Beginner Contest 044 Rückblick auf frühere Fragen
AtCoder Beginner Contest 083 Rückblick auf frühere Fragen
AtCoder Beginner Contest 048 Rückblick auf frühere Fragen
AtCoder Beginner Contest 124 Rückblick auf frühere Fragen
AtCoder Beginner Contest 116 Rückblick auf frühere Fragen
AtCoder Beginner Contest 097 Rückblick auf frühere Fragen
AtCoder Beginner Contest 088 Rückblick auf frühere Fragen
AtCoder Beginner Contest 099 Rückblick auf frühere Fragen
AtCoder Beginner Contest 065 Rückblick auf frühere Fragen
AtCoder Beginner Contest 053 Rückblick auf frühere Fragen
AtCoder Beginner Contest 094 Rückblick auf frühere Fragen
AtCoder Beginner Contest 063 Rückblick auf frühere Fragen
AtCoder Beginner Contest 107 Rückblick auf frühere Fragen
AtCoder Beginner Contest 071 Rückblick auf frühere Fragen
AtCoder Beginner Contest 064 Rückblick auf frühere Fragen
AtCoder Beginner Contest 082 Rückblick auf frühere Fragen
AtCoder Beginner Contest 084 Rückblick auf frühere Fragen
AtCoder Beginner Contest 068 Rückblick auf frühere Fragen
AtCoder Beginner Contest 043 Rückblick auf frühere Fragen
AtCoder Beginner Contest 098 Rückblick auf frühere Fragen
AtCoder Beginner Contest 114 Rückblick auf frühere Fragen
AtCoder Beginner Contest 045 Rückblick auf frühere Fragen
AtCoder Beginner Contest 120 Rückblick auf frühere Fragen
AtCoder Beginner Contest 108 Rückblick auf frühere Fragen