AtCoder Beginner Contest 085 - C

beta.atcoder.jp N枚のお札がすべてが5000円だったとして目標金額と合計金額の比較をすると、 合計金額を減らすためには5000円を1000円に変換するしかなく、 合計金額を増やすためには5000円を10000円に変換するしかない。 これを利用すればよい。 もし行っ…

AtCoder Beginner Contest 110 - C

beta.atcoder.jp 直観とテストケースに頼って実装してしまった。学びにならないのでよくない。 def solve(S, T): sm = {} tm = {} for s, t in zip(S, T): if s in sm and sm[s] != t: return "No" sm[s] = t if t in tm and tm[t] != s: return "No" tm[t] …

AtCoder Beginner Contest 113 - C

beta.atcoder.jp ソートとカウントして出力を作ってから元の順番で。tupleは便利。 def solve(N, M, PYs): Ys = {i + 1: 1 for i in range(N)} ret = {} for p, y in sorted(PYs, key=lambda x: x[1]): ret[(p, y)] = "{:06d}{:06d}".format(p, Ys[p]) Ys[p]…

AtCoder Beginner Contest 075 - C

beta.atcoder.jp 計算量的に一本ずつ外して探索して結果を確認すればよい。 あんまり実装しない隣接行列と再帰でやったが若干はまった。 あんまりなれない実装はするもんじゃないな。 def solve(N, M, ABs): ans = 0 for i in range(M): adjMat = [[0 for _ …

AtCoder Beginner Contest 079 - C

beta.atcoder.jp binaryで総当たり。やっと何も見ずにformatの中身をかけた。 evalはまぁ便利なので若干邪道と思いつつ使う。pythonばっかりつかってるとC++でちゃんと書けるか不安になる。 def solve(ABCD): for i in range(0, 8): ops = "{:03b}".format(i…

AtCoder Beginner Contest 046 - D / 047 - C

beta.atcoder.jp 気づけるか。そこが勝負。 解説の通りなんだけれども、得点を最大化する戦略はパーを出すだけ出す。 そして並び順はどうでもよい。 というのも、相手がグーを出しているとき、グーからパーにすると+1ポイント。 相手がパーを出していると…

AtCoder Beginner Contest 076 C

beta.atcoder.jp 辞書順最小を目指すためにはなるべく前のほうにaを入れてあげる = Tの検索は後ろから。 |S| - |T|の位置から始めて前に行き、Tの長さだけ? or S[i] = T[i]であることを調べる。 pythonのallはfor / if / flagな文を一つのif分にまとめられる…

AtCoder Beginner Contest 070 C / 073 C

beta.atcoder.jp 読んだらわかる、最小公倍数やん。コードは覚えてないけれども。 最小公倍数を求めるときには、最大公約数を求めるのが定石。 というのも最小公倍数を求めるときには a * bの約数のうち、共通で取り除いても問題ないものを取り除く必要があ…

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