4完＋時間外1完
出かけたり家具を組み立てたりで疲れていた割に脳はさえていた。むしろ普段運動してなさすぎでは…残り5分でなんとか4完のため、5完は到底無理。ただ、E問題の方が回答に時間がかからなかったので、こちらを先に解けばパフォ＋400以上行けたわけだがE問題は練習でだろうと一度も解いたことがなく、今回時間外で緑パフォとはいえまず本番で解こうなどとは思わないだろう。単純に実力が足りない。
さすがにDE（どっちかというとD）は想定解とは違うのかなと思いつつもどちらも想定解の範囲だったようで、いい考察ができたように思う。
C問題
シグマが出てくると普段使ってなさ過ぎて何すればいいかわからなくなるけどよくよく見るとiとi+1以降をかけたものをひたすら足していく。数字が大きくなると思いきや3回以上かけるわけではなくそこまで大きくはならないため10**9+7で割ったあまりはおまけ程度。よくよく考えるとi*それ以降の総和となっているため累積和を取れば何やらうまくいきそうな気がする。
N=int(input())
T=list(map(int,input().split()))
mod=(10**9)+7
goukei=0
S=[]
tmp=0
for i in range(N):
tmp+=T[i]
S.append(tmp)
for i in range(N-1):
#print(T[i]*(S[N-1]-S[i]))
goukei+=(T[i]*(S[N-1]-S[i]))
goukei=goukei%mod
print(goukei)D問題
かなり苦戦。まずはBFSの前処理的な考えで
for i in range(M):
A,B=map(int,input().split())
S[A].append(B)
S[B].append(A)を使うことは思いつき、これを行ごとに見て最大であればそれに1足せばいいのではないか？と思ったがダメなパターンが2つあり、
1.複数回同じグループを言及しているもの
これはset()で回避できる
2.例えば1と2 1と3が友達で、3と4が友達の場合、S[i]の長さは最大で2でプログラムは3を返すが答えは4になる。サンプルは全部通るため特に2に気づかず、何が悪いかわからず相当な時間を浪費した。
うすうすはBFSで最大の島（グループ）を探していけば行けるのでは？と思っていたが、時間内に作成できる気がしないため遠回りしたが、結局そうすることとなった。0の時うまくいく気がしなかったので念のためifで分けた（意味があるかは微妙なところ）
from collections import deque
N,M=map(int,input().split())
D = [-1]*(N+1)
#S=[[0] * 3 for _ in range(2)] 2行3列の場合
S = [[]for i in range(N+1)]
deq=deque()
for i in range(M):
A,B=map(int,input().split())
S[A].append(B)
S[B].append(A)
ans=0
for i in range(1,N+1):
deq.append(i)
count=0
#D = [-1]*(N+1)
while len(deq)!=0:
v= deq.popleft()
for nv in S[v]:
if D[nv] !=-1:
continue
D[nv] =D[v]+1
deq.append(nv)
count+=1
if count>ans:
ans=count
if ans==0:
print(1)
else:
print(ans)E問題
残り4分しかないためまず解けない。あきらめていたがこの時点で順位がかなり悪く、もしかしてE問題も簡単なのではないか？と思ってみてみるといけそうなので時間外に解いてみた。
考えるところは2つ。coprimeはあえて言及されていないのだろうが互いに素の意味のはず
1.全体で最大公約数（GCD）をとり、1であるかないか（ないならnot coprime ）
2.配列中の任意の2つのGCDがすべて1
1は簡単（？）でhttps://note.nkmk.me/python-gcd-lcm/
がそのまま使える。
2については愚直にやるとTLEするため（した）何かいい方法がないか考察した。序盤でエラトステネスの篩の要領で行けるのではと思いつつも面倒なので愚直に作って遠回りした。
素因数分解して1以外についてエラトステネスの篩を用い、素因数がすでにエラトステネスの篩によって振るわれていないかを確認する。
import math
from functools import reduce
N=int(input())
T=list(map(int,input().split()))
def make_divisors(n):
divisors = []
for i in range(1, int(n**0.5)+1):
if n % i == 0 :
if i!=1:
divisors.append(i)
if i != n // i:
divisors.append(n//i)
divisors.sort()
return divisors
def gcd(*numbers):
return reduce(math.gcd, numbers)
def gcd_list(numbers):
return reduce(math.gcd, numbers)
S=[]
tmp=gcd_list(T)
if tmp!=1:
print("not coprime")
else:
T.sort()
n=10**6+1
isprime=[True]*(n+1)
isprime[0]=False
isprime[1]=False
for i in range(len(T)):
S=make_divisors(T[i])
#print(S)
while len(S)!=0:
tmp=S.pop()
if isprime[tmp]==True:
j=tmp+tmp
while j<=n:
isprime[j] =False
j=j+tmp
else:
print("setwise coprime")
exit()
print("pairwise coprime")反省点
何よりも精進が足りない。unionfind?何それ？という状態だったし、エラトステネスの篩についても動作の大本をいまいち理解していなかったため確信に至らなかった。時間がないといいつつ2ちゃんまとめやゲームしてる場合ではない。しっかし累積和灰パフォ、unionfind or BFS茶パフォですかそうですか…
コメント