[Professional competition practice] I tried AtCoder Beginner Contest 171

We participated in AtCoder Beginner Contest 171. This is my first time participating in a competitive programming contest.

3 Complete, D problem was blocked by the execution time wall, E was also implemented, but TLE is embarrassing with indescribable code when reviewing now ...

A - Alphabet

#Alphabet
S = input()
if S in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
    print('A')
else:
    print('a')

Problem of returning uppercase or lowercase letters for input of one letter of the alphabet. I wish I could judge it from ASCII code etc., but I had never implemented such a thing in Python, so as you can see, I forcibly answered it.

B - Mix Juice

#Mix Juice
N, K = list(map(int, input().split()))
P = sorted(map(int, input().split()))
print(sum(P[0:K]))

The price of each of the N kinds of fruits is given, and the lowest price when purchasing one of the K kinds of fruits is calculated. ↓ Sort N types of prices and answer as the total value of K from the smallest.

C - One Quadrillion and One Dalmatians

#One Quadrillion and One Dalmatians
alphabet = list('abcdefghijklmnopqrstuvwxyz')
N = int(input())-1
 
def shin26(N):
    if(int(N/26)!=0):
        return(shin26(int(N/26)-1)+alphabet[N%26])
    return alphabet[N%26]
 
print(shin26(N))

A question that returns A ~ Z, AA ~ AZ, BA ~ ... for input like EXCEL column number (answer is lowercase). I changed the recursive function to find the N-ary number so that it returns a character string from a to z. Here, too, by creating a list of a to z, the alphabet can be obtained by giving the address of the list.

After this, I learned about the truncation division operator "//" on Python. (It was not necessary to combine int and division operator)

D - Replacing

###Failure###
#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
 
for i in range(Q):
    B, C = list(map(int, input().split()))
    CC = A==B
    NC = CC==False
    A = A*(NC) + C*CC
    print(A.sum())

D Problem could not be done in time. Given an array A, the problem of repeatedly replacing B with C and outputting the total value of A each time. At first, I replaced it honestly, but it sank because the execution time was exceeded.

He advised me that if I knew the number of Bs in the array immediately after the end, I would be able to find the difference from the previous total value (Thank you !!).

###Failure###
#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    if B in u:
        posB = np.where(u==B)
        asum += int(count[posB]) * (C-B)
        # print(u)
        # print(count)
        if not (C in u):
            u[posB] = C
        else :
            posC = np.where(u==C)
            count[posC] += count[posB]
            u = np.delete(u,posB)
            count = np.delete(count,posB)
    print(asum)

Convert array A to an array with count u of a certain number. When changing from B to C, the number was changed, and if it could be integrated, the policy was to integrate (the output is calculated from the difference as described above), but this also sank.

** List search is slow **

I knew……. It is slow to turn a for statement on Python (usually, if there is a calculation to turn a for statement, replace it with a matrix operation and turn it with numpy). Furthermore, acquaintances of C ++ users also suffered from overrun time in the same way.

A plan to create a B → C conversion tree and apply it at the end ↓ Not possible because output is required for each conversion.

After all, glance at the commentary "Since the integer to be input is at most $ 10 ^ 5 $, make an array of $ 10 ^ 5 $ and put the number of the number in the address address." Certainly this does not require a search!

So, I got AC with the following answer.

#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
L = np.zeros(10**5,int)
for i in range(len(u)):
    L[u[i]-1] = count[i]
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    asum += L[B-1] * (C-B)
    L[C-1] += L[B-1]
    L[B-1] = 0
    print(asum)

E - Red Scarf

###Failure###
#Red Scarf
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
output = ''
 
def binary(A, p):
    if not np.all(A==0) :
        return binary( (A-A%2)/2 , p+1 ) + ((A%2).sum())%2 * 2**p
    return ((A%2).sum())%2 * 2**p
 
for i in range(N):
    ken = (np.delete(A,i))
    output += str(int(binary(ken,0)))
    if i != N-1:
        output += ' '
 
print(output)

I didn't have any knowledge of xor, so I decided by binary. End

I did this because I understood that it can be judged by the number of 1s in each digit of the binary number, but TLE. I got an AC below with the advice from an acquaintance that I could take the xor of all the numbers and then take the xor with my own number.

#Red Scarf
N = int(input())
A = list(map(int, input().split()))
output = list()
 
axor = A[0]
for i in range(1,N):
    axor ^= A[i]
 
for i in range(N):
    output.append(axor^A[i])
print(*output)

I added some knowledge that I learned, such as the append method.

Summary

The F problem is untouched. At the next ABC, we are working hard to solve past questions in order to aim for a larger number of complete answers. I'd like to make that happen in the article. .. ..

Recommended Posts

[Professional competition practice] I tried AtCoder Beginner Contest 171
[Professional competition practice] I tried At Coder Beginner Selection
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
Atcoder Beginner Contest 153
AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 182 Note
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 183 Note
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 184 Note
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 188 Note
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 181 Participation Report
AtCoder Beginner Contest 175 Virtual entry
AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Beginner Contest 154 Participation Report
AtCoder Beginner Contest # 003 Participation Note
AtCoder Beginner Contest 166 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Beginner Contest 162 Participation Report
AtCoder Beginner Contest 157 Participation Report
AtCoder Beginner Contest 167 Participation Report