Typical DP Contest A

DP訓練。 tdpc.contest.atcoder.jp まずはDP抜きにして問題文がきちんと理解できていることを確認するために さくっと実装。 def solve(N, Ps): cs = set() cs.add(0) for p in Ps: d = set() for c in cs: d.add(c + p) cs.update(d) return len(cs) if __n…

AtCoder Beginner Contest 046 - C / 050 - C

beta.atcoder.jp 答えを見たらもっと楽だった。 確認時の比を t : a、前回までの累計をT, A、前回確認時からの差分をx , yとしたとき以下が成り立てばよい。 T + x : A + y = t : a 式にしてこれを整理すると、 x = (t * A + y * t) / a - T y = (a * T + x …

AtCoder Beginner Contest 061 - C / 064 - C

beta.atcoder.jp 基数ソートで計算量N。 普通のソートはNlogNなのでソートそのものは間に合うけれども 挿入回数が1010まで行くのでばらばらに数値を扱うと間に合わなさそう。 def solve(N, K, ABs): counts = {i: 0 for i in range(1, 10 ** 5 + 1)} for a, …

AtCoder Beginner Contest 054 - C / 057 - C

beta.atcoder.jp 無向グラフの探索。再帰よりもキューのほうが好き。深さ優先と幅優先の切り替えが楽だから。 def solve(N, M, Es): al = {} for e in Es: al.setdefault(e[0], []).append(e[1]) al.setdefault(e[1], []).append(e[0]) ans = 0 q = [(1, [1]…

AtCoder Beginner Contest 042 - C / 044 - C

Tenka1のログインアカウント間違えて参加してしまった。。 とはいえ、300点、400点問題あたりに壁を感じるので過去問練習。 abc042.contest.atcoder.jp 数が少ないので総当たり。最大 2N 回繰り返されるかな。 def solve(N, K, Ds): while True: c = set([in…

Write-up: TopCoder TCO19 Single Round Match 737 Div2

以下3問。Div2って書いてなかったけど多分Div2。 Easy: Make737Easy Medium: AliceAndBobMedium Hard: SimpleMathProblem 公式Editorial Single Round Match 737 Editorials - Topcoder 2.0