🦊

2022/03/30に公開

# A - New Generation ABC

``````import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
n = int(input())
if 1<=n<=125:
print(4)
elif 126<=n<=211:
print(6)
else:
print(8)

if __name__ == '__main__':
main()
``````

# B - How many?

``````import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
s,t = map(int, inputs().split())
ans = 0
for a in range(0, s+1):
for b in range(0, s+1):
for c in range(0, s+1):
if a+b+c<=s:
if a*b*c<=t:
ans += 1
print(ans)

if __name__ == '__main__':
main()
``````

sが高々100程度なので3重ループでも間に合うため、(a,b,c)の組を全探索

# C - Distribution

``````import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

def main():
n = int(input())
s = list(map(int, inputs().split()))
t = list(map(int, inputs().split()))
mn = min(t)
ans = [inf]*n
for idx in range(n):
if t[idx]==mn:
break
ans[idx] = t[idx]
for j in range(1, n):
nx = ans[(idx+j-1)%n]+s[(idx+j-1)%n]
ans[(idx+j)%n] = min(t[(idx+j)%n], nx)
print(*ans, sep='\n')

if __name__ == '__main__':
main()
``````

その時刻xからスタートし、宝石が渡されてくる場合(x+s[i-1])と、高橋君に宝石をもらう場合(t[i])で小さい値を採用していく

# D - Sum of Maximum Weights

``````import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
mod = 10**9+7
inf = float('inf')
#sys.setrecursionlimit(10**7)

class UnionFind:
"""
n : 要素数
root : 親ノード
size : グループのサイズ
"""

def __init__(self, n):
self.n = n
self.root = [-1]*(n+1)
self.size = [1]*(n+1)

"""ノードxのrootノードを見つける"""
def Find_Root(self, x):
if self.root[x] < 0:
return x
else:
self.root[x] = self.Find_Root(self.root[x])
return self.root[x]

"""木の合併"""
def Union(self, x, y):
#入力ノードの親を探索
x = self.Find_Root(x)
y = self.Find_Root(y)

#既に同じ木に所属する場合
if x==y:
return

#異なる木に所属する場合 -> sizeが小さい方から大きい方に合併する
elif self.size[x] > self.size[y]:
self.size[x] += self.size[y]
self.root[y] = x

else:
self.size[y] += self.size[x]
self.root[x] = y

"""xとyが同じグループに所属するか"""
#　辺(x,y)が橋の場合
#   ⇒(x,y)以外をUnionしたとき、isSameGroup(self, x, y)=False

def isSameGroup(self, x, y):
return self.Find_Root(x) == self.Find_Root(y)

""" 頂点数を数える"""
#全連結成分にするために必要な橋の本数は、cnt - 1
def Count_Vertex(self):
cnt = 0
for i in range(self.n):
if self.root[i+1] < 0:
cnt += 1
return cnt

""" xが属する集合に含まれる全ノードを返す """
def Members(self, x):
r = self.Find_Root(x)
return [i for i in range(self.n+1) if self.Find_Root(i) == r]

"""xが属する集合のサイズ"""
def Size(self, x):
return self.size[self.Find_Root(x)]

def main():
n = int(input())
g = []
for _ in range(n-1):
u,v,w = map(int, inputs().split())
g.append((u-1, v-1, w))
g = sorted(g, key=lambda x:x[2])
uf = UnionFind(n)
ans = 0
for i in range(n-1):
u,v,w = g[i]
x = uf.Size(u)
y = uf.Size(v)
ans += x*y*w
uf.Union(u,v)
print(ans)

if __name__ == '__main__':
main()
``````

• 頂点u,v間の最大距離が求まればよい
• dijkstraの更新式を累積させるのではなく最大値で更新すれば取得可能？
• dijkstra:O(|E|logN) x 開始点:O(N)で明らかにTLE

コストの小さい辺からUnionFindで連結していき、w*size(u)*size(v)を求めることでこれが計算可能でした

ログインするとコメントできます