This is a review article for beginners of competition professionals.
The solution I write here is written while looking at the commentary and other people's submissions. It may not be what you actually submitted.
A - Duplex Printing
The question is how many sheets of paper are needed for double-sided printing of page number N.
Divide by 2 and round up.
n = int(input())
print((n+1)//2)
B - Bingo The question is to answer if the numbers and bingo cards given are aligned.
It was a pain to search the 2D array to find the element, so I used the operation of using numpy and replacing it with np.where. I also checked for the presence of bingo by using np.sum () along the vertical and horizontal axes.
Note that pypy3 cannot read numpy.
import numpy as np
S = np.array([list(map(int, input().split())) for _ in range(3)])
n = int(input())
for _ in range(n):
S = np.where(S==int(input()), 0, S)
HBingo = min(np.sum(S, axis=0)) == 0
WBingo = min(np.sum(S, axis=1)) == 0
SBingo = S[2][0] == 0 and S[1][1] == 0 and S[0][2] == 0
BSBingo = S[0][0] == 0 and S[1][1] == 0 and S[2][2] == 0
if HBingo or WBingo or SBingo or BSBingo:
print('Yes')
exit()
print('No')
However, it seems much faster to search the array obediently without using numpy.
C - Guess The Number
It is a problem to return the minimum number that satisfies the conditions of the number of received digits and the number.
First, create each digit with -1 as the initial state. Each time an input is received from it, it is rewritten when either "the value to be rewritten is -1" or "the value to be rewritten does not cause a contradiction" is satisfied. When a contradiction occurs, -1 is output and the process ends.
Finally, convert the digit (-1) that did not rewrite to the minimum value, and you are done. Convert to 1 if it is the first digit from the left (note that 0 is allowed when N = 1), and to 0 if it is after that.
Note that the first digit cannot be changed to 0 when $ N \ geq2 $ (one loss).
N, M = map(int, input().split())
ans = [-1] * N
for _ in range(M):
i, n = map(int, input().split())
if (ans[i-1] == -1 or ans[i-1] == n) and not(N > 1 and i == 1 and n == 0):
ans[i-1] = n
else:
print(-1)
exit()
ans = [n if n != -1 else 0 for n in ans]
if ans[0] == 0 and N > 1:
ans[0] = 1
print(*ans, sep='')
D - Friend Suggestions
Given the status of SNS, it is a question of answering how many relationships are "friends of friends" and "neither friends nor enemies".
I didn't know how to find out if they were connected, so I gave up.
I saw the commentary. The number of friend candidates is the number obtained by subtracting "the number of your friends", "the number of yourself (1)" and "the number of people blocking in the cluster" from "the number of people in the cluster that includes you". Will be.
Therefore, as an array, the array clusterI that stores" the cluster to which each element belongs ", the array clusterN that stores "the number of people in each cluster", and the "number of people blocking with friends" to be drawn later. Create three arrays of ʻout`.
clusterI stores the lowest index in that cluster. This is the problem. The following code is a rough change in the process of rewriting the index with for.
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def unite(x, y):
CX = clusterI[x]
CY = clusterI[y]
if CX != CY:
if CX < CY:
CX, CY = CY, CX
clusterN[CX] += clusterN[CY]
for i in range(n):
if clusterI[i] == CY:
clusterI[i] = CX
for _ in range(m):
a, b = map(int, input().split())
unite(a-1, b-1)
out[a-1] -= 1
out[b-1] -= 1
for _ in range(k):
a, b = map(int, input().split())
if clusterI[a-1] == clusterI[b-1]:
out[a-1] -= 1
out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)
This is TLE.
I rewrote it with a recursive function, referring to other people's code. I passed by this. The big challenge is that you don't have the knowledge about exploration.
n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def find(x):
if clusterI[x] != x:
minI = find(clusterI[x])
clusterI[x] = minI
return minI
else:
return x
def unite(x, y):
CX = find(x)
CY = find(y)
if CX != CY:
if CX > CY:
CX, CY = CY, CX
x, y = y, x
clusterN[CX] += clusterN[CY]
clusterI[CY] = CX
for _ in range(m):
a, b = map(int, input().split())
unite(a-1, b-1)
out[a-1] -= 1
out[b-1] -= 1
for _ in range(k):
a, b = map(int, input().split())
if find(a-1) == find(b-1):
out[a-1] -= 1
out[b-1] -= 1
out = [out[i] + clusterN[find(i)] - 1 for i in range(n)]
print(*out)
E - Simple String Queries
It is a problem to check the number of character types by repeating the operation of converting the character string according to the input.
As always, I did the following code in a straightforward manner.
import collections
N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
Q1, Q2, Q3 = input().split()
if Q1 == '1':
S[int(Q2)-1] = ord(Q3)
else:
print(len(collections.Counter(S[int(Q2)-1: int(Q3)])))
TLE came out.
I looked at the commentary.
Create an array of 26 elements with information about A through Z. The position where the character appears is stored in the element. When counting, check for 26 characters to see if they are within the specified range.
The following is the implementation of that as it is.
N = int(input())
S = list(str(input()))
def ordN(x):
return ord(x) - ord('a')
li = [[] for _ in range(26)]
for i,s in enumerate(S):
li[ordN(s)].append(i)
for i in range(int(input())):
Q1, Q2, Q3 = input().split()
if Q1 == "1":
Q2 = int(Q2) - 1
if S[Q2] != Q3:
li[ordN(S[Q2])] = [n for n in li[ordN(S[Q2])] if n != Q2]
li[ordN(Q3)].append(Q2)
S[Q2] = Q3
else:
Q2, Q3 = int(Q2)-1, int(Q3)-1
count = 0
for j in range(26):
if [True for n in li[j] if Q2 <= n and n <= Q3]:
count += 1
print(count)
At this rate, TLE will still appear. Rewrite with reference to other people's code. The appearance position of characters is kept sorted. In addition, replacement and position check are performed by binary search. The library bisect is used for binary search.
The following two functions are used.
bisect.bisect_left(list, x)
a = [1, 2, 4, 6, 10]
print(bisect.bisect_left(a, 4)) # 3
Returns the position where the second argument can be entered in the list of the first argument without breaking the sort order.
bisect.insort(list, x)
a = [1, 2, 4, 6, 10]
bisect.insort(a, 4)
print(a)# [1, 2, 4, 4, 6, 10]
Inserts into the list of the first argument without breaking the sort order.
The following code was rewritten using this.
import bisect
N = int(input())
S = list(str(input()))
def ordN(x):
return ord(x) - ord('a')
li = [[] for _ in range(26)]
for i,s in enumerate(S):
li[ordN(s)].append(i)
for i in range(int(input())):
Q1, Q2, Q3 = input().split()
if Q1 == "1":
Q2 = int(Q2) - 1
if S[Q2] != Q3:
I = bisect.bisect_left(li[ordN(S[Q2])], Q2)
li[ordN(S[Q2])].pop(I)
bisect.insort(li[ordN(Q3)], Q2)
S[Q2] = Q3
else:
Q2, Q3 = int(Q2)-1, int(Q3)-1
count = 0
for j in range(26):
I = bisect.bisect_left(li[j], Q2)
if I < len(li[j]) and li[j][I] <= Q3:
count += 1
print(count)
I passed by this.
That's all for this article.
Recommended Posts