Break through in 1 minute. Just write.
N = int(input())
print((N + 1) // 2)
Break through in 7 and a half minutes. Just write ... but how should I write if I want to write elegantly ... Especially at the bingo judgment.
A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
for _ in range(N):
b = int(input())
for y in range(3):
for x in range(3):
if A[y][x] == b:
A[y][x] = -1
for y in range(3):
f = True
for x in range(3):
if A[y][x] != -1:
f = False
if f:
print('Yes')
exit()
for x in range(3):
f = True
for y in range(3):
if A[y][x] != -1:
f = False
if f:
print('Yes')
exit()
f = True
for x in range(3):
if A[x][x] != -1:
f = False
if f:
print('Yes')
exit()
f = True
for x in range(3):
if A[2 - x][x] != -1:
f = False
if f:
print('Yes')
exit()
print('No')
Break through in 20 minutes. WA4. Hmm, this is terrible. When N = 1, I overlooked that the first digit can take 0 and it became lumpy. Other than that, it is not difficult to solve, and the digit determined by the array All you have to do is manage and assign the smallest number to the undecided digits.
N, M = map(int, input().split())
t = [-1] * N
for _ in range(M):
s, c = map(int, input().split())
s -= 1
if t[s] != -1 and t[s] != c:
print(-1)
exit()
t[s] = c
if N != 1:
if t[0] == 0:
print(-1)
exit()
if t[0] == -1:
t[0] = 1
for i in range(1, N):
if t[i] == -1:
t[i] = 0
else:
if t[0] == -1:
t[0] = 0
print(''.join(map(str, t)))
Break through in about 25 minutes? I don't know exactly because I made a detour to E. Friend candidates are the size of my friend's friend cluster minus the following.
--My number (= 1) --Number of friends --Number of blocked people in your friend's friend cluster
The size of a friend of a friend cluster can be easily determined with the sized UnionFind.
from sys import setrecursionlimit
def find(parent, i):
t = parent[i]
if t < 0:
return i
t = find(parent, t)
parent[i] = t
return t
def unite(parent, i, j):
i = find(parent, i)
j = find(parent, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
setrecursionlimit(10 ** 5)
N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]
parent = [-1] * N
friends = [[] for _ in range(N)]
for A, B in AB:
unite(parent, A - 1, B - 1)
friends[A-1].append(B-1)
friends[B-1].append(A-1)
blocks = [[] for _ in range(N)]
for C, D in CD:
blocks[C-1].append(D-1)
blocks[D-1].append(C-1)
result = []
for i in range(N):
p = find(parent, i)
t = -parent[p] - 1
t -= len(friends[i])
for b in blocks[i]:
if p == find(parent, b):
t -= 1
result.append(t)
print(*result)
ABC157E - Simple String Queries
Lost. I wondered if I could go with Seg tree and set, but TLE. I wondered if I could go with delayed Seg tree, so I didn't have time to investigate properly, so I wrote appropriately that I should manage Dirty, but performance improved But TLE doesn't disappear. PyPy has improved the performance further, but it's still not enough.
Addendum: If I stopped set and expressed it in bits, it passed easily. Since the character type is only lowercase letters, I can express it with 26 bits. Why does it not flash during the contest (sigh).
class SegmentTree():
_data = []
_offset = 0
_size = 0
def __init__(self, size):
_size = size
t = 1
while t < size:
t *= 2
self._offset = t - 1
self._data = [0 for _ in range(t * 2 - 1)]
def update_all(self, iterable):
self._data[self._offset:self._offset+self._size] = [1 << (ord(c) - ord('a')) for c in iterable]
for i in range(self._offset - 1, -1, -1):
self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]
def update(self, index, value):
i = self._offset + index
self._data[i] = 1 << (ord(value) - ord('a'))
while i >= 1:
i = (i - 1) // 2
self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]
def query(self, start, stop):
result = 0
l = start + self._offset
r = stop + self._offset
while l < r:
if l & 1 == 0:
result = result | self._data[l]
if r & 1 == 0:
result = result | self._data[r - 1]
l = l // 2
r = (r - 1) // 2
return result
N = int(input())
S = input()
st = SegmentTree(N)
st.update_all(S)
Q = int(input())
for _ in range(Q):
q = input().split()
if q[0] == '1':
i, c = q[1:]
i = int(i) - 1
st.update(i, c)
elif q[0] == '2':
l, r = map(int, q[1:])
print(bin(st.query(l - 1, r)).count('1'))
Recommended Posts