【AtCoder】ABC288 のA,B,C における Python解説

ABC 288のA,B,C 問題を解くために考えたこと、ACできるPython3(PyPy3)コードを紹介します。


この記事は @u2dayo さんの記事を参考にしています。見たことのない方はそちらもご覧ください。とても勉強になります。

また、問題の難易度を表す指標を [Atcoder Problems](https://kenkoooo.com/atcoder/#/table/tsuru1471) から引用しています。このサイトは勉強した問題を管理するのにとてもオススメです。

質問やご指摘はこちらまで
Twitter : [Waaa1471](https://twitter.com/Waaaa1471)

作者プロフィール
Atcoder ：[緑 910](https://atcoder.jp/users/tsuru1471) 
230204 現在

# 目次
[はじめに](#はじめに)
[A.Many A+B Problems](#amany-ab-problems)
[B.Qualification Contest](#bqualification-contest)
[C.Don’t be cycle](#cdont-be-cycle)


## はじめに

特にC問題以降になると、競技プログラミングに典型的な前提知識、少し難しい数学的考察が必要になり始めます。
しかし、公式解説ではこの部分の解説があっさりしすぎていて競技プログラミング(Atcoder)を始めたばかりの人にはわかりにくい、難しいと感じるのではないでしょうか。

またC++がわからないと、コードの書き方を勉強することが難しいです。一応、参加者全員のコードを見ること自体は可能ですが、提出コードは必ずしも教育的ではありません(ここで紹介する記事も本番で提出したものとは全く異なります)。そんなものから初学者が解説もなしになにか得ることはとても難しいと思います。実際適当に何人かのコードをみたものの、意味がわからずに終わった経験があるのではないでしょうか。

この記事がそんな方々の勉強の助けになればよいなと思っています。



# A.Many A+B Problems
[問題](https://atcoder.jp/contests/abc288/tasks/abc288_a)

難易度： 灰色 6

# 考察

適切に入力を受け取り、クエリごとに和をとるだけです。

# コード   
pypy3
93 ms /2000 ms

```php
N=int(input())
for _ in range(N):
    a,b=[int(ab) for ab in input().split()]
    print(a+b)
```


# 補足 

- 入力形式
 [初心者向けAtcoder標準入力セット(Python)](https://qiita.com/jamjamjam/items/e066b8c7bc85487c0785)


# B.Qualification Contest

[問題](https://atcoder.jp/contests/abc288/editorial)

難易度：灰色 44

# 考察

1: 上位K人のハンドルネームの管理 
2: ハンドルネームを辞書順に並び替え

以上 2つの処理を行えるか問われています。

### 上位K人のハンドルネームの管理 
入力で K個までしか受け取らない方法もありますが、ここでは入力を順番にリストに格納した後、スライスして K番目以降を捨てることにします。

### ハンドルネームを辞書順に並び替え
python では辞書順の並び替えは **soretd()** で簡単に実行できます。


# コード
pypy3
63 ms /200 ms
```php
N,K=[int(nk) for nk in input().split()]
S=[]
for _ in range(N):
    s=input()
    S.append(s)

for s in sorted(S[:K]):
    print(s)
```

## 補足
- スライス
[Pythonのスライスによるリストや文字列の部分選択・代入](https://note.nkmk.me/python-slice-usage/)

- sorted()
[Pythonでリストをソートするsortとsortedの違い](https://note.nkmk.me/python-list-sort-sorted/)

# C.Don’t be cycle

[問題](https://atcoder.jp/contests/abc288/tasks/abc288_c)

難易度 ： <font color="brown">茶色 436 </font>



# 考察

まず、**グラフは破壊よりも構築する方が簡単です。** 
この事実に基づくと、**閉路を持たないようにグラフを構築した場合に、いくつの辺を無視したか** を求める問題であると解釈することができます。

閉路を検出しながらグラフを構築するには **Union-Find**が適しています。頂点 $Ai$ , $Bi$ を結ぶ前に、これらが既に同じ連結成分であればこの辺を採用すべきでない(無視する)と判断できます。もし採用してしまうと、閉路を成してしまうからです。

## コード
pypy3
535 ms /2000 ms
### メイン
```php

ここに Union-Find クラスを書く

if __name__ =="__main__":
    N,M=[int(nm) for nm in input().split()]
    uf=UnionFind(N)
    ans=0
    for _ in range(M):
        a,b=[int(ab)-1 for ab in input().split()]
        # 閉路を成すか判定
        if uf.same(a,b):
            ans+=1
        
        uf.union(a,b)
    
    print(ans)


```
### Union-Find クラス
```php
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 same(self,x,y):
        return self.find(x) == self.find(y)

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

# 補足

- 類題
[218E Destruction](https://atcoder.jp/contests/abc218/tasks/abc218_e)

- Union-Find
[PythonでのUnion-Find（素集合データ構造）の実装と使い方](https://note.nkmk.me/python-union-find/)
コードの Union-Find クラスはほとんどこの記事をパクっています。解説もわかりやすいので、ご覧ください
    [B - Union Find](https://atcoder.jp/contests/atc001/tasks/unionfind_a)
スライドがとても分かりやすいです。視覚的な理解ができるのでこちらも併せてオススメしています。


# 終わり

D 問題解けな過ぎワロタ