ABC138参戦記(A問題~C問題)

先日行われたABC138に参加したのでコンテスト中のあれこれをメモしておこうかと思います。使用言語はpython3、結果はABC3完で2403位(順位表情報)でした。コンテストへのリンクはこちら→https://atcoder.jp/contests/abc138

A - Red or Not

$a$が3200以上か未満かで場合分けして"red"を出力するか$s$を出力するか決めれば良さそうです。提出コードはこちら。

ABC138_A.py

a = int(input())
s = str(input())
if a < 3200:
    print("red")
else:
    print(s)

B - Resistors in Parallel

$A_1, A_2, ..., A_N$の逆数を順に足していき、最後にその逆数を出力すれば良さそうです。提出コードはこちら。

ABC138_B.py

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    ans += 1/A[i]
print(1/ans)

C - Alchemist

サンプルなどを見てみると、小さい方から順に合成していくとあまり小さくならなそうな感じがするので、そのような実装をしました。ちゃんと証明した方がいいのかなとは思いましたがサンプルが全て通ったので提出してみたらACしました

ABC138_C.py

N = int(input())
v = list(map(int, input().split()))
v.sort()
tmp = (v[0] + v[1]) / 2
for i in range(2,N):
    tmp = (tmp + v[i]) / 2
print(tmp)

D - Ki

本番中通すことができませんでした...
keyが根、valueがkeyを根とする頂点であるような辞書を作ってそこに含まれる全ての頂点のカウンターにいっぺんに$x$を足していくみたいなことをやったのですが当然のようにTLEしました...

ABC138_D.py

from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(700000)

def setD(d, N):
    for i in range(N):
        d[i] = setsub(d, i)
            
def setsub(d, i):
    tmp = deque()
    for x in d[i]:
        tmp.append(x)
        if d[x] != 0:
            tmp += setsub(d, x)
    return tmp

N, Q = map(int, input().split())
d = defaultdict(deque)

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append(b)

setD(d, N)

ans = [0 for i in range(N)]

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
    for i in d[p]:
        ans[i] += x


for i in range(N):
    ans[i] = str(ans[i])
print(" ".join(ans))

コンテスト後に解説動画やACされてるコードなどをみて累積和のようなことをすればいいということを理解し、一応通せたのですがコンテスト後にテストケースが追加されてるのでもう一度復習してみたいところです。

反省

今回はC問題まで通すことができました。時間配分は大体A-2分、B-3分、C-6分半という感じでした。とにかくDが通せなかったのは痛いですね...要復習です...