😎

# AtCoder ABC229 個人的メモ

2021/11/28に公開

## A - First Grid

↑と同じ

``````#.   |   .#
.#   |   #.
``````
``````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

``````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が既に連結なら、この辺によってグラフの連結成分の個数は変化しない