AtCoder Beginner Contest 166 Review

This time's results

スクリーンショット 2020-05-03 23.29.43.png

Impressions of this time

Overall, I was impatient, and this time too, the result was not good. However, I'm glad that I think I was sticky as it was. Also, I can concentrate only on the first 20 minutes and the last 20 minutes, so I would like to improve that. I wanted to solve the F problem ...

I personally think that solving the F problem is more natural than editorial, so please refer to it.

Problem A

Outputs ABC or ARC.

A.py


s=input()
print("ABC" if s=="ARC" else "ARC")

B problem

You only need to have any one of the sweets, so if you look at k sweets in order and have those sweets, change the element of the array corresponding to each person to 1 ( If you don't have it, leave it at 0). Under this, it is sufficient to count the elements of the array that are not 1, so it becomes as follows.

B.py


n,k=map(int,input().split())
ans=[0]*n
for i in range(k):
    d=int(input())
    a=list(map(int,input().split()))
    for j in a:
        ans[j-1]=1
print(n-sum(ans))

C problem

Also, I did it with the C problem. I thought it wouldn't be that much, but ** I was solving the problem on an algorithm-based basis ... **. The moment I saw it, it was Union Find !!!. I thought it was Union Find and implemented it without noticing it until I tried the sample case. ** Read the question sentence carefully **.

If you read the question sentence correctly, it will not be difficult at all. When there is a road j connecting $ A_j and B_j $, when $ A_j \ leqq B_j $, $ A_j $ is not a good observatory. Also, when $ B_j \ leqq A_j $, $ B_j $ is not a good observatory. Therefore, for each observatory, assume a good observatory (1) at the beginning, and if the road information shows that it is not a good observatory, set it to (0), and finally only the good observatory is 1 Therefore, it is sufficient to consider the total.

C.py


n,m=map(int,input().split())
h=list(map(int,input().split()))
x=[1]*n
for i in range(m):
    a,b=map(int,input().split())
    if h[a-1]>=h[b-1]:
        x[b-1]=0
    if h[a-1]<=h[b-1]:
        x[a-1]=0
print(sum(x))

D problem

** I thought that there would be no such pattern in A and B **, so I tried to narrow down the candidates for ** A and B **, but the desire for O (1) came out and I started factoring. (I returned to myself when I started to factor and think about what the divisors were like.)

Here, when A is negative and B is positive, $ A ^ 5-B ^ 5 <0 $ is not equal to X (> 0), so when A is negative, B is always negative. .. Also, if both A and B are negative and $ A ^ 5-B ^ 5 = X $, A and B are positive if both A and B are swapped and the signs of both A and B are opposite (positive). ** A is a good positive number ** because it exists as a set of numbers. You can also assume $ A> B $ at this time.

Here, if A is determined from $ B ^ 5 = A ^ 5-X $, B can be obtained by O (1), so I tried to find out the range of A.

First, when A is fixed, the minimum value of $ A ^ 5-B ^ 5 $ is $ B = A-1 and $ under $ A> B $ (if $ \ because $ B becomes the maximum). good). In addition, $ A ^ 5- (A-1) ^ 5 $ is a monotonous increase for A. Here, for example, if $ A = 10 ^ 3 $, then $ B = 10 ^ 3-1 $, and $ A ^ 5-B ^ 5 = 4.999009990001 \ times 10 ^ {12} $. Therefore, when $ A = 10 ^ 3 $, $ A ^ 5-B ^ 5> 10 ^ {12}> X $, so A must be ** less than $ 10 ^ 3 $ **. Therefore, it is guaranteed that there is at least one pair of $ (A, B) $ that satisfies the condition, so the range of A is ** sufficient ** considering from 1 to $ 10 ^ 3 $.

Under this, if $ B = (A ^ 5-X) ^ {\ frac {1} {5}} $, then $ B ^ 5 = A ^ 5-X $, so each $ A ^ 5 Take the 5th root of -X $ to find B and see if the number is an integer. Also, in order to avoid an error at this time, $ (A ^ 5-X) ^ {\ frac {1} {5}} $ converted to an integer by the int function is raised to the 5th power and the original $ A ^ I checked if it matches 5-X $. You can find the (A, B) pair by repeating this operation and breaking when a matching (A, B) pair appears.

answerD.py


x=int(input())
for A in range(10**3):
    k=A**5-x
    if k>=0:
        l=int(k**0.2)
        if l**5==k:
            print(A,l)
            break
    else:
        k=-k
        l=int(k**0.2)
        if l**5==k:
            print(A,-l)
            break

E problem

What if I decide one? While conducting the experiment with the policy (this experiment took about 15 minutes), I came up with the idea of ** let's formulate it once **, so the relational expression that holds between the two pair I set up.

In other words, $ A_K + A_L = L-K $ holds when the participants of number K and number L ($ K <L $ is good because we consider the combination) are paired. This expression can be further ** transformed ** into $ A_K + K = L- A_L $.

At this time, the height is positive, so when $ K \ geqq L $, $ A_K + K \ geqq A_K + L> -A_L + L = L-A_L $, and $ A_K + K = L- A_L $ Does not hold. Therefore, $ A_i + i $ ($ i = 1,2,…, N $), $ j- A_j $ ($ j = 1,2,…, N $) are calculated and the values match $ ($ ( i, j) $ will be accepted as a ** pair that meets the conditions without duplication **. Therefore, $ A_i + i $ ($ i = 1,2,…, N $), $ j- A_j $ ($ j = 1,2,…, N $) are managed in the dictionary and included in both. You just have to calculate how many there are for the number.

answerE.py


n=int(input())
a=list(map(int,input().split()))
c,d=dict(),dict()
for i in range(n):
    if i+1-a[i] in c:
        c[i+1-a[i]]+=1
    else:
        c[i+1-a[i]]=1
    if i+1+a[i] in d:
        d[i+1+a[i]]+=1
    else:
        d[i+1+a[i]]=1
ans=0
for i in c:
    if i in d:
        ans+=(c[i]*d[i])
print(ans)

F problem

It was said that the amount of calculation such as DP and DFS would obviously not be in time. I feel that ** being able to calm down once ** is the true power here ...

Looking back at this problem, we can see that A + B + C is constant. In addition, it is a problem to play games, so it is good to ** pay attention to the state **. Also, since ** all the basics are the greedy algorithm **, we will conduct experiments with the above in mind.

Then you can greedily (intuitively) decide on each choice (here, I ended up with the illogical idea that ** there is no greedy reason **). In other words, the idea is that ** small numbers are not subtracted and large numbers are subtracted ** as much as possible. This way you can ** avoid 0 in each selection **.

If you can think so far, the answer will be one step further, but it should be noted that there are patterns ** that cannot avoid ** 0. That is, a pattern ** where both of the selectable numbers are 0. Therefore, we want to not only avoid 0s, but also prevent this pattern in the next selection. Assuming that the current selection is the Xth time, "the number that cannot be selected in the Xth time selection is 0 (①)" and "the character string used for the X + 1th time selection is the character used for the Xth time selection". The pattern of "different from the column (②)" and "the number selected in both the Xth selection and the X + 1th selection is 1 (③) and the Xth operation is -1 for that number" is ** Since both of the numbers that can be selected at the X + 1th time are 0 patterns **, in the case of ①, ②, and ③, the Xth time is compared to the number selected by both the Xth time selection and the X + 1th time selection. All you have to do is operate +1.

answerF.py


n,a,b,c=map(int,input().split())
s_=input().split()
ans=""
for i in range(n):
    s1,s2=s_[i]
    if s2=="B":
        if i!=n-1:
            if s_[i+1]=="AC" and c==0 and a==1:
                a,b,ans=(a+1,b-1,ans+"A")
            elif s_[i+1]=="BC" and c==0 and b==1:
                a,b,ans=(a-1,b+1,ans+"B")
            else:
                a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        else:
            a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        if min(a,b)==-1:
            print("No")
            break
    elif s1=="A":
        if i!=n-1:
            if s_[i+1]=="AB" and b==0 and a==1:
                a,c,ans=(a+1,c-1,ans+"A")
            elif s_[i+1]=="BC" and b==0 and c==1:
                a,c,ans=(a-1,c+1,ans+"C")
            else:
                a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        else:
            a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        if min(a,c)==-1:
            print("No")
            break
    else:
        if i!=n-1:
            if s_[i+1]=="AB" and a==0 and b==1:
                b,c,ans=(b+1,c-1,ans+"B")
            elif s_[i+1]=="AC" and a==0 and c==1:
                b,c,ans=(b-1,c+1,ans+"C")
            else:
                b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        else:
            b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        if min(b,c)==-1:
            print("No")
            break
else:
    print("Yes")
    for j in range(n):
        print(ans[j])

Recommended Posts

AtCoder Beginner Contest 152 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 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 Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 181 Note
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 188 Note
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