ABC336をPythonで（A~E）

AtCoder Beginner Contest 336

A問題

oを入力された数だけ増やす

A

print("L"+"o"*int(input())+"ng")

B問題

$mod2$で$0$だったらカウントを増やして%2%で割る

B

n = int(input())
ans = 0
while n > 0 and n % 2 == 0:
    ans += 1
    n //= 2

print(ans)

C問題

5進数に変換して、各桁を2倍する

C

n = int(input()) - 1

lst = []
while n > 0:
    lst.append(n % 5)
    n //= 5

ans = 0
for l_i in reversed(lst):
    ans = ans * 10 + l_i * 2

print(ans)

D問題

サイズを基準に二分探索

サイズxで出来るかの判定は、
端からxまで上がりそこから下がれるかを調べる
もし、欲しい高さより低い場所aが現れたときは
それまでに条件を満たせるものは絶対になく、そのピラミッドを途中からaの高さまで上がったものが可能性のあるものの中で一番左のものになる

D

n = int(input())
a = list(map(int, input().split()))

def func(x):
    now = 0
    border = 1
    up_side = True
    for i in range(n):
        if a[i] >= border:
            if up_side and border < x:
                border += 1
            else:
                up_side = False
                border -= 1
                if border <= 0:
                    return True
        else:
            up_side = True
            border = a[i] + 1

    return False


ok, ng = 1, n + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if func(mid):
        ok = mid
    else:
        ng = mid

print(ok)

E問題

出来なかったので、後日やります 出来ました

基本は公式解説を参考にしました。
桁和が$p$で且つ$mod$ $p$で0になる自然数の個数を求める関数を用意して、桁和が起こりえるものすべてを計算するようにしてみました。

E

def digit_dp(p):
    # 桁和がpのうち、mod pで0になるN以下の自然数の個数
    # dp[i][j][k][f] = i桁目で、桁和がj、mod pがkとなる数の個数。f=[N未満が確定したもの, Nと等しいかもしれないもの]
    dp = [[[[0] * 2 for _ in range(p + 1)] for _ in range(p + 1)]for _ in range(digit + 1)]
    dp[0][0][0][1] = 1
    for i in range(digit): # i桁目
        n = int(N[i])
        for j in range(p + 1): # 桁和がj
            for k in range(p): # mod p == k
                for x in range(10):
                    for f in range(2):
                        if j + x > p: continue # 桁和が超えたもの
                        if f and n < x: continue # Nより大きくなるもの
                        dp[i + 1][j + x][(k * 10 + x) % p][f and n == x] += dp[i][j][k][f]

    return sum(dp[-1][p][0])

N = input()
digit = len(N) # 桁

ans = 0
for i in range(1, digit * 9 + 1):
    ans += digit_dp(i)

print(ans)