AtCoder Beginner Contest 070 C / 073 C

beta.atcoder.jp

読んだらわかる、最小公倍数やん。コードは覚えてないけれども。

最小公倍数を求めるときには、最大公約数を求めるのが定石。

というのも最小公倍数を求めるときには a * bの約数のうち、共通で取り除いても問題ないものを取り除く必要がある。 この共通なものこそが最大公約数なわけである。

最大公約数のアルゴリズムはユークリッドの互除法。 証明はさておき、プログラムコード的には小さいのと大きいのに分け、 大 % 小と大を計算する。大 % 小が0になるまでループしたとき、大が最大公約数になる。

def solve(N, As):
    n = 1

    def gcd(a, b):
        a, b = min(a, b), max(a, b)
        while a > 0:
            a, b = b % a, a
        return b

    def lcm(a, b):
        return a * b // gcd(a, b)

    for a in As:
        n = lcm(a, n)
    return n


if __name__ == "__main__":
    N = int(input())
    As = [int(input()) for _ in range(N)]
    print(solve(N, As))

beta.atcoder.jp

数ごとに出現数の偶奇をとって奇数のものをカウントすればよい。 pythonだとCounterでワンライナーでも行けるかな？

300点問題波ありすぎない？

from collections import Counter


def solve(N, As):
    c = Counter(As)
    return len([k for k, v in c.items() if v % 2 == 1])


if __name__ == "__main__":
    N = int(input())
    As = [int(input()) for _ in range(N)]
    print(solve(N, As))

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 __name__ == "__main__":
    N = int(input())
    Ps = [int(c) for c in input().split(" ")]
    print(solve(N, Ps))

練習のためDPを考える。実装はどうあれ、思考が大事。

まず、順番はどうあれ、すべてを処理しそうなので、0番目からi番目を処理することを考える。

ここで以下のように考える。

「i番目において何通り存在するかを計算しようとしたとき、i-1番目までの処理結果として何が出てくれば、計算できるか。」

今回は、i-1番目までに通り数が出てくるだけではi番目は計算できない。 そこでi-1番目までに作れるすべての数値のSetが必要だと思いつく。 つまりは「i-1番目において、特定の数値が作れるか否か」の情報があればi番目に役に立てられる。

ではi-1番目までの結果をどう得るかで配列と再帰の2パターンで実装する。

配列

def dp_solve1(N, Ps):
    dp = [[False for p in range(sum(Ps) + 1)] for i in range(N + 1)]
    dp[0][0] = True
    for i in range(1, N + 1):
        for j in range(sum(Ps) + 1):
            if j - Ps[i - 1] >= 0:
                dp[i][j] = dp[i - 1][j - Ps[i - 1]] or dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j]
    return sum(dp[N])

配列の場合は漸化式となり、i-1番目の配列に、i-1番目までの結果が入っており、これを元にi番目の配列を作る。 「i番目においてjが作れるか否か」をbooleanとしてdp[i][j]に入れると、

  1. i-1番目においてjが作れていれば、「p[i]を取らない」選択によってi番目でも作れる

  2. i-1番目においてj - p[i]が作れていれば、「p[i]を取る」選択によってi番目でも作れる。

これが大方針となる。初期条件としてはdp[0][0] = True

実装面の注意として

  1. 初期条件は問題を考える配列のさらにひとつ前の配列に存在する必要がある。

  2. 作れる数の最大範囲の分だけ、jの範囲が必要

  3. j - p[i]が0以下のときは作れない。

次に、再帰を考える、

def dp_solve2(N, Ps):
    def dp(i):
        if i == 0:
            return set([0, Ps[i]])
        else:
            prev = dp(i - 1)
            return set([ps + pv for ps in [0, Ps[i]] for pv in prev])
    return len(dp(N - 1))

再帰は「i-1番目において、特定の数値が作れるか否か」をダイレクトに「作れる数値すべて」としてSetとして返す。 一番小さい問題として、0番目だけで考えると、単純に取るか取らないかの2パターンを返し、 i-1番目の結果からさらに、取るか取らないかの2パターン分をすべて計算、Setにして返す。

実装面の注意として

  1. dpの最初のコールはPの問題の添え字なので、Nではなく、N-1。

  2. dpは2つ以上の引数であることが多いが１次元配列でも立派にDP。２つであることを前提に考えない。

実装面では添え字の細かい部分まで気を張る必要があるね。

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 * a) / t -  A

となる。このとき、x, y がいずれも0または正の整数となり、最少であればよい。

xの右辺のうち、Tは整数のため、残りの部分が分子がaで割り切れることが必要であり、

(t * A) % a = m

とすると、

(m + (y * t)) % a = 0

となるyを見つければよい。

さらに、x が0または正より

x =  (t * A + y * t) / a -  T  >= 0

が成り立つため、 yについて整理すると、

y >= (T * a - t * A) / t

というyの条件ができる。y >= 0と合わせて、 これらの条件のうち大きいほうをyの検索範囲の最初にする。

ユークリッドの互除法とかをほんとは使いそうなんだけれども、 条件さえ決めてしまえば+1ずつしても間に合ってしまったのでそのまま提出。 周りの解答見るともう4倍ぐらい早いな。。

def solve(N, TAs):
    T, A = 1, 1
    for t, a in TAs:
        m = (t * A) % a
        y = max(0, (T * a - t * A) // t)
        while True:
            if (m + (y * t)) % a == 0:
                break
            y += 1
        x = (t * A + t * y) // a - T
 
        T += x
        A += y
    return T + A
  
if __name__ == "__main__":
    N = int(input())
    TAs = [(tuple)(map(int, input().split(" "))) for l in range(N)]
    print(solve(N, TAs))

beta.atcoder.jp

まずNの偶奇でAとして存在可能な数値が分かれる。 Nが偶数の時、Aの要素は奇数になり、それらはすべて2つずつ存在する。 Nが奇数の時、Aの要素は偶数になり、ちょうど真ん中にある0は一つ、それ以外はすべて二つずつ存在する。

以下でテストケースは通るんだけどAの要素の上限設定も必要だった。このままだと相異なればよいだけや。

from collections import Counter
 
 
def solve(N, As):
    c = Counter(As)
    n = 10 ** 9 + 7
    if c['0'] == N % 2 and \
            all([v == 2 and int(i) % 2 == (N + 1) % 2 for i, v in c.items() if i != '0']):
        return pow(2, N // 2, n)
 
    return 0
 
 
if __name__ == "__main__":
    N = int(input())
    As = input().split(" ")
    print(solve(N, As))

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, b in ABs:
        counts[a] += b
    s = 0
    for c, count in counts.items():
        s += count
        if K <= s:
            return c


if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    ABs = []
    for _ in range(N):
        ABs.append(tuple(map(int, input().split(" "))))
    print(solve(N, K, ABs))

この辺りはアルゴリズムイントロダクション様様。 セールで半額で買ったけど良い買い物したと思う。

books.rakuten.co.jp

beta.atcoder.jp 商の種類のカウント。 質問を見逃して、8種類以上にはならないと思っててはまった。 あと色は選ばなくてはならない、のでALLが一人だけいたら最低1つの色は使うことになる。

def solve(N, As):
    colors = set()
    allcount = 0
    for a in As:
        n = a // 400
        if n < 8:
            colors.add(n)
        else:
            allcount += 1
    return max(len(colors), 1), len(colors) + allcount


if __name__ == "__main__":
    N = int(input())
    As = map(int, input().split(" "))
    m1, m2 = solve(N, As)
    print(m1, m2)

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])]
    while len(q) > 0:
        current, history = q.pop()
        nexts = al[current] if current in al else []
        if len(history) == N:
            ans += 1
        for n in nexts:
            if n not in history:
                nhist = history[:]
                nhist.append(n)
                q.append((n, nhist))
    return ans


if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    Es = []
    for _ in range(M):
        Es.append(tuple(map(int, input().split(" "))))
    print(solve(N, M, Es))

beta.atcoder.jp

簡単な因数分解。300点でも波があるな。

因数を探すとき、上限が√Nであるのはよいのだけれど、下を少し気にしなくてはいけない。 素因数分解だとrangeの最初は2。Nを割りながら探すために1にすると無限ループになってしまう。 逆に単なる因数はNが素数の時を考慮しなくてはならないので、1になる。

def solve(N):
    ret = []
    for i in range(1, int(N ** 0.5) + 1):
        if N % i == 0:
            ret.append(max(len(str(i)),
                           len(str(N // i))))
    return min(ret)


if __name__ == "__main__":
    N = int(input())
    print(solve(N))

pythonはmin / max / all / anyあたりを覚えたらかなり行数が減った気がする。

AtCoder Beginner Contest 042 - C / 044 - C

Tenka1のログインアカウント間違えて参加してしまった。。 とはいえ、300点、400点問題あたりに壁を感じるので過去問練習。

abc042.contest.atcoder.jp

数が少ないので総当たり。最大 2N 回繰り返されるかな。

def solve(N, K, Ds):
    while True:
        c = set([int(c) for c in str(N)])
        if len(c.intersection(Ds)) == 0:
            return N
        N += 1

abc044.contest.atcoder.jp

再帰で頑張ろうとしたがうまくいかなかったので、総当たりに変更。 頻出だけれどN個の0と1の組み合わせは0~2のN乗の2進数表示でどうにかなる。format記法が覚えられない。 計算量が少なければ、初めから総当たりにすべきだった。 別解への挑戦は一度終わってからにしよう。本番のように練習を。

def solve(S):
    l = 2 ** (len(S) - 1)
    sum = 0
    for i in range(l):
        bi = ("{:0%db}" % (len(S) - 1)).format(i)
        ope = []
        for b in bi:
            if b == "0":
                ope.append("")
            else:
                ope.append("+")
        ope.append("")
        p = ""
        for s, o in zip(S, ope):
            p += s
            p += o
        sum += eval(p)
    return sum

アルゴリズムの勉強はしてきたが、実装力が追い付いてないのでまたそろそろ OS自作入門、Linuxのブートプロセスなどと並行してゴリゴリやるか。