AtCoder Beginner Contest 099 Review of past questions

Time required

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

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

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions