はじめに
競技プログラミング初心者がatcoderの問題を埋めていくログです。ログを公開することで継続を促すのが主な目的です。問題設定や解説は公式のものがあるので省略します。解いた感想 (コメント)、コーティングにおいて参考にしたサイトやコードを載せていこうと思います。
なお、初心者ログとして残すので正解以外のコードも掲載します。具体的には、方針は合ってるけどTLEになるようなコードも参考として載せます。
ABC
C問題
005 - おいしいたこ焼きの売り方
コード1. 貪欲法
$time: O(N + M)$
$space: O(N)$
from collections import deque
def solve():
takoyaki = deque()
a_idx = 0
b_idx = 0
for t in range(1, 101):
while takoyaki and takoyaki[0] + T < t:
takoyaki.popleft()
while a_idx < N and A[a_idx] == t:
takoyaki.append(A[a_idx])
a_idx += 1
while b_idx < M and B[b_idx] == t:
if not takoyaki:
print('no')
return
takoyaki.popleft()
b_idx += 1
print('yes')
if __name__ == "__main__":
T = int(input())
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))
solve()
034 - 経路
コード1. nCr
$time: O(N)$
$space: O(N)$
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(W, H):
row, col = W - 1, H - 1
n = row + col
r = row
fact = [ModInt(1)]
for i in range(1, n + 1):
fact.append(fact[i - 1] * i)
print(cmb(fact, n, r))
if __name__ == "__main__":
W, H = map(int, input().split())
solve(W, H)
045 - たくさんの数式
コード1. bit全探索
ジャッジに投げる時はf文字をstrの結合演算子に置換する必要があります。
$time: O(2^N)$
$space: O(2^N)$
def solve(S):
N = len(S) - 1
ret = 0
used_equation = set()
for i in range(pow(2, N)):
tmp_equation = ''
last_j = -1
for j in range(N):
if i >> j & 1:
tmp_equation = f'{tmp_equation} + {S[last_j + 1: j + 1]}'
last_j = j
if last_j < N:
tmp_equation = f'{tmp_equation} + {S[last_j + 1:]}'
ret += eval(tmp_equation) if tmp_equation not in used_equation else 0
used_equation.add(tmp_equation)
print(ret)
if __name__ == "__main__":
S = input()
solve(S)
054 - One-stroke Path
コード1. 順列全探索
$time: O(N!)$
$space: O(N!)$
from collections import deque
def solve():
ret = 0
stack = deque()
stack.append([1, {1}])
while stack:
node, used = stack.popleft()
if len(used) == N:
ret += 1
continue
for n in neighbors[node]:
if n in used:
continue
stack.append([n, used | {n}])
print(ret)
if __name__ == "__main__":
N, M = map(int, input().split())
neighbors = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
neighbors[a].append(b)
neighbors[b].append(a)
solve()
076 - Dubious Document 2
コード１. 辞書式順序
$time: O(|S||T|)$
$space: O(|S|)$
def solve():
if len(S) < len(T):
print('UNRESTORABLE')
return
valid_strs = []
for i in range(len(S)):
for j in range(len(T)):
if len(S) <= i + j or S[i + j] != '?' and S[i + j] != T[j]:
break
else:
valid_strs.append((S[: i] + T + S[i + len(T): ]).replace('?', 'a'))
print(min(valid_strs) if valid_strs else 'UNRESTORABLE')
if __name__ == "__main__":
S = input()
T = input()
solve()
077 - Snuke Festival
コード1. binary search
$time: O(NlogN)$
$space: O(1)$
import bisect
def solve(N, A, B, C):
A.sort()
B.sort()
C.sort()
ret = 0
for j in range(N):
i = bisect.bisect_right(A, B[j] - 1)
k = bisect.bisect_left(C, B[j] + 1)
ret += i * (N - k) if 0 <= i and 0 <= k < N else 0
print(ret)
if __name__ == "__main__":
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
solve(N, A, B, C)
079 - Train Ticket
コード1. bit全探索
$time: O(2^N)$
$space: O(N)$
def solve(operands):
for i in range(pow(2, len(operands) - 1)):
tmp_equation = operands[0]
for j in range(len(operands) - 1):
tmp_equation += '+' if i >> j & 1 else '-'
tmp_equation += operands[j + 1]
if eval(tmp_equation) == 7:
print(tmp_equation + '=7')
return
if __name__ == "__main__":
operands = list(input())
solve(operands)
083 - Multiple Gift
コード1. 貪欲法
$time: O(log \frac{Y}{X})$
$space: O(1)$
def solve():
ret = 1
cur_num = X
while cur_num * 2 <= Y:
cur_num *= 2
ret += 1
print(ret)
if __name__ == "__main__":
X, Y = map(int, input().split())
solve()
104 - All Green
コード1. bit全探索
$time: O(N2^N)$
$space: O(1)$
def solve(D, G, P, C):
ret = float('inf')
for i in range(pow(2, D)):
tmp_score = 0
tmp_counter = 0
not_selected = -1
for j in range(D):
if i >> j & 1:
tmp_counter += P[j]
tmp_score += P[j] * 100 * (j + 1) + C[j]
else:
not_selected = j
if G <= tmp_score:
ret = min(ret, tmp_counter)
continue
for _ in range(1, P[not_selected]):
tmp_score += 100 * (not_selected + 1)
tmp_counter += 1
if G <= tmp_score:
ret = min(ret, tmp_counter)
break
print(ret)
if __name__ == "__main__":
D, G = map(int, input().split())
P = []
C = []
for _ in range(D):
p, c = map(int, input().split())
P.append(p)
C.append(c)
solve(D, G, P, C)
128 - Switches
コード1. bit全探索
$time: O(2^N(MN))$
$space: O(N)$
def solve(N, M, K, S, P):
ret = 0
for i in range(pow(2, N)):
turned_on_switches = []
for j in range(N):
if i >> j & 1:
turned_on_switches.append(j)
for k in range(M):
kth_turned_on_lights_num = 0
for s in S[k]:
kth_turned_on_lights_num += 1 if s - 1 in turned_on_switches else 0
if kth_turned_on_lights_num % 2 != P[k]:
break
else:
ret += 1
print(ret)
if __name__ == "__main__":
N, M = map(int, input().split())
K = []
S = []
for _ in range(M):
tmp = list(map(int, input().split()))
K.append(tmp[0])
S.append(tmp[1:])
P = list(map(int, input().split()))
solve(N, M, K, S, P)
145 - Average Length
コード1. 順列全探索
$time: O(N!)$
$space: O(N!)$
from collections import deque
def solve(N, X, Y):
ret = 0
counter = 0
stack = deque()
cities = [i for i in range(N)]
for city_idx in cities:
stack.append([0, city_idx, cities[:city_idx] + cities[city_idx + 1:]])
while stack:
dist, city_idx, rest = stack.pop()
if not rest:
ret += dist
counter += 1
for idx, next_city_idx in enumerate(rest):
stack.append([dist + ((X[city_idx] - X[next_city_idx])**2 + (Y[city_idx] - Y[next_city_idx])**2)**(1/2), next_city_idx, rest[:idx] + rest[idx + 1:]])
print(ret / counter)
if __name__ == "__main__":
N = int(input())
X = []
Y = []
for _ in range(N):
x, y = map(int, input().split())
X.append(x)
Y.append(y)
solve(N, X, Y)
147 - HonestOrUnkind2
コード1. bit全探索
$time: O(2^N)$
$space: O(N)$
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))
150 - Count Order
コード1. 順列全探索
$time: O(N!)$
$space: O(N!)$
from itertools import permutations
def solve(N, P, Q):
vals = [i for i in range(1, N + 1)]
perms = list(permutations(vals))
print(abs(perms.index(P) - perms.index(Q)))
if __name__ == "__main__":
N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
solve(N, P, Q)
165 - Many Requirements
コード１. DFS
$time: O(Q_{M}H_{N})$
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
コード1. bit全探索
$time: O(M2^N)$
$space: O(N) + O(M)$
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))
D問題
002 - 派閥
コード1. bit全探索
$time: O(2^N N^2)$
$space: O(N)$
def isValidGroup(group_members, relations):
if len(group_members) <= 1:
return True
for i in range(len(group_members)):
for j in range(i + 1, len(group_members)):
if group_members[j] not in relations[group_members[i]]:
return False
return True
def solve(N, relations):
ret = 0
for i in range(pow(2, N)):
current_group_members = []
for j in range(N):
if i >> j & 1:
current_group_members.append(j + 1)
ret = max(ret, len(current_group_members)) if isValidGroup(current_group_members, relations) else ret
print(ret)
if __name__ == "__main__":
N, M = map(int, input().split())
relations = [set() for _ in range(N + 1)]
for _ in range(M):
x, y = map(int, input().split())
relations[x].add(y)
relations[y].add(x)
solve(N, relations)
023 - 射撃王
コード１. 二分探索
$time: O(Nlog(NS))$
$space: O(N)$
def isValid(X, H, S):
bucket = {i: 0 for i in range(N + 1)}
for i in range(N):
if (X - H[i]) // S[i] <= N:
bucket[(X - H[i]) // S[i]] += 1
else:
bucket[N] += 1
T = []
for k in bucket:
T += [k] * bucket[k]
current_time = 0
for t in T:
if t < current_time:
return False
current_time += 1
return True
def solve(N, H, S):
ok = max([H[i] + S[i] * (N - 1) for i in range(N)])
ng = max(H) - 1
while ng < ok - 1:
mid = ng + ok >> 1
if isValid(mid, H, S):
ok = mid
else:
ng = mid
print(ok)
if __name__ == "__main__":
N = int(input())
H = []
S = []
for _ in range(N):
h, s = map(int, input().split())
H.append(h)
S.append(s)
solve(N, H, S)
088 - Grid Repainting
コード１. BFS
$time: O(HW)$
$space: O(HW)$
from collections import deque
def solve():
if s[0][0] == '#':
print(-1)
return
stack = deque()
stack.append([0, 0, 0])
used = [[False for _ in range(W)] for _ in range(H)]
costs = [[float('inf') for _ in range(W)] for _ in range(H)]
while stack:
i, j, cost = stack.popleft()
costs[i][j] = cost
for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if not 0 <= x < H or not 0 <= y < W or used[x][y] or s[x][y] == '#':
continue
stack.append([x, y, cost + 1])
used[x][y] = True
print(dot_num - 1 - costs[H - 1][W - 1] if costs[H - 1][W - 1] != float('inf') else -1)
if __name__ == "__main__":
H, W = map(int, input().split())
s = []
dot_num = 0
for _ in range(H):
tmp = list(input())
dot_num += tmp.count('.')
s.append(tmp)
solve()
103 - Islands War
コード１. 区間スケジューリング
$time: O(M)$
$space: O(1)$
def solve():
ret = 0
most_right = 0
for left, right in sects:
if left < most_right:
continue
ret += 1
most_right = right
print(ret)
if __name__ == "__main__":
N, M = map(int, input().split())
sects = []
for _ in range(M):
sects.append(list(map(int, input().split())))
sects.sort(key=lambda x: x[1])
solve()
138 - Ki
コード１. DFS
$time: O(N + Q)$
$space: O(N)$
from collections import deque
def solve(N, children, weights):
ret = [0 for _ in range(N + 1)]
stack = deque()
stack.append([0, 1])
used = [False for _ in range(N + 1)]
used[1] = True
while stack:
weights_sum, node = stack.pop()
weights_sum += weights[node]
ret[node] = weights_sum
if not children[node]:
continue
for c in children[node]:
if used[c]:
continue
stack.append([weights_sum, c])
used[c] = True
for idx in range(1, N + 1):
print(ret[idx], end=" ")
if __name__ == "__main__":
N, Q = map(int, input().split())
children = [[] for _ in range(N + 1)]
for _ in range(1, N):
a, b = map(int, input().split())
children[a].append(b)
children[b].append(a)
weights = [0 for _ in range(N + 1)]
for _ in range(Q):
p, x = map(int, input().split())
weights[p] += x
solve(N, children, weights)
145 - Knight
- 動的計画法を使おうとする場合、二次元配列を初期化するだけでTLE。
- 二項係数に気付いても高速化しなければやっぱりTLE。
- 下記のように高速化してもPython3で提出したらTLE。
「斜交座標を作ればいけるのか・・・？」みたいなことを解き始めた時には考えていましたが無理ですね。ちなみに二項係数の高速化はよくある設定みたいです。
コード１. ナイーブな実装
$time: O\ (X + Y)$
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
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)
コード2. ModIntの導入 + 逆元計算の高速化
提出の際は必要なmethodだけ記載した方がいいです。
$time: O\ (X + Y)$
Pythonでmodintを実装してみた
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
コード1. 超愚直 BFS (TLE)
まあ考え方自体は合ってますね。残念ながらこれだと計算時間が足りません。ポイントはBFSを行なっている最中にused_edgesやused_colors内をin関数で検索しているところです。ここで計算オーダーが増えています。この余分な計算を無くすことで正解が導かれます。
$time: O(N^2)$
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)
コード2. 改良版 BFS
used_edgesとused_colorsにおいて使用するデータ構造をlistからsetに変更しました。これによりinによる検索の平均オーダーが$O(n)$から$O(1)$になりました。
Time Complexity - Python Wiki
$time: O(N)$
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
コード1. 二重ループ(TLE)
前述のModIntを利用した実装。まあ計算量的に絶対通らないけど念の為試したくなる解法ですね。言うまでもなく二重ループを回すとTLEです。
$time: O(N^2)$
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)
コード2. bitごとにXOR計算 (TLE)
一応想定解法ですが、TLEです。
$time: O(Nlog(max(A)))$
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)))
コード3. bitごとにXOR計算 (高速化)
- 配列を使わない
- 文字列を介さないで直接bit計算
- Aの最大値を求めないで定数として(Aの桁数の最大値を)定義する
ことで高速化できます。これで4倍近く高速化されました。
$time: O(Nlog(max(A)))$
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
コード1. イテレート
何も言うことがないです。文意を読み取った時にシンプルすぎて何か見落としているのではないかと少し怖くなりました。
$time: O(N)$
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
コード1. イテレート
$time: O(N)$
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
コード1. イテレート
考察で見落としがあり、苦戦しました。
AtCoder ABC 150 D - Semi Common Multiple (400 点)
$time: O(N)$
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
コード1. BFS + 2重ループ
stack.appendではなくstack.popleft()の後にusedを更新するとTLEです。
$time: O((HW)^2)$
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
コード1. map生成
全ての数字を定数長の二次元配列に格納できることに気づくかどうかですね。
$time: O(N)$
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
コード1. イテレートして階乗計算（TLE）
そういえば線形オーダーよりも高速で階乗を計算する方法を知らないです。
$time: O(N)$
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)
コード2. nCrの計算を改良
なぜか$n-r+1$~ $n$のイテレートを$O(N)$だと誤解してました（本当になぜ？）。
繰り返し二乗法を実装しようと思いましたが、pythonだとpow関数で既に採用されてるので必要ないみたいです。
$time: max(O(A), O(B))$
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
コード1. 愚直なUnionFind(TLE)
$time: O(N^2)$
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=' ')
コード2. 二重ループ＋UnionFind(TLE)
first_order_friendsとblocked_listを統一しました。この段階で二重ループを回していることがTLEの直接的な原因であることに気づきました。
$time: O(N^2)$
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=' ')
コード3. 入力チェック ＋ UnionFind
コード２での考察を元に
- c,dが同じグループに属する場合のみ
except_listに追加 - $O(1)$でグループの要素数を取得
するように変更しました。
$time: O(N)$
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++
コード1. BFS
$10^6$でも間に合うのか不安でしたが、大丈夫みたいです。
$time: O(N^2)$
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
コード1. 3次元配列
解説見たときに「あっ」って声が出ました。流石にオレオレ実装が過ぎますね。
$time: O(N)$
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))
コード2. deque
大分スッキリしました。
$time: O(N)$
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
コード1. 和の公式
$time: O(N - K)$
$space: O(1)$
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))
コード2. 累積和
$time: O(N)$
$space: O(N)$
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
コード1. DP
$time: O(N)$
$space: O(N)$
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
コード1. Floyd's cycle finding
$time: O(N)$
$space: O(N)$
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)
コード1. BFS
$time: O(N + M)$
$space: O(N + M)$
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)
171 - Replacing
コード1. イテレート
$time: O(N + Q)$
$space: O(N)$
def solve():
ret = sum(A)
dict_A = {}
for a in A:
dict_A[a] = dict_A.get(a, 0) + 1
for i in range(Q):
tmp = dict_A.get(B[i], 0)
ret -= tmp * B[i]
dict_A[B[i]] = 0
dict_A[C[i]] = dict_A.get(C[i], 0) + tmp
ret += C[i] * tmp
print(ret)
if __name__ == "__main__":
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B, C = [], []
for _ in range(Q):
b, c = map(int, input().split())
B.append(b)
C.append(c)
solve()
172 - Sum of Divisors
コード1. ループの入れ替え
$time: O(N)$
$space: O(1)$
def solve():
ret = 0
for k in range(1, N + 1):
y = N // k
ret += k * y * (y + 1) // 2
print(ret)
if __name__ == "__main__":
N = int(input())
solve()
E問題
148 - Double Factorial
コード1. 式変形
$time: O(logN)$
$space: O(1)$
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
コード1. dp
$time: O(NH)$
$space: O(H)$
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
コード1. ソート ＋ イテレート
$time: max(O(X + Y), O(AlogA), O(BlogB), O(ClogC))$
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))
コード2. ソート
こちらの方が簡潔ですね。
$time: max(O(AlogA), O(BlogB), O((X + Y + C)log(X + Y + C)))$
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
コード1. イテレート + 辞書
$time: O(N)$
$sapce: O(N)$
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
コード1. 異なる色の数をイテレート
$time: O(N)$
$space: O(N)$
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
A問題
029 - 高橋君とお肉
コード1. bit全探索
$time: O(2^N)$
$space: O(1)$
def solve(N, T):
shortest_time = float('inf')
for i in range(pow(2, N)):
left_totoal_time = 0
right_total_time = 0
for j in range(N):
if i >> j & 1:
left_totoal_time += T[j]
else:
right_total_time += T[j]
shortest_time = min(shortest_time, max(left_totoal_time, right_total_time))
print(shortest_time)
if __name__ == "__main__":
N = int(input())
T = []
for _ in range(N):
T.append(int(input()))
solve(N, T)
B問題
026 - 完全数
コード1. 約数列挙
$time: O(\sqrt{N})$
$space: O(\sqrt{N})$
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))
031 - 埋め立て
コード1. BFS
$N = 100$
$time: O(N^2)$
$space: O(N)$
from collections import deque
def bfs(i, j, area_count):
stack = deque()
stack.append([i, j])
used = [[False for _ in range(C)] for _ in range(R)]
used[i][j] = True
while stack:
x, y = stack.popleft()
area_count -= 1
for r, c in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if not 0 <= r < R or not 0 <= c < C or A[r][c] == 'x' or used[r][c]:
continue
stack.append([r, c])
used[r][c] = True
return not area_count
def solve():
for i in range(R):
for j in range(C):
if bfs(i, j, total_area_count if A[i][j] == 'o' else total_area_count + 1):
print('YES')
return
print('NO')
if __name__ == "__main__":
R, C = 10, 10
A = []
total_area_count = 0
for _ in range(R):
a = list(input())
total_area_count += a.count('o')
A.append(a)
solve()
037 - バウムテスト
コード1. BFS
$time: O(N + M)$
$space: O(N)$
from collections import deque
def solve():
ret = 0
used = [False for _ in range(N + 1)]
stack = deque()
for i in range(1, N + 1):
if used[i]:
continue
if not neighbors[i]:
ret += 1
continue
for n in neighbors[i]:
stack.append([n, i])
used[n] = True
is_tree = True
while stack:
node, parent = stack.popleft()
for n in neighbors[node]:
if n == parent:
continue
if used[n]:
is_tree = False
continue
stack.append([n, node])
used[n] = True
if is_tree:
ret += 1
print(ret)
if __name__ == "__main__":
N, M = map(int, input().split())
neighbors = [[] for _ in range(N + 1)]
for _ in range(M):
u, v = map(int, input().split())
neighbors[u].append(v)
neighbors[v].append(u)
solve()
C問題
005 - 器物損壊！高橋君
コード1. BFS
$time: O(HW)$
$space: O(HW)$
from collections import deque
def solve():
stack = deque()
stack.append([(si, sj), 0])
cost_matrix = [[float('inf') for _ in range(W)] for _ in range(H)]
cost_matrix[si][sj] = 0
while stack:
(i, j), cost = stack.popleft()
for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if not 0 <= x < H or not 0 <= y < W or 2 < cost:
continue
if c[x][y] == 'g':
cost_matrix[x][y] = min(cost_matrix[x][y], cost)
if c[x][y] == '#' and cost + 1 < cost_matrix[x][y] and cost + 1 <= 2:
stack.append([(x, y), cost + 1])
cost_matrix[x][y] = cost + 1
if c[x][y] == '.' and cost < cost_matrix[x][y]:
stack.append([(x, y), cost])
cost_matrix[x][y] = cost
print('YES' if cost_matrix[gi][gj] <= 2 else 'NO')
if __name__ == "__main__":
H, W = map(int, input().split())
c = []
si, sj = 0, 0
gi, gj = 0, 0
for i in range(H):
tmp = list(input())
if 's' in tmp:
si, sj = i, tmp.index('s')
if 'g' in tmp:
gi, gj = i, tmp.index('g')
c.append(tmp)
solve()
006 - 積み重ね
コード1. 貪欲法
$time: O(N)$
$space: O(N)$
def solve():
base_ws = [0 for _ in range(N)]
for w in W:
for idx, bw in enumerate(base_ws):
if w <= bw or bw == 0:
base_ws[idx] = w
break
print(N - base_ws.count(0))
if __name__ == "__main__":
N = int(input())
W = []
for _ in range(N):
W.append(int(input()))
solve()
AGC
A問題
033 - Darker and Darker
コード1. BFS
$time: O(HW)$
$space: O(HW)$
from collections import deque
def solve():
max_cost = 0
stack = deque()
used = [[False for _ in range(W)] for _ in range(H)]
for i in range(H):
for j in range(W):
if A[i][j] == '.':
continue
stack.append([(i, j), 0])
used[i][j] = True
while stack:
(i, j), cost = stack.popleft()
max_cost = max(max_cost, cost)
for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
if not 0 <= x < H or not 0 <= y < W or used[x][y]:
continue
stack.append([(x, y), cost + 1])
used[x][y] = True
print(max_cost)
if __name__ == "__main__":
H, W = map(int, input().split())
A = []
for _ in range(H):
A.append(list(input()))
solve()
038 - 01 Matrix
コード1. 考察
$time: O(HW)$
$space: O(HW)$
def solve():
for row in range(H):
for col in range(W):
if (row < B and col < A) or (B <= row and A <= col):
print(0, end='')
else:
print(1, end='')
print()
if __name__ == "__main__":
H, W, A, B = map(int, input().split())
solve()
043 - Range Flip Find Route
コード1. DP
実装よりは考察が大変でした。
$time: O(HW)$
$space: O(HW)$
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))
B問題
003 - Simplified mahjong
コード1. 貪欲法
$time: O(N)$
$space: O(1)$
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))
その他
B問題
キーエンスプログラミングコンテスト2020 - Robot Arms
コード1. 区間スケジューリング
$time: O(N)$
$sapce: O(1)$
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))
第二回全国統一プログラミング王決定戦予選
コード1. 数え上げ
$time: O(N)$
$sapce: O(N)$
MOD = 998244353
def solve():
if D[0] != 0 or 0 in D[1:]:
print(0)
return
tree_dict = dict()
max_dist = 0
for idx, dist in enumerate(D):
tree_dict[dist] = tree_dict.get(dist, 0) + 1
max_dist = max(max_dist, dist)
ret = 1
for dist in range(max_dist + 1):
if not dist in tree_dict:
print(0)
return
ret = (ret * pow(tree_dict.get(dist - 1, 1), tree_dict[dist])) % MOD
print(ret)
if __name__ == "__main__":
N = int(input())
D = list(map(int, input().split()))
solve()
C問題
SoundHound Inc. Programming Contest 2018 - Ordinary Beauty
僕にとっては全くの初見知識が問われていました。$d = 1$での$O(m)$の解法は思いつくも、そこから一般化して高速化出来なかったです。
コード1. 期待値の線形性
「期待値の線型性」についての解説と、それを用いる問題のまとめ
$time: O(1)$
$sapce: O(1)$
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))
DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 - Strawberry Cakes
実装かなり悩みました。
コード1. イテレート
$time: O(HW)$
$sapce: O(HW)$
import numpy as np
def solve():
ret = np.array([[1 for _ in range(W)] for _ in range(H)])
row_groups = np.array([0 for _ in range(H)])
row_group_set = set()
prev_row = 0
for row in range(H):
if '#' in s[row]:
row_groups[prev_row: row + 1] = row
row_group_set.add(row)
prev_row = row + 1
row_groups[prev_row: ] = prev_row - 1
cur_group_num = 1
for row in row_group_set:
prev_col = 0
for col in range(W):
if s[row][col] == '#':
ret[row][prev_col: col + 1] = cur_group_num
cur_group_num += 1
prev_col = col + 1
ret[row][prev_col: ] = cur_group_num - 1
for row, row_group_num in enumerate(row_groups):
if row in row_group_set:
continue
for col in range(W):
ret[row][col] = ret[row_group_num][col]
for row in ret:
print(' '.join(map(str, row.tolist())))
if __name__ == "__main__":
H, W, K = map(int, input().split())
s = []
for row in range(H):
s.append(list(input()))
solve()
D問題
三井住友信託銀行プログラミングコンテスト2019 - Lucky PIN
コード1. イテレート ＋ 辞書
$time: O(100\ N)$
$sapce: O(100\ N)$
$100\ N \leq 3\times 10^6$
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))
パナソニックプログラミングコンテスト2020 - String Equivalence
コード1. DFS
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"))
E問題 - Colorful Hats 2
三井住友信託銀行プログラミングコンテスト2019
コード1. イテレート
$time: O(N)$
$space: O(N)$
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))