

# AtCoder Beginner Contest 218
https://atcoder.jp/contests/abc218

ABC218の問題を、本番で自分が解けた所＋1問の解説です。  
初めて色がついたので投稿してみました。  
茶色を維持しつつ、次は水色を目指したい。
![](https://cdn.apollon.ai/media/notebox/userimages/45a38cbe-78a8-4c7f-aa43-ebd78fd4999d.png)

# A - Weather Forecast
https://atcoder.jp/contests/abc218/tasks/abc218_a

## 文字列のスライス
* $S[i]$で、$i+1$文字目が抽出できる
* 0indexなので注意
* 後はif文で条件に従ってあげる。



```python
N = int(input())
S = input()
 
if S[N-1] == 'o':
    print('Yes')
else:
    print('No')
```

# B - qwerty
https://atcoder.jp/contests/abc218/tasks/abc218_b

## 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で当ててあげれば良いね



```python
#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)
```


```python
# after
L = list(map(int,input().split()))
ans = ''
for i in L:
    ans += chr(96 + i)
print(ans)
```

# C - Shapes
https://atcoder.jp/contests/abc218/tasks/abc218_c

## 平行移動の話

* 回転が不要な状態で、図形Sを平行移動を繰り返した時に図形Tと一致するか否かを考える
* 縦横に並行移動する必要がある？
    * グリッド上にあるS、Tの場所がズレているなら、平行移動する必要がある
        * 場所がズレている＝図形S、Tの上下左右に存在する、'#'の含まれていない行の数が異なっている
    * つまり、図形S、Tの上下左右に存在する、'#'の含まれていない行を全て削れば図形は一致する筈

## 回転の話
* numpyのrot90でかんたんに90度回転できる


```python
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
https://atcoder.jp/contests/abc218/tasks/abc218_d

## 長方形を一意に定めるには
* 左下の頂点と、右下の頂点を決めると長方形が一意に定まる。
* 条件より、2000個のうちから2つの組み合わせで全探索


```python
# 入力部
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 
https://atcoder.jp/contests/abc218/tasks/abc218_e

## 考え方
1. 先に道を全部外してプラスの報酬を全て受け取る
2. 報酬がマイナスの道に関してはとりあえず繋ぐ
3. 報酬がプラスの道を、報酬が小さい順（昇順）に並び替える
4. まだ繋いでない（報酬がプラス）道の、一番報酬が小さい道を取り上げる。
    * Q:道の両端の地点は既に繋がっている？
        * 繋がっている場合→繋ぐ必要が無いので、報酬はそのまま（貰ったまま）
        * 繋がっていない場合→繋ぐ必要があるので、報酬を返却して道を繋ぐ

## UnionFind木
https://www.slideshare.net/chokudai/union-find-49066733/1
* 行程4の、「グラフの2点が繋がっているか？」の判定と、「グラフの2点を繋ぐ」を速く行うためのデータ構造
* O(log n)らしい。


```python
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)
```


AtCoder Beginner Contest 218
https://atcoder.jp/contests/abc218
ABC218の問題を、本番で自分が解けた所＋1問の解説です。
初めて色が

ABC218 茶色コーダーが解けた所まで＋あと1問

AtCoder Beginner Contest 218

A - Weather Forecast

文字列のスライス

B - qwerty

chr関数

C - Shapes

平行移動の話

回転の話

D - Rectangles

長方形を一意に定めるには

E - Destruction

考え方

UnionFind木

Discussion

コメントにはログインが必要です。