Ceci est un journal pour les débutants en programmation compétitive pour résoudre les problèmes d'atcoder. L'objectif principal est d'encourager la poursuite en publiant le journal. Puisqu'il existe des paramètres et des explications de problème officiels, je les omettrai. Je posterai les impressions (commentaires) que j'ai résolus, les sites et codes auxquels j'ai fait référence dans le revêtement. De plus, puisqu'il restera comme journal de débutant, les codes autres que la bonne réponse seront également affichés. Plus précisément, je publierai un code qui correspond à la politique mais devient TLE comme référence.
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
Je pensais quand j'ai commencé à résoudre des choses comme "Puis-je faire des coordonnées obliques ...?", Mais c'est impossible. En passant, l'accélération du coefficient binomial semble être un paramètre courant.
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)
Lors de la soumission, il est préférable de ne décrire que la méthode nécessaire.
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
Eh bien, l'idée elle-même est correcte. Malheureusement, cela n'a pas assez de temps de calcul. Le fait est qu'en faisant BFS, je cherche à l'intérieur de ʻused_edges et ʻused_colors avec la fonction ʻin`. Les ordres de calcul augmentent ici. La bonne réponse peut être obtenue en éliminant ce calcul supplémentaire.
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)
Changement de la structure de données utilisée dans ʻused_edges et ʻused_colors from list en set. Cela a changé l'ordre moyen des recherches ʻin` de $ O (n) $ à $ 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
Implémentation utilisant le "ModInt" mentionné ci-dessus. Eh bien, c'est une solution que vous voulez absolument essayer au cas où, même si elle ne passe jamais en termes de montant de calcul. Inutile de dire que tourner la double boucle est 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)
C'est une solution hypothétique, mais c'est 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)))
Vous pouvez accélérer en faisant cela. C'est presque quatre fois plus rapide.
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
Je n'ai rien à dire. Quand j'ai lu le sens, j'avais un peu peur que ce soit trop simple et j'ai oublié quelque chose.
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
J'ai eu du mal parce que je l'ai négligé dans ma considération.
AtCoder ABC 150 D - Semi-commun 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
Mettre à jour ʻused après stack.popleft () ʻau lieu de stack.append est 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
Remarquez-vous que vous pouvez stocker tous les nombres dans un tableau bidimensionnel de longueur constante?
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
Au fait, je ne sais pas comment calculer le multiplicateur plus rapidement que l'ordre linéaire.
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)
Pour une raison quelconque, j'ai mal compris que l'itération de $ n-r + 1 $ ~ $ n $ était $ O (N) $ (pourquoi vraiment?). J'ai essayé d'implémenter la méthode square à plusieurs reprises, mais il semble que ce n'est pas nécessaire en python car elle est déjà adoptée dans la fonction pow.
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=' ')
Unifiés first_order_friends et blocks_list. À ce stade, j'ai réalisé que tourner la double boucle était la cause directe de 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=' ')
Basé sur la considération dans le code 2
--Ajouter à ʻexcept_list` seulement si c et d appartiennent au même groupe -Obtenir le nombre d'éléments dans le groupe avec $ O (1) $
Je l'ai changé en.
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++
J'avais peur que 10 $ ^ 6 $ suffiraient, mais cela semble bien.
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
Quand j'ai vu le commentaire, j'ai entendu une voix disant "Ah". Il est trop tard pour le mettre en œuvre.
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))
C'était très rafraîchissant.
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))
C'est plus concis.
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
C'était plus difficile à considérer que la mise en œuvre.
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
Pour moi, une première connaissance complète était nécessaire. Je pourrais penser à une solution pour $ O (m) $ avec $ d = 1 $, mais je ne pouvais pas la généraliser et l'accélérer.
Explication de la "linéarité des valeurs attendues" et résumé des problèmes d'utilisation
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