総括
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)
方針は、
- 文字列
Sを先頭からすべて試してみる - 上記で選んだ添え字
sから文字列Tとの一致を判定 -
SとTが一致しない添え字の数をカウントする - 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のテンプレが役に立ちました。
同じグループの中に友達がいないようにグループを作成するためには、最も大きな友達関係にあるグループメンバーをバラバラにすればよさそうです。
方針は、
- UnionFindでグループ属性を管理
- それぞれのグループのサイズをチェック
- 最も大きいグループサイズが答え
です。
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」の条件分岐に気を付けて回答を出力します。