It's free, and chokudai said that I want you to receive it, so I participated in the real thing unlike the past two times. The result is intermediate with 70 points. The first time is 64 points, the second time is 76 points It's a point, so it's just in the middle. I was doing it early in the morning like the last two times, but since I slept for 3 hours, I couldn't help being sleepy from the middle. Maybe that's why I had a lot of WA. I think the rest, but I think it's okay because even a refreshing head can be solved and it's only one question left.
Break through in 2 minutes. Just write.
s = input()
t = input()
if s == t:
print('same')
elif s.lower() == t.lower():
print('case-insensitive')
else:
print('different')
Break through in 10 and a half minutes. It's quite difficult even though it's a B problem !? At first, it takes a lot of time because the person who solved the yukicoder formula early misunderstood that it was the type with a high score.
N, M, Q = map(int, input().split())
score = [N] * (M + 1)
answered = [[False] * (M + 1) for _ in range(N + 1)]
for _ in range(Q):
s = list(map(int, input().split()))
if s[0] == 1:
t = 0
for i in range(1, M + 1):
if answered[s[1]][i]:
t += score[i]
print(t)
elif s[0] == 2:
score[s[2]] -= 1
answered[s[1]][s[2]] = True
Break through in 13 and a half minutes. TLE2, WA1. C problem but naive writing TLE !? In a hurry, bring modpow of O (log N </ i>) implementation for Go language and rewrite it in Python While making a bug and eating WA, AC.
Explanation PDF reference implementation, setrecursionlimit is meaningless, and I'm not sure that sys.stdin.buffer.readline is used instead of sys.stdin.readline, ʻa * r ** (n -1) `It's up to 10 9 + 9 29 </ sup> </ sup>, but I wonder if it's good. O (log N </ i>) I wonder if I want to avoid writing.
A, R, N = map(int, input().split())
result = A
a = R
b = N - 1
while b != 0 and result <= 1000000000:
if b & 1 != 0:
result *= a
a *= a
b >>= 1
if result > 1000000000:
print('large')
else:
print(result)
It broke through in 9 and a half minutes. It wasn't too difficult because I just cut out each character and matched it.
N = int(input())
s = [input() for _ in range(5)]
a = [
'.###..#..###.###.#.#.###.###.###.###.###.',
'.#.#.##....#...#.#.#.#...#.....#.#.#.#.#.',
'.#.#..#..###.###.###.###.###...#.###.###.',
'.#.#..#..#.....#...#...#.#.#...#.#.#...#.',
'.###.###.###.###...#.###.###...#.###.###.'
]
result = []
for i in range(N):
t = [s[j][i * 4:(i + 1) * 4] for j in range(5)]
for j in range(10):
for k in range(5):
if t[k] != a[k][j * 4:(j + 1) * 4]:
break
else:
result.append(j)
break
print(''.join(str(i) for i in result))
It broke through in 8 and a half minutes. Even if I read the problem statement, I thought that if I changed the color of the sprinkler that was running, the surrounding color would change, but I thought that I should change it when it became WA, and submitted it AC. From the point of view, it would be a problem if the sprinklers that were running were adjacent to each other, so it would actually start and stop, and then the next query. It feels like the links have already been written many times, and there is nothing to worry about.
N, M, Q = map(int, input().split())
links = [[] for _ in range(N + 1)]
for _ in range(M):
u, v = map(int, input().split())
links[u].append(v)
links[v].append(u)
c = [0] + list(map(int, input().split()))
for _ in range(Q):
s = list(map(int, input().split()))
if s[0] == 1:
x = s[1]
print(c[x])
for y in links[x]:
c[y] = c[x]
if s[0] == 2:
x, y = s[1:]
print(c[x])
c[x] = y
Break through in 40 minutes and a half? WA2. I forgot to output -1 when it was unreachable and output infinity. Of the other 6 types of movement, only 4 types of up, down, left and right were implemented. I wasted my time because I couldn't get the input example. Well, it's not so difficult because it's a breadth-first search that makes me think how many times I'll write it. sub>, y i </ sub>, X, Y ≤ 200 However, if you make it a space, you can pass through the obstacle next to the edge, but it becomes impassable. Note that you have to spread one by one on the top, bottom, left and right.
from collections import deque
INF = float('inf')
N, X, Y = map(int, input().split())
t = [['.'] * 403 for _ in range(403)]
for _ in range(N):
x, y = map(int, input().split())
t[y + 201][x + 201] = '#'
d = [[INF] * 403 for _ in range(403)]
d[0 + 201][0 + 201] = 0
q = deque([(0, 0)])
while q:
y, x = q.popleft()
i, j = y + 201, x + 201
if i + 1 < 403 and j - 1 >= 0 and t[i + 1][j - 1] != '#' and d[i + 1][j - 1] > d[i][j] + 1:
d[i + 1][j - 1] = d[i][j] + 1
q.append((y + 1, x - 1))
if i + 1 < 403 and j + 1 < 403 and t[i + 1][j + 1] != '#' and d[i + 1][j + 1] > d[i][j] + 1:
d[i + 1][j + 1] = d[i][j] + 1
q.append((y + 1, x + 1))
if i - 1 >= 0 and t[i - 1][j] != '#' and d[i - 1][j] > d[i][j] + 1:
d[i - 1][j] = d[i][j] + 1
q.append((y - 1, x))
if i + 1 < 403 and t[i + 1][j] != '#' and d[i + 1][j] > d[i][j] + 1:
d[i + 1][j] = d[i][j] + 1
q.append((y + 1, x))
if j - 1 >= 0 and t[i][j - 1] != '#' and d[i][j - 1] > d[i][j] + 1:
d[i][j - 1] = d[i][j] + 1
q.append((y, x - 1))
if j + 1 < 403 and t[i][j + 1] != '#' and d[i][j + 1] > d[i][j] + 1:
d[i][j + 1] = d[i][j] + 1
q.append((y, x + 1))
if d[Y + 201][X + 201] == INF:
print(-1)
else:
print(d[Y + 201][X + 201])
Break through in 40 and a half minutes. WA4. The problem of making a palindrome by taking characters from each line of the matrix, but misunderstanding that it is a problem of making a palindrome using all the characters in the matrix. A set of sets. I think you can solve it if you know.
N = int(input())
a = [input() for _ in range(N)]
t = ''
for i in range(N // 2):
u = list(set(a[i]) & set(a[N - 1 - i]))
if len(u) == 0:
print(-1)
exit()
t += u[0]
if N % 2 == 0:
print(t + t[::-1])
else:
print(t + a[N // 2][0] + t[::-1])
It broke through in 27 and a half minutes. I remembered ABC134E --Sequence Decomposing.
N, M = map(int, input().split())
a = list(map(int, input().split()))
eater = [-1] * M
eater[0] = 1
t = [-1] * N
t[0] = a[0]
for i in range(1, M):
ng = -1
ok = N
while abs(ng - ok) > 1:
m = (ok + ng) // 2
if a[i] > t[m]:
ok = m
else:
ng = m
if ok != N:
t[ok] = a[i]
eater[i] = ok + 1
print('\n'.join(str(i) for i in eater))
Break through in 68 minutes. WA2, TLE2, RE2. N ≤ 10 5 </ sup> Make a list of N × N without seeing it. Stupid occurrence. It is big if you actually do column replacement and transposition. Since it is a disaster, I process it with O (1) in the reading table, but I wasted time forgetting that the row swapping and column swapping are swapped at the time of transposition. Isn't there a lot of query problems this time? (3 questions) Eye).
from sys import stdin
readline = stdin.readline
N = int(readline())
Q = int(readline())
result = []
transposed = False
rows = list(range(N + 1))
cols = list(range(N + 1))
for _ in range(Q):
Query = list(map(int, readline().split()))
if Query[0] == 1:
A, B = Query[1:]
if not transposed:
t = rows[A]
rows[A] = rows[B]
rows[B] = t
else:
t = cols[A]
cols[A] = cols[B]
cols[B] = t
elif Query[0] == 2:
A, B = Query[1:]
if not transposed:
t = cols[A]
cols[A] = cols[B]
cols[B] = t
else:
t = rows[A]
rows[A] = rows[B]
rows[B] = t
elif Query[0] == 3:
transposed = not transposed
elif Query[0] == 4:
A, B = Query[1:]
y, x = A, B
if transposed:
y, x = x, y
y = rows[y]
x = cols[x]
result.append(N * (y - 1) + x - 1)
print('\n'.join(str(i) for i in result))
Break through in 63 minutes and a half. WA2, RE1. The biggest thing this time. If you think it's a simple problem with one DP to distribute WA. I don't really understand why, I guess I made a mistake, so I rewrote it in Go language At the moment I wrote T1 / 2 in the middle of writing, I thought I would avoid it, and said," Why are you writing T1 * 0.5? It's a floating point number !!!" Noticed AC.
N, L = map(int, input().split())
x = set(map(int, input().split()))
T1, T2, T3 = map(int, input().split())
dp = [float('inf')] * (L + 4)
dp[0] = 0
for i in range(L):
a = dp[i] + T1
if i + 1 in x:
a += T3
if dp[i + 1] > a:
dp[i + 1] = a
a = dp[i] + T1 + T2
if i + 2 in x:
a += T3
if dp[i + 2] > a:
dp[i + 2] = a
a = dp[i] + T1 + T2 * 3
if i + 4 in x:
a += T3
if dp[i + 4] > a:
dp[i + 4] = a
result = dp[L]
result = min(result, dp[L - 1] + T1 // 2 + T2 // 2)
result = min(result, dp[L - 2] + T1 // 2 + 3 * T2 // 2)
result = min(result, dp[L - 3] + T1 // 2 + 5 * T2 // 2)
print(result)
I gave up because I had 20 minutes left. Anyway, I have to solve 2 questions to become an advanced player. If I record only what is below, I can move with O (1), but which desk is on it now? Is O (* N *), I wondered what to do. However, this time there are many query problems (4th question).
I gave up because I had 20 minutes left. Anyway, I have to solve 2 questions before I can become an advanced player. 1 ≤ a i </ sub> ≤ 2 So can I have two priority queues? Is O (* N *), so I thought it would be impossible, maybe a balanced binary search tree.
Recommended Posts