😎
AtCoder ABC229 個人的メモ
A - First Grid
↑と同じ
条件を満たさないパターンは以下の2つなので、そのパターンか否かを判別
#. | .#
.# | #.
S1 = input()
S2 = input()
if S1[0] == S2[1] == "." or S1[1] == S2[0] == ".":
print("No")
else:
print("Yes")
B - Hard Calculation
AとBの各桁を足し算して10以上になるかを判別すればおｋ
A, B = input().split()
ans = 0
for i in range(min(len(A), len(B))):
j = i + 1
if int(A[-j]) + int(B[-j]) >= 10:
ans = 1
break
if ans:
print("Hard")
else:
print("Easy")
C - Cheese
チーズは1[g]ずつ載せることができるので、密度が大きいものから使っていけばおｋ
N, W = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(N)]
lst.sort()
weight = 0
value = 0
while weight < W and lst:
a, b = lst.pop()
res = min(W - weight, b)
weight += res
value += a * res
print(value)
D - Longest X
文字列Sの区間[l, r]の"."がK個以下となるr-l+1の最大値を求める。
from itertools import accumulate
S = input()
K = int(input())
N = len(S)
cumsum = list(accumulate((s == "." for s in S), initial=0))
ans = 0
right = 0
for left in range(N):
while right < N and cumsum[right + 1] - cumsum[left] <= K:
right += 1
ans = max(ans, right - left)
print(ans)
E - Graph Destruction
頂点番号の大きい順にグラフに頂点と辺を追加していけばおｋ
union-findの実装
class UnionFind:
"""Union-Find(素集合データ構造(disjoint-set data structure)に対しての操作)"""
def __init__(self, n: int):
"""
Constructer(Initialize parameter in this class)
Parameters
----------
n : int
Number of node
Yields
-----
root : list
When value is postive, express root of the node.
When it is negative, express this node is root and size of set.
"""
self.root = [-1] * n
def find(self, x: int) -> int:
"""
Search root of node x
Parameters
----------
x : int
node x
Returns
-------
x : int
Root of node x
"""
if self.root[x] < 0:
return x
self.root[x] = self.find(self.root[x])
return self.root[x]
def unite(self, x: int, y: int) -> bool:
"""
Unite two set including node x and node y into one set.
Parameters
----------
x, y : int
Node number
Returns
-------
unite_result : bool
False : Already two node include same set.
True : United
"""
x = self.find(x)
y = self.find(y)
if x == y:
return False
if self.root[x] > self.root[y]:
x, y = y, x
self.root[x] += self.root[y]
self.root[y] = x
return True
def is_same(self, x: int, y: int) -> bool:
"""
Determine if x and y are in same set.
Parameters
----------
x, y : int
Node number
Returns
-------
result : bool
Determining result
"""
return self.find(x) == self.find(y)
def size(self, x: int) -> int:
"""
Return size of set including node x.
Parameters
----------
x : int
Node number
Returns
-------
Size of set : int
"""
return self.root[self.find(x)] * -1
N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
x, y = map(lambda n: int(n) - 1, input().split())
# x < yとなるようにする
if x > y:
x, y = y, x
edge[x].append(y)
union = UnionFind(N)
ans = [0] * (N)
for i in range(N - 2, -1, -1):
# 頂点i+1が追加され連結成分が1つ増える(まだ頂点i+1に辺が追加されていない)
ans[i] = ans[i + 1] + 1
# 頂点i+1と既にグラフに追加されている頂点j(i<j)を結ぶ辺を追加する
for adjacent_node in edge[i + 1]:
# 頂点i+1と頂点n_nodeが既に連結なら、この辺によってグラフの連結成分の個数は変化しない
if union.is_same(i + 1, adjacent_node):
continue
# そうでないならば、連結成分が1つ減る
union.unite(i + 1, adjacent_node)
ans[i] -= 1
print(*ans, sep="\n")
Discussion