총괄

A와 D만 풀었습니다.
B로 멈추어 버려, C도 풀지 않고···.
D가 빨리 풀린 것이 유일한 구원.
B와 C의 시간 손실로 E까지 진행하지 않고.
분한 결과가 되었습니다.

문제

AtCoder Beginner Contest 177

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. 문자열 S2. 상기에서 선택한 첨자 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 를 "제곱하여 합한 것"을 sq_sum 로 하고, "합계하여 제곱한 것"을 sum_sq

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)

할 일은 두 가지로, "모든 쌍에서 GCD를 취하고 1인지 확인"과 "모든 A에서 GCD를 취하여 1인지 확인"하는 것입니다. 입니다.
제약적으로 두 번째는 아무것도 생각하지 않고 할 수 있지만, 첫 번째로 궁리해야합니다.

모든 쌍으로 GCD를 취하면 TLE 가 되어 버리므로, 다른 접근법을 생각합니다.
GCD가 1이라는 것은, 1회로 온 A에 대해서, 그 배수인 숫자는 나오지 않게 되므로, 그것을 체크합니다.
구체적으로는 memo 의 배열에 A 의 요소의 출현수를 카운트해, memo 를 첨자의 스텝 마다 합을 취해, sum 를 취합니다.

그리고는 「pairwise coprime」, 「setwise coprime」, 「not coprime」의 조건 분기를 주의해 응답을 출력합니다.