ABC264 回想・解説(Python)
目次
総括
ooooxxxx
A-Dの4完。
E問題のUFに気づくことはできましたが、先読みと発電所をまとめる工夫ができずタイムアップ。
A. "atcoder".substr()
word = "atcoder"
L, R = map(int, input().split())
print(word[L - 1 : R])
B. Nice Grid
gridを再現して回答。ただ、それに時間を使うぐらいだったらベタうちしたほうが早かった...
公式解説を見ると、中心からの距離で判定していた。なるほど。
R, C = map(int, input().split())
grid = [["black"] * 15 for _ in range(15)]
c = "white"
cnt = 1
while cnt < 14:
for i in range(cnt, 15 - cnt):
for j in range(cnt, 15 - cnt):
grid[i][j] = c
cnt += 1
c = "white" if c == "black" else "black"
print(grid[R - 1][C - 1])
C. Matrix Reducing
行列Aの行または列を任意に削除して、行列Bと一致するかという問題。
行列Aの行または列を任意に選択して、行列Bに一致させられるかという問題に読み替えることができる（制約的にも実行時間は変わらない）。
行列Bの行数と列数を行列Aから選択する組み合わせを全パターン確認して、一致するかどうか判定する。
from itertools import combinations
H1, W1 = map(int, input().split())
A1 = [list(input().split()) for _ in range(H1)]
H2, W2 = map(int, input().split())
A2 = [list(input().split()) for _ in range(H2)]
for i in combinations(range(H1), H2): # 残す行の組み合わせ
for j in combinations(range(W1), W2): # 残す列の組み合わせ
tmp = [[-1] * W2 for _ in range(H2)]
for h_i, k in enumerate(i):
for w_i, l in enumerate(j):
tmp[h_i][w_i] = A1[k][l]
if tmp == A2:
print("Yes")
exit()
print("No")
D. "redocta".swap(i,i+1)
バブルソートを実装する。愚直に実装していくだけ。
S = list(input())
word = "atcoder"
cnt = 0
for i, w in enumerate(word):
idx = S.index(w)
for j in range(idx, i, -1):
S[j], S[j - 1] = S[j - 1], S[j]
cnt += abs(i - idx)
print(cnt)
E. Blackout 2
本番中は
- 発電所につながっているかどうかをどう持たせるか
- 電線を切る、という行為とそのあとの状態をどう持つか
に悩んで回答できなかった。
queryを先に読んでおいて、最後まで切れない電線を繋いだ状態を初期状態としておく。そしてqueryを逆から読んでいき電線を繋いでいく≒簡単にいうと逆再生。そのときに発電所につながっている都市の数を保持しておき、最後に出力したらいい。
そして、逆から電線を繋いでいく場合はどの発電所に繋がっているかに依らないので、発電所はすべてNにしてしまうと、繋がっている都市が数えやすい。uf.size(N)で発電所Nに繋がっている地点の数。そこから発電所Nの1箇所を引くことで簡単に算出できる。
class UnionFind:
"""Union Find木クラス
Attributes:
parent (list): 親要素を格納するリスト。親要素は自身のサイズを格納する。
Notes:
- parent[i] < 0 の場合、iは根。この時、-parent[i]はそのグループのサイズ
- parent[i] = -1 とすると、iは独立。
"""
def __init__(self, n):
"""
Args:
n (int): The number of objects. 要素数
"""
self.n = n
self.parents = [-1] * n
def find(self, x):
"""returns the root of x
Args:
x (int): The object to find the root of. 要素
Returns:
int: The root of x.
"""
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y):
"""unites the root of x and the root of y
Args:
x (int): The first object to union. 要素
y (int): The second object to union. 要素
"""
x = self.find(x)
y = self.find(y)
if x == y: # すでに同じ親
return
# union by size
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def size(self, x):
"""returns the size of the group of x
Args:
x (int): The object to find the size of. 要素
Returns:
int: The size of the group of x.
"""
return -self.parents[self.find(x)]
def same(self, x, y):
"""returns True if the root of x is the same as the root of y
Args:
x (int): The first object to check. 要素
y (int): The second object to check. 要素
Returns:
bool: True if the root of x is the same as the root of y.
"""
return self.find(x) == self.find(y)
def members(self, x):
"""returns the members of the group of x
Args:
x (int): The object to find the members of. 要素
Returns:
list: The members of the group of x.
"""
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def roots(self):
"""returns the roots
Returns:
list: The roots.
"""
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
"""returns the number of groups
Returns:
int: The number of groups.
"""
return len(self.roots())
def all_group_members(self):
"""returns all groups
Returns:
list: All group members.
"""
return {r: self.members(r) for r in self.roots()}
def int1(x: int) -> int:
return int(x) - 1
N, M, E = map(int, input().split())
uf = UnionFind(N + 1)
e = []
for i in range(E):
u, v = map(int1, input().split())
e.append((min(u, N), min(v, N)))
Q = int(input())
x = []
for i in range(Q):
x.append(int1(input()))
# 最後まで切れない電線で地点を結ぶ
for i in set(range(E)) - set(x):
u, v = e[i]
uf.union(u, v)
# queryを逆読みして、電線を順に繋いで電気の通る都市の数を格納
ans = [uf.size(N) - 1]
for i in reversed(x):
u, v = e[i]
uf.union(u, v)
ans.append(uf.size(N) - 1)
print(*reversed(ans[:-1]), sep="\n")