AtCoder Grand Contest 041 Review

I would like to review the AGC041 that I had the other day.

This time's results

スクリーンショット 2020-01-01 11.01.52.png

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

AtCoder Grand Contest 041 Review
AtCoder Grand Contest 048 Review
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 152 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Past Question Challenge 1
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 177
yukicoder contest 259 Review
yukicoder contest 264 Review
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
yukicoder contest 261 Review
yukicoder contest 267 Review
AtCoder Beginner Contest 173
yukicoder contest 266 Review
Atcoder Beginner Contest 153
yukicoder contest 263 Review
yukicoder contest 268 Review
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