ABC248 A~DをPythonで解く！

はじめに

そろそろ茶色コーダーから抜け出したいChunky_RBP_Chanです。
ABC248 A~Dを解いたのでシェアします。

A: Lacked Number

問題

0~9のうち9種類使った文字列Sが与えられるので使われていない数字を求めよ

解答

文字列を全部見て、ない数字を出力すればよいです。

S = input()
for i in range(10):
    for j in range(len(S)):
        if i == int(S[j]):
            break
    else:
        print(i)
        break

B: Slimes

問題

一回叫ぶごとにK倍に増殖するスライムがA匹いる。B匹以上に増やすには何回叫べばよいか

解答

愚直にAをK倍してBを超えるまで繰り返せばよいです。

A,B,K = map(int, input().split())
num = 0
while B > A*K**num:
    num += 1
print(num)

C: Dice Sum

問題

長さ$N$の数列$A = (A_1,...,A_N)$のうち
$1\leq A_i \leq M$
$\sum_{i=1}^{N}A_i\leq K$
を満たす数列$A$の個数を998244353で割った余りを求めよ。

解答

$N+1$行$K+1$列の配列を用いてDPにより答えを求めます。
$dp[i][j]=i-1$番目までの和が$j$である個数
DPの更新式
$dp[i+1][j+k] += dp[i][j] \space (j+k \leq K)$
を考えれば、$N$番目までの和が$K$以下となる個数は$dp[N][j]$ $(j\leq K)$の和です。

N,M,K = map(int, input().split())
dp = [[0]*(K+1)for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(K+1):
        if dp[i][j] == 0:
            continue
        for k in range(1,M+1):
            next = k+j
            if next <= K:
                dp[i+1][next] += dp[i][j]
print(sum(dp[-1])%998244353)

D: Range Count Query

問題

長さ$N$の数列$A = (A_1,...,A_N)$と$Q$個のクエリが与えられる。
クエリごとに$L,R,X$が与えられるので$A_L,...,A_R$の中で$X$と等しいものの個数を求めよ。

解答

$L$,$R$,$X$が与えられたとき$A_i=X$となる添字を$B_j$とします。($j=1,...,$($A_i=X$となる$i$の個数))
$B_{j+1}$より前にある$X$は$A_{B_1},...,A_{B_j}$の計$j$個なので、
$B_{j} \leq L < B_{j+1}$
$B_{k} \leq R < B_{k+1}$
となる$j$、$k$を二分探索により見つければ$X$は$L$までに$j$個あり、$R$までには$k$個あることがわかります。
したがって$L$から$R$までにある$X$の個数は
$A_L=X$の場合 $\space k-j+1$
$A_L\neq X$の場合 $\space k-j$
解答では、$1$から$N$までをキーに持つ辞書numdictに$B_j$を配列を保管し、各クエリごとキー$X$がもつ配列について二分探索を行います。

例 $A=(1,2,1,1),L=1,R=3,X=1$の場合
数列$A$で$1$となる添字は$[1,3,4]$であり、$L$と$R$は
$B_1\leq L < B_2$,
$B_2 \leq R < B_3$
を満たします。したがって、$L$までに$X$と等しいのは$A_{B_1}$の１つ、$R$までには$A_{B_1},A_{B_2}$の2つがあり、
$A_L=1$なので答えは$2-1+1=2$

def bisect(x,ind,size):
    ok = -1
    ng = size
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if ind >= numdict[x][mid]:
            ok = mid
        else:
            ng = mid
    return ok

N = int(input())
A = list(map(int, input().split()))
Q = int(input())

numdict = {i:[-1] for i in range(1,N+1)}
for i in range(N):
    num = A[i]
    numdict[num].append(i)
for i in range(Q):
    l,r,x = map(int, input().split())
    L = bisect(x,l-1,len(numdict[x]))
    R = bisect(x,r-1,len(numdict[x]))
    print(R-L + (A[l-1] == x))