【AtCoder】ABC226をPython3で解説（ABCD）

ABC226のA-D問題の解説。

https://atcoder.jp/contests/abc226

## 目次
[A - Round decimals](#a---round-decimals)
[B - Counting Arrays](#b---counting-arrays)
[C - Martial artist](#c---martial-aritist)
[D - Telepotation](#d---telepotation)

## A - Round decimals

https://atcoder.jp/contests/abc226/tasks/abc226_a

### 解説

与えられた実数`X`を、小数点第一位で四捨五入して出力する問題。

pythonであれば、`round`など使ってもよいが、今回は条件分岐で説明する。

ある実数`X`は小数点第三位までしかないので、整数部分はスライスして保存しておく。
条件分岐だが`x[-3]`などとして、小数点第一位の値を参照し、その値が5以上であるかどうかを判定する。

もし5以上であれば、保存しておいた整数部分に1を足して出力、5未満であれば、そのまま保存しておいた整数部分を出力してあげるとよい。

### コード
```python
def main():
    x = input()
    before_point = int(x[:-4])

    if int(x[-3]) >= 5:
        print(before_point+1)
    else:
        print(before_point)

if __name__ == '__main__':
    main()
```
## B - Counting Arrays 

https://atcoder.jp/contests/abc226/tasks/abc226_b

### 解説

入力された数列が何種類あるか求める問題。
重複する要素の判定は、`set()`をもちいることで、実装できる。

入力された数列のインデックス番号1以上の配列をスライスして、タプルに置き換える。これを`set()`にいれて、長さを出力したものが答えとなる。

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

    for _ in range(n):
        len_and_arrays = list(map(int, input().split()))
        arrays = tuple(len_and_arrays[1:])
        kind_of_arrays.add(arrays)

    print(len(kind_of_arrays))

if __name__ == '__main__':
    main()
```
## C - Martial artist

https://atcoder.jp/contests/abc226/tasks/abc226_c

### 解説

技$i$を習得するためには、時間$T_i$が必要で、技$A_{i, 1}, A_{i, 2}, ..., A_{i, K_i}$を習得している必要がある。このとき技$N$を取得するために、必要な最小時間を答える問題。

最初の文章だが、例えば入力例1を用いると、技$3$を取るためには、時間$7$が必要で、技$1$を習得している必要がある。

最小の時間をどうやって出すのか。結論、技$N$から逆算して答えれば良い。
入力例2で考えると、技$5$を習得するためには、技$1, 2, 3, 4$の習得が必要である。技$5$を習得する時間は、$1000000000$なので、事前に変数を用意して、値を足しておく。残りは技$1, 2, 3, 4$の習得が必要なので、このなかから値を一つ取り出し、技$5$でやったことと同じことを繰り返す。
こうして、習得する必要のある技がなくなるまで繰り返すことで、それまでにかかった合計時間がわかるので、これを出力すればよい。

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

    techs = []

    for _ in range(n):
        tech = list(map(int, input().split()))
        techs.append(tech)

    nxt = techs[-1][2:] # 次に調べる技
    time = techs[-1][0] # 必要な合計時間
    get_tech = set() # 習得した技

    while nxt: # 習得する必要がある技がなくなるまで
        now_tech = nxt.pop() - 1
        if now_tech not in get_tech: # まだ習得していない技であれば
            get_tech.add(now_tech) # 技を習得済みに
            time += techs[now_tech][0] # 習得する時間を足す
            nxt.extend(techs[now_tech][2:]) # 習得する必要のある技を配列として追加
    
    print(time) # 必要な合計時間を出力

if __name__ == '__main__':
    main()
```
## D - Teleportation

https://atcoder.jp/contests/abc226/tasks/abc226_d

### 解説

街$i$から街$j$に移動するとき、街$i$の位置に、`(a, b)`をそれぞれ足してあげることで移動できる。また、他の街同士で移動するとき`(a, b)`を複数回足して移動しても良い。ただし、移動する際の`(a, b)`は1種類のみしか使ってはならない。このとき、すべての街同士を移動できる`(a,b)`の数を数えるという問題。

例では、街1から街2まで`(a,b)=(1,2)`で移動できる。

![IMG_0762.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/9f4605ee-32c7-b5cb-6162-a9b88f8b2235.jpeg)

考えたいのが、2枚目の例である。このように街3から街4、街4から街5は、`(a,b)=(1,1)`で移動できる。街3から街5は、`(a,b)=(2,2)`で移動できるが、これは`(a,b)=(1,1)`を2回もちいても移動できる。つまり、`a, b`の最大公約数で互いを割ることで、最小の移動手段を求めることができる。

![IMG_0763.jpeg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/716184/c1c93b6a-e6c0-c4df-ebf8-bada376fc7b2.jpeg)

したがって、この3つは1種類の移動にまとめることができる。

これをすべての街に対して行い、すべての移動手段を出力すれば`AC`。

### コード
```python
def main():
    from itertools import permutations
    import math

    n = int(input())
    towns = [] # 街の位置
    town_nums = [i for i in range(n)] # 街の全番号
    
    for _ in range(n):
        x_y = list(map(int, input().split()))
        towns.append(x_y)

    result = set() # 結果集計用

    for uv in permutations(town_nums, 2): # すべての街に対して、2つ選んで順序付きで並び替えてタプルを作成
        u = towns[uv[0]]
        v = towns[uv[1]]
        x_dist, y_dist = v[0]-u[0], v[1]-u[1] # x軸とy軸で2つの街の距離の差を取る
        xy_gcd = math.gcd(x_dist, y_dist) # それぞれの距離の差の最大公約数を取る
        result.add((x_dist//xy_gcd, y_dist//xy_gcd)) # 最小移動単位で集計
    
    print(len(result))

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

## 編集後記

A問題でWAした衝撃のABC。