It took an unusual amount of time to write a normal DP (C problem) and I misread the problem sentence (D problem). I can't think of any solution other than calm down ... Today, the flow of contest → review was relatively smooth, so I will do my best to solve the contest and review every day.
It took a long time because I thought that I had to output the numbers after that even though I only had to output ABD or ACD.
answerA.py
n=int(input())
x=n-999 if n>999 else n
if n>999:
print("ABD")
else:
print("ABC")
Considering the difference between the towers next to each other, the difference between the i + 1st tower and the i-th tower is i + 1, so subtract b from the height of the bath tower or ba-1st tower. Just subtract a from the height.
answerB.py
a,b=map(int,input().split())
k=b-a
print(((1+k)*k)//2-b)
First, when there is the minimum number of operations **, even if the operation is replaced, the number of times remains the minimum **, so the operation to withdraw 1 yen is used for adjustment up to N yen. Here, the operation to pull out the power of 6 from n <= 100000 is $ 6 ^ 1… 6 ^ 6 $, and the operation to pull out the power of 9 is $ 9 ^ 1… 9 ^ 5 $ in 6 ways ($ 6 ^ 7> 100000
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])
First of all, I thought that I could repaint multiple times for one square (because I saw the problem that repainting can be done multiple times in the repainting problem), but this time it is not possible to repaint multiple times. Note that you can't ** (the commented out part).
** Please note that there are such harmful effects if you connect it to the problem or algorithm you solved before **.
First, in other words, for the squares (i, j), the squares with the same mod3 of i + j have the same color, but the squares with different mod3 of i + j have different colors. Therefore, in order to separate cases with mod3 of i + j, ** store each value of mod3 of i + j in the array g **. (1)
Based on this, the colors of the squares will be rewritten in order, but if you decide the color to rewrite the squares for each of the three arrays in the array g, there are $ 30 \ times29 \ times28
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