Atcoder ABC248 振り返り

A - Lacked Number【AC】

　not inと書くことで，含まれていないときTrueが返ってきます．

N = input()
for i in range(10):
    if str(i) not in N:
        print(i)
        break

B - Slimes【AC】

　ドラえもんのバイバインの回を知っていれば，たとえK=2でも一瞬で10^9を超えちゃう事がイメージできます．

A, B, K = map(int, input().split())
ans = 0

while A < B :
    A *= K
    ans += 1
print(ans)

C - Dice Sum【解説AC】

　DPが苦手すぎる……アルゴ式か何かでDPの徹底訓練をする必要がありそうです……
　dp[i][j]=i項目まで値を決めたとき合計がjになる数列の個数
と定義します．1項目の値を決めたとき合計がjになる数列の個数は一つなのでdp[0][j]を1とします．

N, M, K = map(int, input().split())
dp = [[0 for _ in range(K+1)] for _ in range(N)]
MOD = 998244353 
for i in range(1, M+1):
    dp[0][i] = 1

for i in range(N-1):
    for k in range(K+1):
        for m in range(1, M+1):
            if m+k <= K:
                dp[i+1][m+k] += dp[i][k]
                dp[i+1][m+k] %= MOD

print(sum(dp[-1]) % MOD)

D - Range Count Query【AC】

　累積和的な考えで解きました．i番目に値Xが出現したらlist[X][i]に+1し，それぞれのlist[X]に対して累積和的を取ったら，cumsum[X][R]-cumsum[X][L]で求めることが出来ます．
　しかし，これだとリストにNXの要素を持つ事が必要になり，時間が足りません．そこで，i番目に値Xが出現したらlist[X]にiをappendします．そして，LとRがlist[X]の何番目に存在するかを二分探索で求めれば，ただしい解を出すことが出来ます．

import bisect

N = int(input())
A = [int(i) for i in input().split()]
cumsum_dic = {a:[] for a in set(A)}
for i, a in enumerate(A):
    cumsum_dic[a].append(i)

for _ in range(int(input())):
    L, R, X = map(int, input().split())
    L, R = L-1, R-1
    try:
        cumsum = cumsum_dic[X]
        left = bisect.bisect_left(cumsum, L)
        right = bisect.bisect_right(cumsum, R)
        print(right - left)
    except KeyError:
        print(0)