This is a log for beginners in competitive programming to fill in atcoder problems. The main purpose is to encourage continuation by publishing logs. Since there are official problem settings and explanations, I will omit them. I will post the impressions (comments) I solved, the sites and codes that I referred to in the coating. In addition, since it will be left as a beginner log, codes other than the correct answer will also be posted. Specifically, I will post a code that matches the policy but becomes TLE as a reference.
ABC
147 - HonestOrUnkind2
def solve(N, A, X, Y):
ret = 0
for i in range(2 ** N):
tmp = []
for j in range(N):
if i >> j & 1:
tmp.append(j)
if not tmp:
continue
is_valid = True
for a_idx in tmp:
for idx in range(A[a_idx]):
if (Y[a_idx][idx] and X[a_idx][idx] - 1 not in tmp) \
or (not Y[a_idx][idx] and X[a_idx][idx] - 1 in tmp):
is_valid = False
break
ret = max(ret, len(tmp)) if is_valid else ret
return ret
if __name__ == "__main__":
N = int(input())
A = []
X, Y = [], []
for _ in range(N):
A.append(int(input()))
tmp_x, tmp_y = [], []
for _ in range(A[-1]):
x, y = map(int, input().split())
tmp_x.append(x)
tmp_y.append(y)
X.append(tmp_x)
Y.append(tmp_y)
print(solve(N, A, X, Y))
165 - Many Requirements
def solve(cur_index):
global ret
if cur_index == N:
tmp_sum = 0
for i in range(Q):
if A[b[i]] - A[a[i]] == c[i]:
tmp_sum += d[i]
ret = max(ret, tmp_sum)
return
for i in range(min(A[cur_index], M), M + 1):
A[cur_index + 1] = i
solve(cur_index + 1)
if __name__ == '__main__':
N, M, Q = map(int, input().split())
a = [0 for _ in range(Q)]
b = [0 for _ in range(Q)]
c = [0 for _ in range(Q)]
d = [0 for _ in range(Q)]
for i in range(Q):
a[i], b[i], c[i], d[i] = map(int, input().split())
ret = 0
A = [1 for _ in range(N + 1)]
solve(0)
print(ret)
167 - Skill Up
def is_valid(vals, M, X):
for i in range(M):
if vals[i] < X:
return False
return True
def solve(N, M, X, C, A):
ret = float("inf")
for i in range(2 ** N):
tmp_vals = [0 for _ in range(M)]
cost = 0
for j in range(N):
if (i >> j) & 1:
cost += C[j]
for k in range(M):
tmp_vals[k] += A[j][k]
ret = min(ret, cost) if is_valid(tmp_vals, M, X) else ret
return ret if ret != float("inf") else -1
if __name__ == '__main__':
N, M, X = map(int, input().split())
C = []
A = []
for _ in range(N):
tmp = list(map(int, input().split()))
C.append(tmp[0])
A.append(tmp[1:])
print(solve(N, M, X, C, A))
145 - Knight
--If you want to use dynamic programming, just initialize the two-line array and TLE. ――Even if you notice the binomial coefficient, if you do not speed up, it is still TLE. --TLE if you submit it in Python3 even if you speed it up as below.
I was thinking when I started to solve things like "Can I make oblique coordinates ...?", But that's impossible. By the way, speeding up the binomial coefficient seems to be a common setting.
X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3
if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
print(0)
exit()
n, m = map(int, [n, m])
mod = 10**9 + 7
fact = [1]
inv = [1]
for i in range(1, X + Y + 1):
fact.append((fact[i-1] * i) % mod)
inv.append(pow(fact[-1], mod-2, mod))
def cmb(n, r):
return fact[n] * inv[n-r] * inv[r]
print(cmb(n+m, min(n, m)) % mod)
When submitting, it is better to describe only the required method.
X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3
if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
print(0)
exit()
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
n, m = map(int, [n, m])
fact = [ModInt(1)]
for i in range(1, X + Y + 1):
fact.append(fact[i-1] * i)
def cmb(n, r):
return fact[n] / fact[n-r] / fact[r]
print(cmb(n+m, min(n, m)))
146 - Coloring Edges on Tree
Well, the idea itself is correct. Unfortunately, this does not have enough calculation time. The point is that while doing BFS, I'm searching inside ʻused_edges and ʻused_colors with the ʻin` function. Calculation orders are increasing here. The correct answer can be derived by eliminating this extra calculation.
from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
a, b = map(int, input().split())
edges[a].append([edge_idx, b])
edges[b].append([edge_idx, a])
used_edges = []
colors = [1 for _ in range(1, N + 1)]
used_colors = [[] for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1
while stack:
edge_info, parent_node_idx = stack.popleft()
cur_color = 1
for edge_idx, node_idx in edge_info:
if edge_idx in used_edges: continue
while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
cur_color += 1
used_colors[node_idx].append(cur_color)
colors[edge_idx] = cur_color
stack.append([edges[node_idx], node_idx])
used_edges.append(edge_idx)
max_col = max(max_col, cur_color)
cur_color += 1
print(max_col)
for c in colors[1:]:
print(c)
Changed the data structures used in ʻused_edges and ʻused_colors from list to set. This changed the average order for ʻin` searches from $ O (n) $ to $ O (1) $.
Time Complexity - Python Wiki
from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
a, b = map(int, input().split())
edges[a].append([edge_idx, b])
edges[b].append([edge_idx, a])
used_edges = set()
colors = [1 for _ in range(1, N + 1)]
used_colors = [set() for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1
while stack:
edge_info, parent_node_idx = stack.pop()
cur_color = 1
for edge_idx, node_idx in edge_info:
if edge_idx in used_edges: continue
while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
cur_color += 1
used_colors[node_idx].add(cur_color)
colors[edge_idx] = cur_color
stack.append([edges[node_idx], node_idx])
used_edges.add(edge_idx)
max_col = max(max_col, cur_color)
cur_color += 1
print(max_col)
for c in colors[1:]:
print(c)
147 - Xor Sum 4
Implementation using the above-mentioned ModInt. Well, it's a solution that you definitely want to try just in case, although it never passes in terms of calculation amount. Needless to say, turning a double loop is TLE.
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
if isinstance(x, str):
x = int(x)
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
N = int(input())
A = list(map(int, input().split()))
def xor(a, b):
return a ^ b
ret = ModInt(0)
for i in range(N - 1):
for j in range(i + 1, N):
ret += xor(A[i], A[j])
print(ret)
It is a hypothetical solution, but it is TLE.
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
if isinstance(x, str):
x = int(x)
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
def encode(N, A, max_k):
bits = [[0, 0] for _ in range(max_k)]
for i in range(N):
a = format(A[i], 'b').zfill(max_k)
for k in range(max_k):
if int(a[k]) == 0:
bits[max_k - 1 - k][0] += 1
else:
bits[max_k - 1 - k][1] += 1
return bits
def decode(bits):
return sum([ModInt(2 ** k * (counter[0] * counter[1])) for k, counter in enumerate(bits)])
N = int(input())
A = list(map(int, input().split()))
max_k = len(bin(max(A))) - 2
print(decode(encode(N, A, max_k)))
--Do not use arrays --Bit calculation directly without using a character string --Define as a constant (maximum number of digits of A) without finding the maximum value of A
You can speed up by doing this. This is nearly four times faster.
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
if isinstance(x, str):
x = int(x)
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
def calc(N, A, max_k):
ret = ModInt(0)
for k in range(max_k):
count = 0
for i in A:
if i & (1 << k):
count += 1
ret += 2 ** k * count * (N - count)
return ret
N = int(input())
A = list(map(int, input().split()))
max_k = 60
print(calc(N, A, max_k))
148 - Brick Break
I have nothing to say. When I read the sentence, I was a little scared that it was too simple and I overlooked something.
N = int(input())
a = list(map(int, input().split()))
broken = 0
for n in range(N):
if a[n] != broken + 1:
continue
broken += 1
if broken == 0:
print(-1)
else:
print(N - broken)
149 - Prediction and Restriction
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
def getScore(t, R, S, P):
if t == 'r':
return P
if t == 's':
return R
return S
latest = [{'string': '', 'count': 0} for _ in range(K)]
ret = 0
for idx, t in enumerate(T):
latest_idx = idx % K
if idx + 1 <= K or t != latest[latest_idx]['string']:
ret += getScore(t, R, S, P)
latest[latest_idx]['string'] = t
latest[latest_idx]['count'] = 1
continue
if latest[latest_idx]['count'] % 2 == 0:
ret += getScore(t, R, S, P)
latest[latest_idx]['count'] += 1
print(ret)
150 - Semi Common Multiple
I had a hard time because I overlooked it in my consideration.
AtCoder ABC 150 D --Semi Common Multiple (400 points)
from fractions import gcd
def lcm(x, y):
return (x * y) // gcd(x, y)
def solve(N, M, A):
while A[0] % 2 == 0:
for idx, a in enumerate(A):
if a % 2 != 0:
return 0
A[idx] //= 2
M //= 2
for a in A:
if a % 2 == 0:
return 0
cur_lcm = 1
for a in A:
cur_lcm = lcm(cur_lcm, a)
if M < cur_lcm:
return 0
return (M // cur_lcm + 1) // 2
if __name__ == '__main__':
N, M = map(int, input().split())
A = list((map(int, input().split())))
A = [a // 2 for a in A]
print(solve(N, M, A))
151 - Maze Master
Updating ʻused after stack.popleft () instead of stack.append` is TLE.
from collections import deque
def bfs(start, maze, H, W):
max_step = 0
used = [[False for _ in range(W)] for _ in range(H)]
start_x, start_y = start
used[start_x][start_y] = True
stack = deque([[start, 0]])
while stack:
(i, j), step = stack.popleft()
if maze[i][j] == '#':
continue
max_step = max(max_step, step)
for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if 0 <= x < H and 0 <= y < W and not used[x][y]:
stack.append([(x, y), step + 1])
used[x][y] = True
return max_step
if __name__ == '__main__':
H, W = map(int, input().split())
S = []
for _ in range(H):
S.append(list(input()))
ret = 0
for i in range(H):
for j in range(W):
ret = max(ret, bfs((i, j), S, H, W))
print(ret)
152 - Handstand 2
Did you notice that you can store all the numbers in a constant-length two-dimensional array?
def solve(N):
ret = 0
counter = [[0 for _ in range(10)] for _ in range(10)]
for n in range(1, N + 1):
i, j = map(int, [str(n)[0], str(n)[-1]])
counter[i][j] += 1
for i in range(10):
for j in range(10):
ret += counter[i][j] * counter[j][i]
return ret
if __name__ == '__main__':
N = int(input())
ret = solve(N)
print(ret)
156 - Bouquet
By the way, I don't know how to calculate factorial faster than linear order.
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
def cmb(fact, n, r):
return fact[n] / fact[n-r] / fact[r]
def solve(n, a, b):
fact = [ModInt(1)]
for i in range(1, max(n, a, b) + 1):
fact.append(fact[i-1] * i)
return ModInt(2**n) - 1 - cmb(fact, n, a) - cmb(fact, n, b)
if __name__ == '__main__':
n, a, b = map(int, input().split())
ret = solve(n, a, b)
print(ret)
For some reason, I misunderstood the iterator of $ n-r + 1 $ ~ $ n $ as $ O (N) $ (why really?). I tried to implement the square method repeatedly, but it seems that it is not necessary because it is already adopted in the pow function in python.
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
def cmb(fact, n, r):
mul = ModInt(1)
for i in range(n - r + 1, n + 1):
mul *= i
return mul / fact[r]
def solve(n, a, b):
fact = [ModInt(1)]
for i in range(1, max(a, b) + 1):
fact.append(fact[i-1] * i)
return ModInt(pow(2,n)) - 1 - cmb(fact, n, a) - cmb(fact, n, b)
if __name__ == '__main__':
n, a, b = map(int, input().split())
ret = solve(n, a, b)
print(ret)
157 - Friend Suggestions
class UnionFind():
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def members(self, x):
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def solve(uf, first_order_friends, blocked_list):
ret = [0]
for i in range(1, N + 1):
ret.append(len(list(set(uf.members(i)) - first_order_friends[i] - blocked_list[i])) - 1)
return ret
if __name__ == '__main__':
N, M, K = map(int, input().split())
first_order_friends = [set() for _ in range(N + 1)]
blocked_list = [set() for _ in range(N + 1)]
uf = UnionFind(N + 1)
for _ in range(M):
a, b = map(int, input().split())
first_order_friends[a].add(b)
first_order_friends[b].add(a)
uf.union(a, b)
for _ in range(K):
c, d = map(int, input().split())
blocked_list[c].add(d)
blocked_list[d].add(c)
for ans in solve(uf, first_order_friends, blocked_list)[1:]:
print(ans, end=' ')
Unified first_order_friends and blocked_list. At this stage, I realized that turning the double loop was the direct cause of the TLE.
class UnionFind():
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def members(self, x, except_list):
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root and i not in except_list]
def solve(uf, first_order_friends):
ret = [0]
for i in range(1, N + 1):
ret.append(len(uf.members(i, first_order_friends[i])) - 1)
return ret
if __name__ == '__main__':
N, M, K = map(int, input().split())
first_order_friends = [set() for _ in range(N + 1)]
blocked_list = [set() for _ in range(N + 1)]
uf = UnionFind(N + 1)
for _ in range(M):
a, b = map(int, input().split())
first_order_friends[a].add(b)
first_order_friends[b].add(a)
uf.union(a, b)
for _ in range(K):
c, d = map(int, input().split())
first_order_friends[c].add(d)
first_order_friends[d].add(c)
for ans in solve(uf, first_order_friends)[1:]:
print(ans, end=' ')
Based on the consideration in Code 2
--Add to ʻexcept_list` only if c and d belong to the same group -Get the number of elements in the group with $ O (1) $
I changed it to.
class UnionFind():
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def same(self, x, y):
return self.find(x) == self.find(y)
def size(self, x):
return -self.parents[self.find(x)]
def solve(uf, except_list):
ret = [0]
for i in range(1, N + 1):
ret.append(uf.size(i) - 1 - len(except_list[i]))
return ret
if __name__ == '__main__':
N, M, K = map(int, input().split())
except_list = [[] for _ in range(N + 1)]
uf = UnionFind(N + 1)
for _ in range(M):
a, b = map(int, input().split())
except_list[a].append(b)
except_list[b].append(a)
uf.union(a, b)
for _ in range(K):
c, d = map(int, input().split())
if not uf.same(c, d):
continue
except_list[c].append(d)
except_list[d].append(c)
for ans in solve(uf, except_list)[1:]:
print(ans, end=' ')
160 - Line++
I was worried that $ 10 ^ 6 $ would be enough, but it seems to be okay.
from collections import deque
def solve(N, X, Y):
ret = [0] * N
already_used = [[False for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(1, N + 1):
already_used[i][i] = True
reached = [False for _ in range(N + 1)]
reached[i] = True
stack = deque([[i, 0]])
while stack:
node, step = stack.popleft()
if 1 <= step and not already_used[i][node]:
ret[step] += 1
already_used[i][node], already_used[node][i] = True, True
for x in [node + 1, node - 1]:
if 0 < x < N + 1 and not reached[x]:
stack.append([x, step + 1])
reached[x] = True
if node == X and not reached[Y]:
stack.append([Y, step + 1])
reached[x] = True
if node == Y and not reached[X]:
stack.append([X, step + 1])
reached[x] = True
return ret
if __name__ == '__main__':
N, X, Y = map(int, input().split())
for r in solve(N, X, Y)[1:]:
print(r)
161 - Lunlun Number
When I saw the commentary, I heard a voice saying "Ah". It's too late to implement it.
def solve(K):
ref = [[['0'], ['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['8'], ['9']]]
if K < 10:
return ref[0][K][0]
rest = K - 9
i = 0
while True:
i += 1
ref.append([[] for _ in range(10)])
for j in range(10):
if j == 0:
for r in ref[i-1][j] + ref[i-1][j+1]:
ref[i][j].append(str(j) + r)
elif j == 9:
for r in ref[i-1][j-1] + ref[i-1][j]:
ref[i][j].append(str(j) + r)
rest -= 1
if rest == 0:
return str(j) + r
else:
for r in ref[i-1][j-1] + ref[i-1][j] + ref[i-1][j+1]:
ref[i][j].append(str(j) + r)
rest -= 1
if rest == 0:
return str(j) + r
if __name__ == '__main__':
K = int(input())
print(solve(K))
It was very refreshing.
from collections import deque
def solve(K):
stack = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
for _ in range(K):
num = stack.popleft()
one_digit = num % 10
if one_digit % 10 == 0:
nexts = [num * 10, num * 10 + 1]
elif one_digit % 10 == 9:
nexts = [num * 10 + 8, num * 10 + 9]
else:
nexts = [num * 10 + one_digit - 1, num * 10 + one_digit, num * 10 + one_digit + 1]
for n in nexts:
stack.append(n)
return num
if __name__ == '__main__':
K = int(input())
print(solve(K))
163 - Sum of Large Numbers
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
def sumOfArithmeticSequence(a, b):
return (a + b) * (b - a + 1) // 2
def solve(N, K):
ret = ModInt(0)
for i in range(K, N + 2):
ret += sumOfArithmeticSequence(N - i + 1, N) - sumOfArithmeticSequence(0, i - 1) + 1
return ret
if __name__ == '__main__':
N, K = map(int, input().split())
print(solve(N, K))
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
def differenceOfMaximumSumAndMinimumSum(cumulative_sum, i):
return (cumulative_sum[-1] - cumulative_sum[-i-1]) - cumulative_sum[i - 1]
def solve(N, K):
ret = ModInt(1)
cumulative_sum = [0] * (N + 1)
tmp_sum = 0
for i in range(1, N + 1):
tmp_sum += i
cumulative_sum[i] = tmp_sum
for i in range(K, N + 1):
ret += differenceOfMaximumSumAndMinimumSum(cumulative_sum, i) + 1
return ret
if __name__ == '__main__':
N, K = map(int, input().split())
print(solve(N, K))
164 - Multiple of 2019
MOD = 2019
def solve(S):
N = len(S)
dp = [0 for _ in range(MOD)]
tmp = 0
ret = 0
for i in range(N - 1, -1, -1):
m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
ret += dp[m]
dp[m] += 1
tmp = m
ret += dp[0]
return ret
if __name__ == "__main__":
S = input()
print(solve(S))
167 - Teleporter
def solve(N, K, A):
slow, fast = 1, 1
is_first = True
while is_first or slow != fast:
is_first = False
slow = A[slow - 1]
fast = A[A[fast - 1] - 1]
fast = 1
steps_before_entering_cycle = []
while slow != fast:
steps_before_entering_cycle.append(fast)
slow = A[slow - 1]
fast = A[fast - 1]
if K < len(steps_before_entering_cycle):
return steps_before_entering_cycle[K]
cycles = [slow]
while A[slow - 1] != cycles[0]:
cycles.append(A[slow - 1])
slow = A[slow - 1]
ret = cycles[(K - len(steps_before_entering_cycle)) % len(cycles)]
return ret
if __name__ == '__main__':
N, K = map(int, input().split())
A = list(map(int, input().split()))
print(solve(N, K, A))
168 - .. (Double Dots)
from collections import deque, defaultdict
def solve(N, M, paths):
used = [False for _ in range(M)]
stack = deque([1])
ret = [[float("inf"), -1] for _ in range(N + 1)]
ret[1] = [0, 1]
while stack:
cur = stack.popleft()
nexts = paths[cur]
for n in nexts:
if used[n[0]]:
continue
used[n[0]] = True
if ret[cur][0] + 1 < ret[n[1]][0]:
ret[n[1]] = [ret[cur][0] + 1, cur]
stack.append(n[1])
print("Yes")
for r in ret[2:]:
print(r[1])
if __name__ == "__main__":
N, M = map(int, input().split())
paths = defaultdict(list)
for idx in range(M):
a, b = map(int, input().split())
paths[a].append([idx, b])
paths[b].append([idx, a])
solve(N, M, paths)
148 - Double Factorial
def solve(N):
if N < 9 or N % 2:
return 0
ret = 0
N //= 2
while N:
ret += N // 5
N //= 5
return ret
if __name__ == "__main__":
N = int(input())
print(solve(N))
153 - Crested Ibis vs Monster
def solve(h, n, A, B):
dp = [float("inf")] * h + [0]
for i in range(h, -1, -1):
if dp[i] == float("inf"):
continue
for j in range(n):
if 0 <= i - A[j]:
dp[i - A[j]] = min(dp[i - A[j]], dp[i] + B[j])
else:
dp[0] = min(dp[0], dp[i] + B[j])
return dp[0]
if __name__ == '__main__':
h, n = map(int, input().split())
a = [0] * n
b = [0] * n
for i in range(n):
a[i], b[i] = map(int, input().split())
print(solve(h, n, a, b))
160 - Red and Green Apples
def solve(X, Y, p, q, r):
red_apples = sorted(p, reverse=True)[: X]
green_apples = sorted(q, reverse=True)[: Y]
white_apples = sorted(r)
ret = 0
while red_apples and green_apples:
if not white_apples or (white_apples[-1] < red_apples[-1] and white_apples[-1] < green_apples[-1]):
return ret + sum(red_apples) + sum(green_apples)
ret += white_apples.pop(-1)
if red_apples[-1] < green_apples[-1]:
red_apples.pop(-1)
else:
green_apples.pop(-1)
if not red_apples:
while green_apples and white_apples and (green_apples[-1] < white_apples[-1]):
ret += white_apples.pop(-1)
green_apples.pop(-1)
return ret + sum(green_apples)
else:
while red_apples and white_apples and (red_apples[-1] < white_apples[-1]):
ret += white_apples.pop(-1)
red_apples.pop(-1)
return ret + sum(red_apples)
if __name__ == '__main__':
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
print(solve(X, Y, p, q, r))
This is more concise.
def solve(X, Y, p, q, r):
red_apples = sorted(p, reverse=True)[: X]
green_apples = sorted(q, reverse=True)[: Y]
return sum(sorted(red_apples + green_apples + r, reverse=True)[: X + Y])
if __name__ == '__main__':
X, Y, A, B, C = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
print(solve(X, Y, p, q, r))
166 - This Message Will Self-Destruct in 5s
def solve(N, A):
ret = 0
ref = {}
for idx, a in enumerate(A):
ith_val = idx - a
ret += ref[ith_val] if ith_val in ref else 0
ref[idx + a] = ref.get(idx + a, 0) + 1
return ret
if __name__ == '__main__':
N = int(input())
A = list(map(int, input().split()))
print(solve(N, A))
167 - Colorful Blocks
MOD = 998244353
class ModInt:
def __init__(self, x):
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
def cmb(fact, n ,r):
return ModInt(1) * fact[n] / fact[n - r] / fact[r]
def solve(N, M, K):
fact = [ModInt(1)]
for i in range(1, N + 1):
fact.append(fact[i -1] * i)
ret = ModInt(0)
for x in range(K + 1):
ret += cmb(fact, N - 1, x) * M * pow(M - 1, N - x - 1, MOD)
return ret
if __name__ == '__main__':
N, M, K = map(int, input().split())
print(solve(N, M, K))
ARC
def getDivs(N):
divs = []
for i in range(1, int(N**0.5) + 1):
if not N % i:
divs.append(i)
if i != N // i:
divs.append(N // i)
return divs
def solve(N):
divs = getDivs(N)
div_sum = sum(divs)
if div_sum == 2 * N:
return "Perfect"
return "Abundant" if 2 * N < div_sum else "Deficient"
if __name__ == "__main__":
N = int(input())
print(solve(N))
AGC
43 - Range Flip Find Route
It was harder to consider than the implementation.
def solve(H, W, s):
scores = [[float('inf') for _ in range(W)] for _ in range(H)]
scores[0][0] = 0 if s[0][0] == '.' else 1
for i in range(H):
for j in range(W):
for x, y in [(i - 1, j), (i, j - 1)]:
if x < 0 or y < 0:
continue
if s[i][j] == '.' or s[x][y] == '#':
scores[i][j] = min(scores[i][j], scores[x][y])
else:
scores[i][j] = min(scores[i][j], scores[x][y] + 1)
return scores[H - 1][W - 1]
if __name__ == '__main__':
H, W = map(int, input().split())
s = []
for _ in range(H):
s.append(list(input()))
print(solve(H, W, s))
3 - Simplified mahjong
def solve(N, A):
ret = 0
for idx in range(N):
ret += A[idx] // 2
A[idx] %= 2
if A[idx] and idx + 1 < N and A[idx + 1]:
ret += 1
A[idx + 1] -= 1
return ret
if __name__ == "__main__":
N = int(input())
A = [0 for _ in range(N)]
for idx in range(N):
A[idx] = int(input())
print(solve(N, A))
def solve(N, data):
ret = N
data.sort(key=lambda x: x[0] - x[1])
most_right = float("-inf")
for idx, d in enumerate(data):
l, r = d[0] - d[1], d[0] + d[1]
if not idx or most_right <= l:
most_right = r
continue
ret -= 1
most_right = min(r, most_right)
return ret
if __name__ == "__main__":
N = int(input())
data = []
for _ in range(N):
data.append(list(map(int, input().split())))
print(solve(N, data))
SoundHound Inc. Programming Contest 2018 - Ordinary Beauty
For me, a complete first-time knowledge was required. I could think of a solution for $ O (m) $ with $ d = 1 $, but I couldn't generalize it and speed it up.
Explanation of "linearity of expected value" and summary of problems using it
def solve(n, m, d):
return (m - 1) * 2 * (n - d) / n**2 if d else (m - 1) / n
if __name__ == "__main__":
n, m, d = map(int, input().split())
print(solve(n, m, d))
import copy
def solve(N, S):
single_ref = [False for _ in range(10)]
double_ref = [{} for _ in range(N)]
for i in range(N - 1, -1, -1):
if i == N - 1:
single_ref[int(S[i])] = True
continue
double_ref[i] = copy.deepcopy(double_ref[i + 1])
for j in range(10):
if not single_ref[j]:
continue
double_ref[i][S[i] + str(j)] = 1
single_ref[int(S[i])] = True
ret = {}
for i in range(N - 1):
for k in double_ref[i + 1].keys():
ret[S[i] + k] = 1
return len(ret.keys())
if __name__ == "__main__":
N = int(input())
S = input()
print(solve(N, S))
def dfs(s, mx):
if len(s) == N:
print(s)
return
for c in range(ord("a"), mx + 1):
dfs(s + chr(c), mx + 1 if c == mx else mx)
if __name__ == "__main__":
N = int(input())
dfs("", ord("a"))
MOD = 10**9 + 7
class ModInt:
def __init__(self, x):
self.x = x % MOD
def __str__(self):
return str(self.x)
__repr__ = __str__
def __add__(self, other):
return (
ModInt(self.x + other.x) if isinstance(other, ModInt) else
ModInt(self.x + other)
)
def __sub__(self, other):
return (
ModInt(self.x - other.x) if isinstance(other, ModInt) else
ModInt(self.x - other)
)
def __mul__(self, other):
return (
ModInt(self.x * other.x) if isinstance(other, ModInt) else
ModInt(self.x * other)
)
def __truediv__(self, other):
return (
ModInt(
self.x * pow(other.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(self.x * pow(other, MOD - 2, MOD))
)
def __pow__(self, other):
return (
ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(self.x, other, MOD))
)
__radd__ = __add__
def __rsub__(self, other):
return (
ModInt(other.x - self.x) if isinstance(other, ModInt) else
ModInt(other - self.x)
)
__rmul__ = __mul__
def __rtruediv__(self, other):
return (
ModInt(
other.x * pow(self.x, MOD - 2, MOD)
) if isinstance(other, ModInt) else
ModInt(other * pow(self.x, MOD - 2, MOD))
)
def __rpow__(self, other):
return (
ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
ModInt(pow(other, self.x, MOD))
)
def solve(N, A):
ret = ModInt(1)
count = [3 if not i else 0 for i in range(N + 1)]
for a in A:
ret *= count[a]
if not ret:
break
count[a] -= 1
count[a + 1] += 1
return ret
if __name__ == "__main__":
N = int(input())
A = list(map(int, input().split()))
print(solve(N, A))
Recommended Posts