ABC321をPythonで（A~F）

A問題

全探索

A

n = input()

for i in range(len(n) - 1):
    if n[i] <= n[i + 1]:
        print("No")
        exit()
print("Yes")

B問題

とりうるスコアを全部ためす
計算量的にも十分間に合う

B

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

for i in range(101):
    b = a + [i]
    b.sort()
    if sum(b[1:-1]) >= x:
        print(i)
        exit()

print(-1)

C問題

満たす数がかなり少なそうなのでDFSを使って全部求めておく

C

lst = set()
def DFS(x, t):
    global lst
    for i in range(t):
        y = x * 10 + i
        lst.add(y)
        if i > 0:
            DFS(y, i)

for i in range(1, 10):
    lst.add(i)
    DFS(i, i)

lst = sorted(lst)
print(lst[int(input()) - 1])

D問題

Bをソートすると
それぞれのa_iについて
価格がsになるものとpになるものが2分探索で求められる

D

n, m, p = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.sort()

sum_b = [0] + [i for i in accumulate(b)]

ans = 0
for a_i in a:
    x = bisect(b, p - a_i)
    ans += a_i * x + sum_b[x] + p * (m - x)

print(ans)

E問題

まずNが十分に大きいとき
頂点xからkだけ大きいほうに向かったとき
最小値はx*2**k, 最大値はx*2**k+2**k - 1

これをxのときと、i回親に戻りそれの逆側の子でk - i - 1だけ進む
のを足し合わせたのが答え

E

def calc(n, x, k):
    if k <= 0:
        return 1 if 1 <= x <= n and k == 0 else 0
    if k > 60:return 0
    mini = x
    for _ in range(k):
        mini *= 2
        if mini > n:break
    if mini > n:
        return 0
    else:
        return min(mini +2 ** k - 1, n) - mini + 1

for _ in range(int(input())):
    n, x, k = map(int, input().split())
    ans = calc(n, x, k)
    for i in range(1, k + 1):
        if x <= 1:
            break
        elif i == k:
            ans += 1
        elif x % 2 == 0:
            x //= 2
            ans += calc(n, x * 2 + 1, k - i - 1)
        else:
            x //= 2
            ans += calc(n, x * 2, k - i - 1)

    print(ans)

F問題

+だけのときは典型的なDPなので-について考える

+x -xの連続でクエリがきたときは+xが来た時と逆順で計算すれば戻せる
+xと-xの間に他のクエリが来ても足し算引き算は可換なので上と同様に計算してもよい

F

mod = 998244353
q, k = map(int,input().split())

dp = [1] + [0] * k
for _ in range(q):
    f, X = input().split()
    x = int(X)

    if f == "+" and x <= k:
        for i in range(k, x - 1, -1):
            dp[i] += dp[i - x]
            dp[i] %= mod
    elif f == "-" and x <= k:
        for i in range(x, k + 1):
            dp[i] -= dp[i - x]
            dp[i] %= mod

    print(dp[k])