[PYTHON] AtCoder Beginner Contest 099 Review of past questions

Time required

Impressions

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.

Problem A

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

B problem

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)

C problem

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 ). There are 5 ways ( 9 ^ 6> 100000 $). Therefore, I thought about how to select the operation by allowing duplication, and if it was less than n, I thought that it would be compensated by 1. Therefore, ** DP can be used **, and it can be obtained by O (n) by considering the operation of extracting the power of 6 → the operation of extracting the power of 9. Also, when finding the minimum value with DP, inf is entered as the initial value in the prepared array, but k yen (k <= n) can be expressed by using k 1-yen coins, so as the initial value The initial value i is assigned where the index is i.

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

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 , so each of them If you rewrite the color of the squares ( 500 \ times500 $), you will find that you cannot make it within the time limit. Here, we decided to perform pre-processing to calculate in advance what the total discomfort will be when the color of each square is changed from 1 to C **. (2) In addition, there are $ 30 \ times29 \ times28 $ ways, but ** there is no need to rewrite to a color that feels awkward when rewriting **, so there are 3 ways that each of the three arrays contained in array g has the least discomfort. Choose the color of (3) and find the minimum value in the $ 3 \ times3 \ times3 $ streets that can be the minimum of the total (4).

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