[PYTHON] AtCoder Grand Contest 041 Review
I would like to review the AGC041 that I had the other day.
This time's results
Since I was able to complete it for the first time, I think that I can raise the score to myself, but since I only had to change my mind a little about the C problem, I wanted to complete it three times.
Problem A
I came up with a solution relatively quickly, but I spit out 2WA because I quickly submitted a solution that was clearly wrong and I submitted Python code as C ++ code. First, the easiest thing to understand is when the distance between table A and table B is even. In this case, the table tennis players at each table should reduce the distance between the tables by 2 and output the distance divided by 2. Next, we need to consider the case where the distance between table A and table B is odd. In that case, you can make the distance between the two tables even by going to the end (table 1 or table N) and staying there in one round. At this time, it is necessary to consider the one closer to the end, so you can output the min side with both c and d in the code below. (If you code the formula around here properly, it becomes WA.) The key to this problem is ** classifying the state during the transition **. In this problem, you can see that if you win at table 1 and if you lose at table N, you can only ** ** not move to another table. It is also easy to consider that the case where both are close to each other is clearly the minimum, in which case the distance is even, and when they are at the edge, the evenness changes.
answerA.py
x=[]
n,a,b=map(int,input().split())
if (b-a)%2==0:
print((b-a)//2)
else:
c=(a-1)+(b-a+1)//2
d=(n-b)+(b-a+1)//2
print(min(c,d))
B problem
For the time being, arrange people in descending order. At this time, questions A1 to Ap can be unconditionally adopted because question P is adopted in the contest. Here, if you can change the question of Ap, which has the lowest score among the P questions, to a question smaller than that, the question can be adopted in the contest. If v <= p, continue to vote for A1 ~ Ap-1 and Aj (j> = p + 1), and know that Aj should be able to exceed Ap. On the other hand, in the case of v> p, there are still more votes for Aj (j> = p + 1) even if all the judges vote for A1 ~ Ap-1, Aj, and ** Aj exceeds Ap. You can see that it is not possible to judge just by doing ** (because if there is a vote in Ap, it may exceed Aj). Now, when thinking about how to choose the remaining votes for the judge, we must also notice that even if we vote for Ak (k> j + 1), we will exceed Aj. In other words, even if you vote for A1 ~ Ap-1 and Aj ~ An (at this point, the score of the question you voted for is + m) and put the remaining votes of the judge in Ap ~ Aj-1, Aj will It can be said that Aj can be adopted in the contest if Al (p <= l <= j-1) or more for any l. You can also see that Ap ~ Aj-1 is equal to Aj when the remaining votes of the judge are ** maximally voted so that Ap does not exceed Aj (at this time, Ap ~ Aj-1 is the original Since it is larger than Aj, it is guaranteed that the maximum vote for each will not exceed m). Also, they are arranged in descending order, and ** you will not be able to enter the contest after a certain Aj, so you can search for such Aj by binary search **. To explain the inside of the adopt function, first of all, A1 to Ap-1 do not need to be considered in the first place, so they are sliced as a [p-1:]. b is the value when the maximum vote for Ax + p + 1 (x is considered as 0 index), if b is not more than Ap, it cannot be adopted, so False is returned (1), and al is for all judges. In the total number of votes (however, A1 ~ Ap-1, Ax + p + 1 ~ An will vote, so I have already subtracted that amount), if al is 0 or less, all the judges' votes are used up Therefore, True is returned (2), s is the number of votes required to make Ap ~ Ax + p Ax + p + 1 (b). If al exceeds s, False, otherwise True. To return.
answerB.py
n,m,v,p=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
a=a[p-1:]
le=len(a)
l,r=0,le-1
def adopt(x):
global a,n,m,v,p
b=a[x]+m
#(1)
if b<a[0]:
return False
al=v*m
al-=(n-x)*m
#(2)
if al<=0:
return True
s=x*b-sum(a[:x])
#(3)
if al>s:
return False
else:
return True
while l+1<r:
k=(l+r)//2
if adopt(k):
l=k
else:
r=k
if adopt(r):
print(p+r)
else:
print(p+l)
Code that I went to aim for both shortest and fastest after the contest ↓ (It became a half-finished code that was neither very short nor early.)
answerB_better.py
n,m,v,p=map(int,input().split())
a=sorted(list(map(int, input().split())),reverse=True)[p-1:]
l,r=0,n-p
while l+1<r:
k=(l+r)//2
b=a[k]+m
if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])): r=k
else: l=k
b=a[r]+m
print(p+l if(b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r]))) else p+r)
C problem
I couldn't solve it during the contest. According to the consideration during the contest, it is necessary to equalize the number of dominoes placed vertically and horizontally, and if they are equalized, the quality can be set to 3 to create an arrangement of dominoes that meets the conditions. It turns out (except when n = 2,3). Here, when the dominoes were arranged in consideration of symmetry, when n was a multiple of 3, the dominoes of quality 1 could be found by arranging the dominoes vertically and horizontally along the diagonal line. However, I could not find a highly symmetric arrangement when n was not a multiple of 3 (** I should consider another method here **). So, ** large numbers often work well when split **, so think about this problem as well. Focusing on the partial square matrix from the i-th row to the j-th row and the i-th to j-th column, the part from the i-th row to the j-th row and the i-th to j-th column other than this square matrix is 0. If so, you can see that the quality of the partial square matrix is from row i to column j and from column i to column j. Therefore, we know that we should construct it with such a partial square matrix. Considering the matrix whose quality is 3, I feel that it seems to be found in a square matrix of 4th order or higher. From here, we will do our best to find such a square matrix **. Looking at the method of Answer, I found a square matrix of order 3,4,5,6,7, and divided the cases with mod4 to make it square. You can arrange square matrices in order on the diagonal of the matrix. (Counting from the top, it is 4th, 4th, 4th, ..., (4or5or6or7) It is lined up with the following.) I use mod6 to classify cases when n is a multiple of 3. However, since we need to find a square matrix of order 3,4,5,6,7,8, the solution method is probably the easiest method.
answerC.py
n=int(input())
if n==2:
print(-1)
else:
x=[]
if n%3==0:
for i in range(n//3):
x.append("."*(3*i)+"a"+"."*(n-3*i-1))
x.append("."*(3*i)+"a"+"."*(n-3*i-1))
x.append("."*(3*i)+".aa"+"."*(n-3*i-3))
elif n%6==1:
for i in range(n//6-1):
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
x.append("."*(n-7)+".aab.c.")
x.append("."*(n-7)+"d..b.c.")
x.append("."*(n-7)+"d..eeff")
x.append("."*(n-7)+"g..mm.l")
x.append("."*(n-7)+"gnn...l")
x.append("."*(n-7)+"h...kkj")
x.append("."*(n-7)+"hii...j")
elif n%6==2:
for i in range(n//6-1):
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
x.append("."*(n-8)+".a.bb.cc")
x.append("."*(n-8)+".a...m.j")
x.append("."*(n-8)+"..pp.m.j")
x.append("."*(n-8)+"hh..i.o.")
x.append("."*(n-8)+"gg..i.o.")
x.append("."*(n-8)+"..n.ll.k")
x.append("."*(n-8)+"f.n....k")
x.append("."*(n-8)+"f.dd.ee.")
elif n%6==4:
for i in range(n//6):
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
x.append("."*(n-4)+"aacb")
x.append("."*(n-4)+"ffcb")
x.append("."*(n-4)+"hgdd")
x.append("."*(n-4)+"hgee")
else:
for i in range(n//6):
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+".a.b.c"+"."*(n-6*i-6))
x.append("."*(6*i)+"ddg.ll"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.g.kk"+"."*(n-6*i-6))
x.append("."*(6*i)+"e.hhj."+"."*(n-6*i-6))
x.append("."*(6*i)+"ffiij."+"."*(n-6*i-6))
x.append("."*(n-5)+"aabbc")
x.append("."*(n-5)+"g.h.c")
x.append("."*(n-5)+"gjh..")
x.append("."*(n-5)+"dj.ii")
x.append("."*(n-5)+"deeff")
for i in range(n):
print("".join(x[i]))
After D problem
I felt that it was still at a level that should be solved, so I would like to challenge it the next time I do it.
Recommended Posts