2022-04-01から1ヶ月間の記事一覧

AtCoder Beginner Contest 248 C

https://atcoder.jp/contests/abc248/tasks/abc248_cでなく、とした方が書きやすいので、そうしましょう。そして、とします。パット見、母関数ですが、C問題で母関数のはずないと思って考え直すと、単なるDPですね。 def update(dp, M, L): new_dp = [0] * (…

AtCoder Beginner Contest 248 B

https://atcoder.jp/contests/abc248/tasks/abc248_bなんということもない問題ですが、ふつうに書くと def F(A, B, K): for k in count(): if A >= B: return k A *= K Aを更新するところが気持ち悪いですね。 こういうときは、べき乗を排出するgeneratorを…

AtCoder Beginner Contest 246 F

https://atcoder.jp/contests/abc246/tasks/abc246_fこの問題は数学的ですが、ということで単純に包除原理を使うだけです。例1で考えると、文字が26種類しかないのでどの文字を使うかを2進数で表して、aが使われていたら最下位ビットを立てて、bが使われてい…

AtCoder Beginner Contest 246 D

https://atcoder.jp/contests/abc246/tasks/abc246_dパッと見、数学的な問題のようですが、そんなことは全然ありません。(b, a) = (0, 5)から辿っていくだけです。計算量はです。 # coding: utf-8 # 2-variable Function from itertools import count ######…

AtCoder Beginner Contest 246 A

https://atcoder.jp/contests/abc246/tasks/abc246_a第一感は、x座標で2回出てくる座標と1回出てくる座標があるので、1回出てくる方を取ればいいのだろう、というものでした。 # coding: utf-8 # Four Points from collections import Counter import sys ##…