This time's results

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

AtCoder Beginner Contest 166 Review