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.
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