・7 min read
ABC218 茶色コーダーが解けた所まで＋あと1問
AtCoder Beginner Contest 218
ABC218の問題を、本番で自分が解けた所＋1問の解説です。
初めて色がついたので投稿してみました。
茶色を維持しつつ、次は水色を目指したい。
初めて色がついたので投稿してみました。
茶色を維持しつつ、次は水色を目指したい。
A - Weather Forecast
文字列のスライス
- で、文字目が抽出できる
- 0indexなので注意
- 後はif文で条件に従ってあげる。
N = int(input())
S = input()
if S[N-1] == 'o':
print('Yes')
else:
print('No')B - qwerty
chr関数
- 数字→文字列はchr関数でこなすとお洒落
- chr(i)で、Unicodeコードポイントである文字が文字列strで返される
- 反対向きの変換はord(s)
- https://note.nkmk.me/python-chr-ord-unicode-code-point/
- 'a'はchr(97)
- chr(96 + i)で、iを1~26で当ててあげれば良いね
#before
L = list(map(int,input().split()))
base_l = ['a']
base_l.append('b')
base_l.append('c')
base_l.append('d')
base_l.append('e')
base_l.append('f')
base_l.append('g')
base_l.append('h')
base_l.append('i')
base_l.append('j')
base_l.append('k')
base_l.append('l')
base_l.append('m')
base_l.append('n')
base_l.append('o')
base_l.append('p')
base_l.append('q')
base_l.append('r')
base_l.append('s')
base_l.append('t')
base_l.append('u')
base_l.append('v')
base_l.append('w')
base_l.append('x')
base_l.append('y')
base_l.append('z')
ans = ''
for i in L:
ans += base_l[i-1]
print(ans)# after
L = list(map(int,input().split()))
ans = ''
for i in L:
ans += chr(96 + i)
print(ans)C - Shapes
平行移動の話
- 回転が不要な状態で、図形Sを平行移動を繰り返した時に図形Tと一致するか否かを考える
- 縦横に並行移動する必要がある？
- グリッド上にあるS、Tの場所がズレているなら、平行移動する必要がある
- 場所がズレている＝図形S、Tの上下左右に存在する、'#'の含まれていない行の数が異なっている
- つまり、図形S、Tの上下左右に存在する、'#'の含まれていない行を全て削れば図形は一致する筈
- グリッド上にあるS、Tの場所がズレているなら、平行移動する必要がある
回転の話
- numpyのrot90でかんたんに90度回転できる
import numpy as np
# 入力
N = int(input())
# Sの入力
S_l = []
for i in range(N):
tmp = input()
S_l.append(list(tmp))
S_array = np.array(S_l)
# Tの入力
T_l = []
for i in range(N):
tmp = input()
T_l.append(list(tmp))
T_array = np.array(T_l)
# S,Tどちらも上から使ってない行を削除する。削除が終わったら90度回転して、また上から削除。
for i in range(4):
for i in range(N): # S削除パート
if '#' in S_array[0]:
break
S_array = np.delete(S_array, 0, 0)
S_array = np.rot90(S_array) # Sを90度回転
for i in range(N): # T削除パート
if '#' in T_array[0]:
break
T_array = np.delete(T_array, 0, 0)
T_array = np.rot90(T_array) # Tを90度回転
# 最終的にSとTを一番小さくした形（使ってない行、列を削りきった状態）で、片方を回転させて同じ形か確かめる
for i in range(4):
if S_array.shape == T_array.shape: # もし行、列の数が一緒で…
if (S_array == T_array).all(): # 同じ形なら終わり
print('Yes')
exit()
S_array = np.rot90(S_array) # 違うなら回転させてみる
print('No') # ダメでした！D - Rectangles
長方形を一意に定めるには
- 左下の頂点と、右下の頂点を決めると長方形が一意に定まる。
- 条件より、2000個のうちから2つの組み合わせで全探索
# 入力部
N = int(input())
L = []
S = set()
ans = 0
for i in range(N):
x, y = map(int, input().split())
L.append([x, y])
S.add((x, y)) # 点が存在するか否かの確認用にsetを作る
for i in range(N-1):
for j in range(i+1, N):
x1, y1 = L[i]
x2, y2 = L[j]
if x1 != x2 and y1 != y2: # 選択した2点が水平or垂直に並んでる場合、長方形はできないのでパス
point3 = (x1, y2)
point4 = (x2, y1)
if (point3 in S) and (point4 in S):
ans += 1
print(int(ans/2)) # 左下と右上で長方形を確定させるパターンと、左上と右下で長方形を確定させるパターンが存在するため最終結果を2で割るE - Destruction
考え方
- 先に道を全部外してプラスの報酬を全て受け取る
- 報酬がマイナスの道に関してはとりあえず繋ぐ
- 報酬がプラスの道を、報酬が小さい順（昇順）に並び替える
- まだ繋いでない（報酬がプラス）道の、一番報酬が小さい道を取り上げる。
- Q:道の両端の地点は既に繋がっている？
- 繋がっている場合→繋ぐ必要が無いので、報酬はそのまま（貰ったまま）
- 繋がっていない場合→繋ぐ必要があるので、報酬を返却して道を繋ぐ
- Q:道の両端の地点は既に繋がっている？
UnionFind木
- 行程4の、「グラフの2点が繋がっているか？」の判定と、「グラフの2点を繋ぐ」を速く行うためのデータ構造
- O(log n)らしい。
N, M = map(int, input().split())
L = []
ans = 0
for i in range(M):
A, B, C = map(int, input().split())
L.append([C, A, B])
if C > 0:
ans += C
class UnionFind:
def __init__(self, n):
self.n = n
self.parent_size = [-1]*n
def leader(self, a):
if self.parent_size[a] < 0:
return a
self.parent_size[a] = self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self, a, b):
x, y = self.leader(a), self.leader(b)
if x == y:
return
if abs(self.parent_size[x]) < abs(self.parent_size[y]):
x, y = y, x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y] = x
return
def same(self, a, b):
return self.leader(a) == self.leader(b)
def size(self, a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result = [[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
L.sort()
uf = UnionFind(N+1)
for c, a, b in L:
if c <= 0:
uf.merge(a, b)
continue
if not uf.same(a, b):
ans -= c
uf.merge(a,b)
print(ans)
