【AtCoder】ABC218をPython3で解説（ABCDE）

ABC218のA-E問題の解説。

https://atcoder.jp/contests/abc218

## 目次
[A - Weather Forecast](#a---weather-forecast)
[B - qwerty](#b---qwerty)
[C - Shapes](#c---shapes)
[D - Rectangles](#d---rectangles)
[E - Destruction](#e---destruction)

## A - Weather Forecast

https://atcoder.jp/contests/abc218/tasks/abc218_a

### 解説

$N$日後の天気予報が晴れ、つまり、`o`かどうかを判定する問題。
$S$の$N-1$文字目が`o`だったら`Yes`。

### コード
```python
def main():
    n = int(input())
    s = input()

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

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

## B - qwerty

https://atcoder.jp/contests/abc218/tasks/abc218_b

### 解説

`P`の入力に対して、対応する英小文字をつなげていくという問題。

数字を文字列に変換するときは、`chr()`を用いる。`chr(97)`が`a`にあたるので、$+96$して文字を連結してあげれば良い。

### コード
```python
def main():
    plist = list(map(int, input().split()))
    s = ''

    for p in plist:
        s += chr(p+96)

    print(s)

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

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

### 解説

$S$のグリッドの中で、$T$の`#`でつくられた形があるかどうかを判定する問題。

まずは、`S`と`T`の`#`の数が等しいかをみる。そもそも`#`の数が等しくなければ、この2つを一致させることができない。

一致していれば、ループに入る。
記録したsの`#`の座標をもとに、tの座標をひとつずつみていく。
一致しなかった場合は、ただちにループを抜けることで計算量を削減できる。

また、一致しなかった場合は、sの座標自体を90度回転させ、同じように`#`の位置を見ていく。

### コード
```python
def main():
    n = int(input())
    s = list(list(input()) for _ in range(n))
    t = list(list(input()) for _ in range(n))

    # sの'#'の座標を記録
    slist = list((i, j) for i in range(n) for j in range(n) if s[i][j] == '#')
    # tの'#'の数を記録
    tcnt = sum(1 for i in range(n) for j in range(n) if t[i][j] == '#')

    # '#'の数が合うかを確認し、あっていなければ'No'
    if len(slist) != tcnt:
        print("No")
        exit()

    # 90度x3回分回す
    for _ in range(4):
        for i in range(-n+1, n):
            for j in range(-n+1, n):
                flag = True
                for x, y in slist:
                    if not (0 <= x+i < n and 0 <= y+j < n and t[x+i][y+j] == '#'):
                        flag = False
                        break

                if flag:
                    print("Yes")
                    exit()
        # 90度回転
        slist = [(y, n-1-x) for x, y in slist]

    print("No")


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

## D - Rectangles

https://atcoder.jp/contests/abc218/tasks/abc218_d

### 解説

$2$次元平面上にある$N$個の点のうちから4つを選んで、何個の長方形が作れるかという問題。

まず`x`を固定して、それに対応する`y`を配列に保存する。つまり、各`x`がもつ`y`を配列として保存する。

それら`x`を2つずつみていき、その`x_i, x_j`がもつyの個数が2以上の場合は、`x_i, x_j`の共通するyを見つける。それらから2つをとった組み合わせの個数を数えてあげると、`x_i, x_j`との長方形の数がわかるので、これを足していったものが答え。


### コード
```python

def main():
    from itertools import combinations

    n = int(input())
    d = dict()

    for _ in range(n):
        x, y = map(int, input().split())
        if x not in d:
            d[x] = [y]
        else:
            d[x].append(y)

    # xの座標
    xaxis = [k for k in d.keys()]

    cnt = 0

    for i in range(len(xaxis)-1):
        for j in range(i+1, len(xaxis)):
            # そのx_i, x_jがもつyの個数が2以上の場合
            if len(d[xaxis[i]]) >= 2 and len(d[xaxis[j]]) >= 2:
                # x_i, x_jの共通するyを見つける
                test = set(d[xaxis[i]]) & set(d[xaxis[j]])
                # それらの組み合わせの個数を数える
                cnt += len(list(combinations(test, 2)))

    print(cnt)


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

## E - Destruction
https://atcoder.jp/contests/abc218/tasks/abc218_e
### 解説

`N`頂点と`M`辺の連結無向グラフが存在するとき、重みのついた辺を取り除くと、その値に応じて報酬がもらえる。また、重みが負の値であれば、その値の絶対値分の罰金を支払う。

このとき、$0$本以上の辺を取り除き、すべての頂点がつながっている場合に得られる、最大の報酬を求める問題。

先に結論をいってしまうと、これは**最小全域木**を求めるアルゴリズムを用いると解くことができる。

このアルゴリズムには、**プリム法**と**クラスカル法**がある。こちらの仕組みついては解説記事をご覧いただきたい。どちらのアルゴリズムでも最小全域木を求めることにはかわりはない。

そもそも最小全域木というのは、**存在するすべての頂点がつながっていて、辺の重みの総和が最小になるデータ構造のこと**をいう。
この問題で、なぜ最小全域木を求める必要があるのか。それは、**罰金があるすべての辺、または、報酬が小さい辺はできるだけ残しておいた全域木を作成する**必要があるためである。

ここからはコードを使って説明していく。

まず、重み（報酬）が正の値を取るとき、`cost`に値を足し、先にすべての報酬を受けとっておく。これが辺をすべて取り除いた場合の報酬の最大値である。しかし、これではグラフが連結であるという条件を満たしていない。つまり、ここから最小全域木を作成する必要がある。

最小全域木をつくるにあたって、最小全域木の辺の値が負（罰金）の場合、辺を取り除く必要がない、つまり、罰金は取る必要がないため、そのままにしておく。

最小全域木の辺の値が正の場合、先程の操作で`cost`が報酬の最大値なので、報酬を受け取れない分、`cost`から報酬分を引く。

これをすべての辺に対して行うことで、今回の問題の報酬の最大値を求めることができる。

### コード1（プリム法）

プリム法では`heapq（優先度付きキュー）`を用いているが、より詳しく知りたい方はこちらを参考にしていただきたい。

https://qiita.com/uniTM/items/9630ed9d51f62b3e35ab

```python
def main():
    from heapq import heappush, heappop

    n, m = map(int, input().split())

    graph = [[] for _ in range(n)]

    cost = 0

    for _ in range(m):
        u, v, c = map(int, input().split())
        u, v = u-1, v-1
        graph[u].append((v, c))  # u->vの辺
        graph[v].append((u, c))  # v->uの辺
        if c >= 0:
            cost += c

    # プリム法
    # 頂点がマークされているか確認する配列
    marked = [False for _ in range(n)]

    # マークされている頂点数を数える
    marked_cnt = 0

    # はじめに0頂点をマーク
    marked[0] = True
    marked_cnt += 1

    # heap
    q = []

    # 頂点0に隣接する辺を保存
    for j, c in graph[0]:
        heappush(q, (c, j))

    # すべての頂点をマークするまでwhileループ
    while marked_cnt < n:
        # 最小の重みの辺をheapで取り出す
        c, i = heappop(q)

        # マークされているならスキップ
        if marked[i]:
            continue

        # 頂点をマーク
        marked[i] = True
        marked_cnt += 1

        # 罰金でなければ報酬を
        # 受け取りすぎているので報酬分の値を引く
        if c >= 0:
            cost -= c

        # 頂点iに隣接する辺を保存
        for j, c in graph[i]:
            # マークされていればスキップ
            if marked[j]:
                continue

            heappush(q, (c, j))

    print(cost)


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

### コード2（クラスカル法）

クラスカル法では`Union-Find`を用いているが、より詳しく知りたい方はこちらを参考にしていただきたい。

https://qiita.com/uniTM/items/77ef2412e426cae44586

```python
# Union-Find

from collections import defaultdict

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members

    def __str__(self):
        return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

# Code

def main():
    n, m = map(int, input().split())
    uf = UnionFind(n)

    # 辺を保存する配列
    edges = []

    # 報酬、つまり、辺の重みを保存する変数
    cost = 0

    for _ in range(m):
        u, v, c = map(int, input().split())
        u, v = u-1, v-1 # インデックスずらし
        edges.append((c, u, v))
        # c_iが0以上のとき、c_iの報酬を得る
        if c >= 0:
            cost += c

    # 重み（報酬）が小さい順に辺をソート
    edges.sort()

    # できるだけ辺（報酬）をとりたいので、
    # 負（罰金）であるか値が小さい辺（報酬）を残した最小全域木を作りたい
    # （それ以外の辺は報酬として受け取れる）
    for edge in edges:
        c, u, v = edge
        # 罰金なら、それらの頂点をつなげる
        if c <= 0:
            uf.union(u, v)
        else:
            # 頂点がつながっていなければ
            if not uf.same(u, v):
                cost -= c # 報酬を引き
                uf.union(u, v) # 頂点同士をつなげる

    print(cost)


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

## 編集後記

最小全域木結構面白いけど、例題が少ないのが難点。