AtCoder Beginner Contest 138（A~D、過去問）

A問題

入力した文字列の大きさによって出力文字を変える問題 atcoder.jp

コード

#!/usr/bin/env python3

#### input
a = int(input())
s = input()

#### process
if a >= 3200:
  print(s)
else:
  print("red")

B問題

N個の入力に対して、

\( \dfrac{1}{\frac{1}{A_1} + \frac{1}{A_2} + ... + \frac{1}{A_N}}\)

を求める問題 atcoder.jp

所感

ABC139で丸め誤差に苦しめられたのでなるべく誤差がでない形（int）で計算を進める

コード

#!/usr/bin/env python3
from functools import reduce

#### input
N = int(input())
As = list(map(int, input().split()))

# N=1ならそのまま数字を返す
if N == 1:
  print(As[0])
  exit()

#### process
# 分母はA_1〜A_Nの積
numerator = reduce(lambda a, b: a * b, As)
denominator = 0
for i in range(0, N):
  tmp = As.pop(0)
  # 分子は「A_1以外の積」＋「A_2以外の積」＋・・・
  denominator = denominator + reduce(lambda a, b: a * b, As)
  As.append(tmp)

print(numerator / denominator)

C問題

\( N \) 個の数字\( v_i \) の中から2つを選んで平均値に置き換える作業を繰り返した時、最後に残る数字の最大値を求める問題

atcoder.jp

所感

先頭から順番に処理を繰り返していくと、最後に残る値は、

\( \dfrac{\dfrac{\dfrac{v_1 + v_2}{2} +v_3}{2} + v_4}{2} ... \)

であり、これを通分すると、

\( v_1 + v_2 + 2v_3 + 2^2v_4 + ... + 2^{N-2}v_N\)

となるのでこれを最大化するためには数列が小さい順に並んでいればいい。
ということで、ソートを行った後に上記を計算しに行く

コード

#!/usr/bin/env python3

#### input
N = int(input())
vs = list(map(int, input().split()))

#### process
vs_sorted = sorted(vs)
vs_sum = vs_sorted[0]

for i in range(1, len(vs_sorted)):
  # リストのインデックスは0から始まるので数値がずれることに注意
  vs_sum = vs_sum + 2**(i-1) * vs_sorted[i]

print(vs_sum / 2**(N-1))

D問題

（説明略） atcoder.jp

所感

木構造の問題。木構造全然詳しくないのでめちゃくちゃ焦った。
各ノードに対して毎回上からたどっていって計算していくと計算量がO(NQ)になって間に合わない。
あるノードの合計得点はその1つ上のノードの合計得点＋自分の獲得得点で計算できるので、 これをなんとかして計算量を減らせないか考えたが思いつかず。
下記は提出だけしたけどTLE連発したやつ。

DFSもBFSも全然わからないので勉強しないと。。。
グラフ理論も色々調べてみてるけど実装までわからん。。。

コード（失敗）

#!/usr/bin/env python3

import sys
input = sys.stdin.readline

#### input
N, Q = list(map(int, input().split()))
ABs = []
for i in range(0, N-1):
  ABs.append(list(map(int, input().split())))

ABs.sort(key=itemgetter(1))

PXs = []
for i in range(0, Q):
  PXs.append(list(map(int, input().split())))

#### process
scores = [0] * N
above_nodes  = [[x+1] for x in range(0, N)]

for i in range(0, len(ABs)):
  above_nodes[ABs[i][1]-1].extend(above_nodes[ABs[i][0]-1])

for i in range(0, len(PXs)):
  scores[PXs[i][0]-1] = scores[PXs[i][0]-1] + PXs[i][1]

for i in range(0, N):
  node_score = 0
  for above_node in above_nodes[i]:
    node_score = node_score + scores[above_node-1]
  print(node_score, end = ' ')
print("")