yukicoder contest 292 参戦記

A 1485 運賃

電車とバスの運賃を足すだけです.

n, m = map(int, input().split())

print(n + m)

B 1486 ロボット

E≦10⁹なのでO(E)は無理だが、F=gcd(A+B,C+D)としたときに、F≦10⁶なのでO(F)は可能. なのでF秒間で2台のロボットが同時に動いている秒数をループで求める. あとはEをFで割ったあまりの秒数についても同様にループを回して同時に動いている秒数を求めれば、最終的な答えが求まる.

from math import gcd

A, B, C, D, E = map(int, input().split())

x = (A + B) * (C + D) // gcd(A + B, C + D)
y = ([True] * A + [False] * B) * (x // (A + B))
z = ([True] * C + [False] * D) * (x // (C + D))

c = 0
for i in range(x):
    if not y[i] or not z[i]:
        continue
    c += 1

result = E // x * c
for i in range(E % x):
    if not y[i] or not z[i]:
        continue
    result += 1
print(result)

C 1487 ぺんぎんさんかっけー

3辺の長さから三角形の面積を求める公式はググればすぐ見つかる. 直感的に各辺が半分になって2次元なので2乗されて1/4となる. サンプルで答えが合ったので、直感通りのようだ.

from math import sqrt

def f(a, b, c):
    s = (a + b + c) / 2
    return sqrt(s * (s - a) * (s - b) * (s - c))

a, b, c = map(int, input().split())

print(f(a, b, c) / 4)

D 1488 Max Score of the Tree

ある辺の長さを2倍にするとどれだけスコアが伸びるかというと、その辺の下にぶら下がっている葉の数×辺の長さだけ増える. DFS でそれぞれの辺の下にある葉の数と最初のスコアを求め、DP で増やせるスコアの最大値を求めれば解ける.

from sys import stdin

readline = stdin.readline

N, K = map(int, readline().split())
links = [{} for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, readline().split())
    a, b = a - 1, b - 1
    links[a][b] = c
    links[b][a] = c


def dfs(parent):
    l = links[parent]
    if len(l) == 0:
        return (0, 1)

    total_score = 0
    total_leaves = 0
    for child in l:
        del links[child][parent]
        score, leaves = dfs(child)
        total_score += score
        total_leaves += leaves
        t.append((l[child], leaves))
        total_score += l[child] * leaves
    return total_score, total_leaves


t = []
result, _ = dfs(0)

dp = [-1] * (K + 1)
dp[0] = 0
for i in range(len(t)):
    for j in range(K - 1,  -1, -1):
        if dp[j] == -1:
            continue
        a = j + t[i][0]
        if a > K:
            continue
        dp[a] = max(dp[a], dp[j] + t[i][0] * t[i][1])
result += max(dp)
print(result)