[PYTHON] AtCoder Beginner Contest 173 Review
This time's results
Impressions of this time
This time, I solved it without any concentration and without proper consideration, so I updated the lowest ranking ever and got the lowest performance in 2020. I think that the E problem could have been solved if I used my head properly, and I feel that D was also lacking in consideration. (Because my mental collapsed on the way ...) But to be honest, I'm not sure what to change to increase the rate ... For the time being, I think there is no choice but to solve various problems and let the typical patterns soak into the body.
Problem A
I was impatient, so I'm embarrassed to solve it crazy from this point.
A.py
n=int(input())
if n%1000==0:
print(0)
else:
print(1000-n%1000)
B problem
It's a problem that I don't really like because typing mistakes are likely to occur. However, I think I could write it better, so I regret it.
B.py
n=int(input())
d={"AC":0,"WA":0,"TLE":0,"RE":0}
for i in range(n):
d[input()]+=1
print("AC x "+str(d["AC"]))
print("WA x "+str(d["WA"]))
print("TLE x "+str(d["TLE"]))
print("RE x "+str(d["RE"]))
C problem
This time, a full bit search came out due to the C problem. I want to think about how to select the rows and columns to be painted in red, so copy the matrix that was input first, overwrite it with red (x), and finally count the number of black (#) that remains. As I was writing this commentary, I noticed that it's easy to implement if you don't bother to copy and count the specified rows and columns, I've been buggy since the first basic problem. maybe.
C.py
h,w,K=map(int,input().split())
c=[input() for i in range(h)]
ans=0
for i in range(2**h):
for j in range(2**w):
d=[[c[z][v] for v in range(w)]for z in range(h)]
for k in range(h):
if (i>>k)&1:
for l in range(w):
d[k][l]="x"
for k in range(w):
if (j>>k)&1:
for l in range(h):
d[l][k]="x"
cnt=0
for k in range(h):
for l in range(w):
cnt+=(d[k][l]=="#")
ans+=(cnt==K)
print(ans)
D problem
For detailed proof, refer to Explanation, and here is a sensuous explanation.
First of all, it seems that ** it is better to arrive in order of friendliness ** from the fact that the situation does not improve even if the people with less friendliness arrive first.
Also, under this assumption, you can think of the ** greedy algorithm **, which is the largest position you should interrupt in the present. That is, you can interrupt as follows:
In the figure above, the friendliness of the person is written on the left side and the comfort is written on the right side. You can see that $ A_i $ gets the friendliness of $ A_ {[\ frac {i + 1} {2}]} $ when interrupting like this (think of it as a complete binary tree). think.). If you notice so far, the implementation is easy and it will be as follows.
I thought I wouldn't be greedy ** and threw it away, but I want to keep in mind that the basics are greedy.
D.py
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=0
for i in range(1,n):
ans+=a[i//2]
print(ans)
E problem
The basic idea is not difficult, but there are so many corner cases that it was a serious problem in terms of mounting.
I couldn't work on the implementation because I thought it would be easier for me to think about it, but when I saw the answer, I felt that I was still lacking in ability because it was written in a neat way. ** I want to gain the ability to think about cases firmly **.
First, notice that there are few patterns in which the product of ** $ K $ numbers is negative **, and consider the case where it is a negative number first. Then, the product of ** $ K $ numbers becomes negative when only an odd number of $ K $ numbers can be selected **. Here, if there is one or more numbers greater than or equal to 0, you can control the evenness and oddness of the number of negative numbers included in the $ K $ number depending on whether the number is included or not. Therefore, the product of $ K $ numbers is negative when all given $ N $ numbers are negative and $ K $ is odd (①), and $ N = K $ and given. If the number of $ N $ includes an odd number of negative numbers (②), it will be either.
Consideration of ① ↓ It is not difficult to calculate when the given number of $ N $ is all negative or all are 0 or more, so I tried to calculate them all together. That is, when the given number of $ N $ is all negative, if $ K $ is even, the product is positive, so the product of $ K $ is the largest in order from the one with the largest absolute value, and $ If K $ is an even number, the product is negative, so the product of $ K $ is the largest in ascending order of absolute value. Also, when all the numbers are 0 or more, the product of $ K $ is the maximum in order from the one with the largest absolute value.
Implementation of ① ↓
Store numbers greater than or equal to 0 in ʻap, store negative numbers in ʻam, and $ N $ if len (ap) == 0 or len (am) == 0 Are all negative numbers (or all positive numbers), so implement as considered. Also, ʻap and ʻam are sorted in descending order of absolute value.
Consideration and implementation of ② ↓ If $ N = K $, consider the product of the given $ N $ numbers. This is requested immediately after receiving the input.
From the above, we will consider the policy under ** where the maximum value of the product of $ K $ numbers is guaranteed to be 0 or more **. (I was confused from this area because I was confused about the policy.)
First, the product of $ K $ cannot be 0 or more unless ** negative numbers are even **, so the product is calculated by pairing ** in order from the number with the largest absolute value. Also, in order to select negative numbers and numbers greater than or equal to 0, the product is calculated by pairing the numbers greater than or equal to 0 in descending order, and these are stored in ʻapm2` in descending order. (After this, I want to check how many numbers 0 or more are selected, so mark 1 for numbers 0 or more and 0 for negative numbers.)
Here, when pairing, there is a possibility that one negative number and one number greater than or equal to 0 may be left over, but if you choose a negative number, you do not need to choose it because the product will be negative, so choose a positive number. Please note that there is a possibility.
First, when ** $ K $ is even **, you can find the product of $ [\ frac {k} {2}] $ numbers from before ʻapm2`, but ** $ K $ is When it is an odd number **, you must select another number in addition to the $ [\ frac {k} {2}] $ number. At this time, if you select "Select one of the largest positive numbers that have not been selected yet (✳︎1)", it is not optimal in the following cases.
5 3
-5 -1 1 2 3
In the above case, -5, -1,3 is the best, but according to (✳︎1), 1,2,3 is the best. In other words, it may be optimal to "choose the largest pair of positive numbers selected, except for the smallest number, which is not selected by ʻapm2` (✳︎2)". (** Be sure to check the optimality with the greedy algorithm! **)
Therefore, while recording the index in ʻap of the number to be selected next as a positive number in p, first ans the number of $ [\ frac {k} {2}] $ from the front. I will append (** Since the operation to remove is troublesome, I tried to temporarily store it in the array ** without asking for the product.).
Under this, if $ K $ is even, find the product of all the numbers of ʻans, and if $ K $ is odd, follow (✳︎1) and (✳︎2) above, ʻap [ Either when selecting p] (①) or when selecting ʻapm2 [k // 2] [0] except for ʻap [p-1] (②).
Here, when p == len (p), all the numbers above 0 are used up, so there is no number corresponding to p, and pattern ① does not exist. Also, when p == 0, no set of numbers greater than or equal to 0 has been used yet, so pattern (2) does not exist. (** Don't forget to consider exceptions! **)
A careful implementation of the above would result in: We also defined a function (multarray) to find the product of a given array divided by $ 10 ^ 9 + 7 $ to simplify implementation.
E.py
#x:Array
mod=10**9+7
def multarray(x):
ret=1
for i in x:
ret*=i
ret%=mod
return ret
n,k=map(int,input().split())
a=list(map(int,input().split()))
#n==In case of k, just call
if n==k:
print(multarray(a))
exit()
#Stored separately for numbers greater than or equal to 0 and negative numbers
ap,am=[],[]
for i in range(n):
if a[i]>=0:
ap.append(a[i])
else:
am.append(a[i])
#Sort by absolute value
ap.sort(reverse=True)
am.sort()
#If there are only numbers greater than or equal to 0 or only positive numbers, the cases are divided first.
if len(am)==0:
print(multarray(ap[:k]))
exit()
if len(ap)==0:
if k%2==0:
print(multarray(am[:k]))
else:
print(multarray(am[::-1][:k]))
exit()
#Store in pairs(Record 0 or more or negative)
apm2=[]
for i in range(len(am)//2):
apm2.append((am[2*i]*am[2*i+1],0))
for i in range(len(ap)//2):
apm2.append((ap[2*i]*ap[2*i+1],1))
apm2.sort(reverse=True)
#Check where to look next with a number greater than or equal to 0
p=0
ans=[]
for i in range(k//2):
p+=(2*apm2[i][1])
ans.append(apm2[i][0])
#When K is even
if k%2==0:
print(multarray(ans))
exit()
ans_cand=[]
#When adding one
if p!=len(ap):
ans_cand.append(multarray(ans)*ap[p]%mod)
#When reducing one and increasing two
if p!=0:
#Decrease index
check_i=ans.index(ap[p-1]*ap[p-2])
#ap[p-1]Operation to reduce(Avoid division by zero)
ans[check_i]=ap[p-2]
ans.append(apm2[k//2][0])
ans_cand.append(multarray(ans))
print(max(ans_cand))
F problem
I haven't solved it yet. I will post a commentary soon.
Recommended Posts