🐡

2022/04/01に公開

# A - Weather Forecast

``````import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
n = int(input())
s = input()
print('Yes' if s[n-1]=='o' else 'No')

if __name__ == '__main__':
main()
``````

# B - qwerty

``````import sys
import heapq, math, itertools
from collections import defaultdict, deque
from string import ascii_lowercase
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
p = list(map(int, inputs().split()))
idx = {i+1:c for i,c in enumerate(ascii_lowercase)}
ans = ''
for x in p:
ans += idx[x]
print(ans)

if __name__ == '__main__':
main()
``````

string.ascii_lowercaseで'a'~'z'の文字列が獲得できるので、覚えておくと何かと便利です。

# C - Shapes

``````import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def left_rotation(mat):
ret = []
mat_s = list(zip(*mat))
for x in mat_s[::-1]:
ret.append(''.join(x))
return ret

def del_outlines(mat):
for i in range(4):
mat = left_rotation(mat)
flg = True
nxt = []
for line in mat:
if set(line)=={'.'} and flg:
continue
else:
nxt.append(line)
flg = False
mat = nxt
return mat

def main():
n = int(input())
s = [input() for _ in range(n)]
t = [input() for _ in range(n)]
s = del_outlines(s)
t = del_outlines(t)
flg = False
for i in range(4):
s = left_rotation(s)
if s==t:
flg = True
print('Yes' if flg else 'No')

if __name__ == '__main__':
main()
``````

• 90度回転 -> 行列の回転
• 並行移動 -> 要するに'#'の部分の位置関係が対応すればよい

これらのことを考えると、

• 処理１：各グリッドの外枠'.'を削除する
• 処理２：90度回転により一致するかを判定

という流れで解決できます。

# D - Rectangles

``````from re import L
import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
n = int(input())
idx = defaultdict(list)
for _ in range(n):
x,y = map(int, input().split())
idx[x].append(y)
ans = 0
for k1,v1 in idx.items():
for k2,v2 in idx.items():
if k1==k2:
continue
l = len(set(v1)&set(v2))
ans += l*(l-1)//2
print(ans//2)

if __name__ == '__main__':
main()
``````

これによって各x座標におけるy座標の点間の組み合わせの総数を考えればよいです。

# E - Destruction

``````import sys
import heapq, math, itertools
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

class UnionFind:
"""
n : 要素数
root : 親ノード
size : グループのサイズ
"""

def __init__(self, n):
self.n = n
self.root = [-1]*(n+1)
self.size = [1]*(n+1)

"""ノードxのrootノードを見つける"""
def Find_Root(self, x):
if self.root[x] < 0:
return x
else:
self.root[x] = self.Find_Root(self.root[x])
return self.root[x]

"""木の合併"""
def Union(self, x, y):
#入力ノードの親を探索
x = self.Find_Root(x)
y = self.Find_Root(y)

#既に同じ木に所属する場合
if x==y:
return

#異なる木に所属する場合 -> sizeが小さい方から大きい方に合併する
elif self.size[x] > self.size[y]:
self.size[x] += self.size[y]
self.root[y] = x

else:
self.size[y] += self.size[x]
self.root[x] = y

"""xとyが同じグループに所属するか"""
#　辺(x,y)が橋の場合
#   ⇒(x,y)以外をUnionしたとき、isSameGroup(self, x, y)=False

def isSameGroup(self, x, y):
return self.Find_Root(x) == self.Find_Root(y)

""" 頂点数を数える"""
#全連結成分にするために必要な橋の本数は、cnt - 1
def Count_Vertex(self):
cnt = 0
for i in range(self.n):
if self.root[i+1] < 0:
cnt += 1
return cnt

""" xが属する集合に含まれる全ノードを返す """
def Members(self, x):
r = self.Find_Root(x)
return [i for i in range(self.n+1) if self.Find_Root(i) == r]

"""xが属する集合のサイズ"""
def Size(self, x):
return self.size[self.Find_Root(x)]

def main():
n,m = map(int, inputs().split())
v = [list(map(int, inputs().split())) for _ in range(m)]
v = sorted(v, key=lambda x:x[2])
uf = UnionFind(n)
ans = 0
for a,b,c in v:
if uf.isSameGroup(a,b):
ans += max(0, c)
else:
uf.Union(a,b)
print(ans)

if __name__ == '__main__':
main()
``````

これを言い換えると、「与えられたM辺のうち、なるべく小さいコストを用いてN頂点連結グラフを構成する問題」と解釈することができます。(これと入力との差分が求めるべき値です)
よって各辺のコストでソートした後に、UnionFindによって各辺の頂点が既に連結しているかを見てあげることで、この問題を解くことができます。