AtCoder Beginner Contest 214

A - New Generation ABC

import sys
import heapq, math
from collections import defaultdict, deque
from bisect import bisect_left, bisect_right
inputs = sys.stdin.readline
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
inputs = sys.stdin.readline
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
inputs = sys.stdin.readline
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()

始めて宝石をもらうのはt[i]が最小になる時。
その時刻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
inputs = sys.stdin.readline
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)を求めることでこれが計算可能でした