総括

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

問題

A. Don't be late

回答


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)

回答


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)

回答


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)

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

(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

回答


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

回答(後日AC)


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」の条件分岐に気を付けて回答を出力します。

AtCoder ABC 177 Python (A~E)

総括

問題