The result was 76 points, which was intermediate (60-79 points). Last time, I was barely intermediate with 64 points, but this time I was advanced if I solved one more question.
Break through in 3 minutes. If you set Bx to -x and xF to x, you only have to be careful where the difference between B1 and 1F is not 1.
S, T = input().split()
def f(s):
if s[0] == 'B':
return -int(s[1])
else:
return int(s[0]) - 1
print(abs(f(S) - f(T)))
Break through in 3 and a half minutes. Just aggregate and output the most.
S = input()
d ={}
for c in S:
d.setdefault(c, 0)
d[c] += 1
print(sorted(((d[k], k) for k in d), reverse=True)[0][1])
Break through in 12 minutes. Just write according to the problem statement.
N = int(input())
S = [input() for _ in range(N)]
T = [list(l) for l in S]
for i in range(N - 2, -1, -1):
for j in range(2 * N - 1):
if T[i][j] == '.':
continue
if j - 1 >= 0:
if T[i + 1][j - 1] == 'X':
T[i][j] = 'X'
if T[i + 1][j] == 'X':
T[i][j] = 'X'
if j + 1 < 2 * N - 1:
if T[i + 1][j + 1] == 'X':
T[i][j] = 'X'
for l in T:
print(''.join(l))
Break through in 11 minutes. Since "." Is an arbitrary character, it is a regular expression, so it is a regular expression to match. After that, all the patterns are generated, but Python is itertools.product.
from itertools import product
from re import search
S = input()
cs = set(S)
cs.add('.')
result = 0
for i in range(1, 4):
for p in product(cs, repeat=i):
if search(''.join(p), S):
result += 1
print(result)
Break through in 8 and a half minutes. I think there is nothing difficult because I just write it exactly as it is written in the problem statement.
N = int(input())
A = list(map(int, input().split()))
result = []
for i in range(N):
x = i
j = 1
x = A[x] - 1
while x != i:
x = A[x] - 1
j += 1
result.append(j)
print(*result)
Break through in 7 and a half minutes. Reminded me of ABC137D --Summer Vacation. Just take the task with the highest point from the prescription queue and digest it repeatedly.
from heapq import heappush, heappop
N = int(input())
d = {}
for _ in range(N):
A, B = map(int, input().split())
d.setdefault(A, [])
d[A].append(B)
t = []
result = 0
for i in range(1, N + 1):
if i in d:
for b in d[i]:
heappush(t, -b)
result += -heappop(t)
print(result)
Break through in 32 minutes. Solved by DP that seeks the minimum cost from all the previous places to all the next places.
N, M = map(int, input().split())
A = [input() for _ in range(N)]
d = {}
for i in range(N):
for j in range(M):
d.setdefault(A[i][j], [])
d[A[i][j]].append((i, j))
for i in list(range(1, 10)) + ['S', 'G']:
if str(i) not in d:
print(-1)
exit()
dp = [[float('inf')] * M for _ in range(N)]
i, j = d['S'][0]
dp[i][j] = 0
current = 'S'
while current != 'G':
if current == 'S':
next = '1'
elif current == '9':
next = 'G'
else:
next = str(int(current) + 1)
for i, j in d[current]:
for ni, nj in d[next]:
dp[ni][nj] = min(dp[ni][nj], dp[i][j] + abs(ni - i) + abs(nj - j))
current = next
i, j = d['G'][0]
print(dp[i][j])
It broke through in 23 and a half minutes. TLE was inevitable if the character string was created obediently according to the problem statement, so I managed and solved the list of character and length pairs.
from collections import deque
Q = int(input())
S = deque()
for _ in range(Q):
Query = input().split()
if Query[0] == '1':
C = Query[1]
X = int(Query[2])
S.append((C, X))
elif Query[0] == '2':
D = int(Query[1])
d = {}
while D != 0 and len(S) != 0:
C, X = S.popleft()
d.setdefault(C, 0)
if X >= D:
d[C] += D
if X != D:
S.appendleft((C, X - D))
D = 0
else:
d[C] += X
D -= X
print(sum(v * v for v in d.values()))
Break through in 12 minutes. The number of people is 2 N </ sup> and N is as small as 16 or less, so it's easy just to simulate it obediently.
N = int(input())
A = list(map(int, input().split()))
result = [1] * (2 ** N)
t = [(i, A[i]) for i in range(2 ** N)]
while len(t) != 1:
nt = []
for i in range(0, len(t), 2):
ai, aj = t[i]
bi, bj = t[i + 1]
if aj > bj:
result[ai] += 1
nt.append(t[i])
else:
result[bi] += 1
nt.append(t[i + 1])
t = nt
result[t[0][0]] -= 1
for i in result:
print(i)
Break through in 20 minutes. The length of the final character string S is 1000 or less, so it's okay to simulate it obediently. If you find the left parenthesis, look for the paired right parenthesis, and if there is a parenthesis inside it, go ahead Since I have to process it, I write the process with a recursive function and finish.
S = input()
def f(s):
i = s.find('(')
if i == -1:
return s
result = s[:i]
s = s[i:]
i = 1
n = 1
while n != 0:
if s[i] == '(':
n += 1
elif s[i] == ')':
n -= 1
i += 1
t = f(s[1:i - 1])
result += t + t[::-1]
result += f(s[i:])
return result
print(f(S))
To be honest, it becomes * O * (* N * 2 </ sup>) and it is TLE, so consider reducing the amount of calculation. Since it is a greedy method that takes the left end of the minimum value from the selectable range, the interval minimum value Is calculated by Segment Tree, and it becomes * O * ( N </ i> log N </ i>).
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] * (t * 2 - 1)
def update_all(self, iterable):
self._data[self._offset:self._offset+self._size] = iterable
for i in range(self._offset - 1, -1, -1):
self._data[i] = min(self._data[i * 2 + 1], self._data[i * 2 + 2])
def update(self, index, value):
i = self._offset + index
self._data[i] = value
while i >= 1:
i = (i - 1) // 2
self._data[i] = min(self._data[i * 2 + 1], self._data[i * 2 + 2])
def query(self, start, stop):
result = float('inf')
l = start + self._offset
r = stop + self._offset
while l < r:
if l & 1 == 0:
result = min(result, self._data[l])
if r & 1 == 0:
result = min(result, self._data[r - 1])
l = l // 2
r = (r - 1) // 2
return result
N, K, D = map(int, input().split())
A = list(map(int, input().split()))
if 1 + (K - 1) * D > N:
print(-1)
exit()
st = SegmentTree(N)
st.update_all(A)
result = []
i = 0
for k in range(K - 1, -1, -1):
m = st.query(i, N - k * D)
result.append(m)
while A[i] != m:
i += 1
i += D
print(*result)
Addendum: I tried to solve it with the priority queue as explained. Since the value that has already passed is left in the queue, I wondered what to do when it became the minimum, but yeah, it should be discarded Is it ...
from heapq import heappush, heappop
N, K, D = map(int, input().split())
A = list(map(int, input().split()))
if 1 + (K - 1) * D > N:
print(-1)
exit()
result = []
q = []
i = 0
l = 0
for k in range(K - 1, -1, -1):
for j in range(l, N - k * D):
heappush(q, (A[j], j))
l = N - k * D
while True:
a, j = heappop(q)
if j >= i:
break
result.append(a)
i = j + D
print(*result)
I also solved it with Sparse Table. In this problem, SegmentTree is * O * (* N * + (* N * / * D *) log N </ i>), whereas * O * ( > N </ i> log N </ i> + * N * / * D *) so it's a bit slow.
class SparseTable():
_data = None
_lookup = None
_f = None
def __init__(self, a):
data = []
lookup = []
f = min
b = 0
while (1 << b) <= len(a):
b += 1
for _ in range(b):
data.append([0] * (1 << b))
data[0][:len(a)] = a
for i in range(1, b):
j = 0
di = data[i]
di1 = data[i - 1]
while j + (1 << i) <= (1 << b):
di[j] = f(di1[j], di1[j + (1 << (i - 1))])
j += 1
lookup = [0] * (len(a) + 1)
for i in range(2, len(lookup)):
lookup[i] = lookup[i >> 1] + 1
self._data = data
self._lookup = lookup
self._f = f
def query(self, start, stop):
b = self._lookup[stop - start]
db = self._data[b]
return self._f(db[start], db[stop - (1 << b)])
N, K, D = map(int, input().split())
A = list(map(int, input().split()))
if 1 + (K - 1) * D > N:
print(-1)
exit()
st = SparseTable(A)
result = []
i = 0
for k in range(K - 1, -1, -1):
m = st.query(i, N - k * D)
result.append(m)
while A[i] != m:
i += 1
i += D
print(*result)
I can't break through. I do TLE, but I can't even write a naive implementation that gives the correct answer.
Recommended Posts