AtCoder ABC 177 Python (A~E)

# 総括
AとDのみ解けました。
Bでどはまりしてしまい、Cも解けず・・・。
Dがすぐに解けたのが唯一の救い。
BとCの時間ロスでEまで進めず。
悔しい結果となりました。


#問題
[AtCoder Beginner Contest 177](https://atcoder.jp/contests/abc177)

# A. Don't be late
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/4c763cbb-9dc4-6c9e-7841-44e34bc79f9a.png)

##### 回答
```python

D, T, S = map(int, input().split())

time = D / S
if T < time:
    print('No')
else:
    print('Yes')

```
速さ```S```で```D```メートル進む場合の時間```time```を求めて制限時間```T```と比較します。


# B. Substring(後日AC)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/e25d8e01-99e3-3da4-c554-70d585e6c4bf.png)

##### 回答
```python

S = input()
T = input()

answer = float('inf')
for s in range(len(S)):
    if len(S) - s < len(T):
        break

    count = 0
    for t in range(len(T)):
        if S[s+t] != T[t]:
            count += 1
            
    answer = min(answer, count)

print(answer)

```

方針は、
1. 文字列```S```を先頭からすべて試してみる
2. 上記で選んだ添え字```s```から文字列```T```との一致を判定
3. ```S```と```T```が一致しない添え字の数をカウントする
4. 1と2を繰り返し行い```min```をとったものが答え
です。

コンテスト時は難しく考えすぎました。
上記の回答例は```S```をメインとして数えあげていますが、コンテスト時は```T```をメインにした数え上げを行おうとし上手くいきませんでした。

# C. Sum of product of pairs(後日AC)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/669c47f6-b93c-be85-0ca8-654d1cfbdc5e.png)

##### 回答
```python

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

sq_sum = sum(map(lambda x: x*x, A))
sum_sq = sum(A) * sum(A)
answer = (sum_sq - sq_sum) // 2

print(answer % mod)

```
下記の式変形に気づければ簡単です。

```math
(A_1 + A_2 + .... + A_n)^2 = (A_1^2 + A_2^2 + .... + A_n^2) + 2(A_1A_2 + A_2A_3 + .... + A_{n-1}A_n)\\

(A_1A_2 + A_2A_3 + .... + A_{n-1}A_n) = ((A_1 + A_2 + .... + A_n)^2 - (A_1^2 + A_2^2 + .... + A_n^2)) \div 2

```

リスト```A```を「2乗して合計したもの」を```sq_sum```とし、「合計して2乗したもの」を```sum_sq```として求め、両者の差をとって2で割ります。


# D. Friends
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/27da4d94-272a-6001-2711-f3fce07f8777.png)


##### 回答
```python

class UnionFind(): # 0インデックス
    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)]


if __name__ == "__main__":
    N, M = map(int, input().split()) # N人、M個の関係
    union_find = UnionFind(N)
    for _ in range(M):
        A, B = map(int, input().split())
        A -= 1
        B -= 1
        union_find.union(A, B)

    answer = 0
    for i in range(N):
        answer = max(answer, union_find.size(i))

    print(answer)
   

```
唯一準備している```UnionFind```のテンプレが役に立ちました。
同じグループの中に友達がいないようにグループを作成するためには、最も大きな友達関係にあるグループメンバーをバラバラにすればよさそうです。

方針は、
1. UnionFindでグループ属性を管理
2. それぞれのグループのサイズをチェック
3. 最も大きいグループサイズが答え

です。

# E. Coprime
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/668985/e77bbb1f-dbec-bb60-8877-c7c725833acc.png)

##### 回答(後日AC)

```python

import math
L = 10**6 + 1

N = int(input())
A = list(map(int, input().split()))
memo = [0] * L
flag = 0 # 0をpairwise coprime

for a in A:
    memo[a] += 1

for i in range(2, L): # すべてでgcdが1ということは、対象の数字ごとのステップに数字がないことと同じ
    if sum(memo[i::i]) > 1:
        flag = 1
        break

g = 0
for i in range(N):
    g = math.gcd(g, A[i])

if flag == 0:
    answer = 'pairwise coprime'
elif flag == 1 and g == 1:
    answer = 'setwise coprime'
else:
    answer = 'not coprime'

print(answer)

```

やることは、2つで、「すべてのペアでGCDをとって1であるか否かをチェック」することと、「すべてのAでGCDをとって1であるか否かをチェック」することです。
制約的に2つ目は何も考えずに行えますが、1つ目で工夫する必要がります。

すべてのペアでGCDをとると```TLE```となってしまうので、違うアプローチを考えます。
GCDが1であるということは、1回でてきたAについて、その倍数である数字は出てこないこととなりますので、それをチェックします。
具体的には、```memo```の配列に```A```の要素の出現数をカウントし、```memo```を添え字のステップごとに和をとり、```sum```をとります。

あとは「pairwise coprime」、「setwise coprime」、「not coprime」の条件分岐に気を付けて回答を出力します。