アルゴリズムの学習改善のための自身の備忘録及び学習の一環として記事を書くことにしました.
読んでくれた方で何かありましたら気兼ねなくコメントしてください.お待ちしております.
A - Lacked Number
問題文 概要
$0$~$9$の中に含まれていない整数は何か
制約と入力
制約
$S$ は数字のみからなる長さ $9$ の文字列である。
$S$ の文字はすべて相異なる。
入力
入力は以下の形式で標準入力から与えられる。
$S$
考察
全探索を用いて，含まない物を探索する．
$0$~$9$まですべてから探索する．
サンプルコード
s=set(list(input()))
ans=-1
for i in range(10):
if str(i) in s:
continue
ans=i
print(ans)
B - Slimes
問題文 概要
$A$が$B$を超えるまで$k$倍を続ける．
何回操作したのかを求める．
制約と入力
制約
$1\leq A \leq B \leq 10^9$
$2\leq K \leq 10^9$
入力は整数。
入力
入力は以下の形式で標準入力から与えられる。
$A \ B \ K$
考察
$A<B$である限り$A=A\times K$を繰り返し続ける．
$A\geq B$となるまでに行った操作回数が答えとなる
サンプルコード
A,B,K=map(int,input().split())
for i in range(10**9):
if A>=B:
print(i)
exit()
else:
A*=K
C - Dice Sum
問題文 概要
数列$A=(A_0,...,A_N)$に対して各要素は$1\leq A_i \leq M$である．
$$\sum_{i=1}^N A_i\leq K$$となる数列の取り方は何通りあるか
制約と入力
制約
$1\leq N,M \leq 50$
$N \leq K \leq NM$
入力は全て整数
入力
$N \ M \ K$
考察
動的計画法を用いて考える．
$dp[n][sum]$として，｢$n$の時の総和｣の取り得る数列の数を保存する．
この時，$nex=(1,2,...,M)$とすると$n+1$の時，$sum+nex$が総和として遷移される
遷移として具体的に
$dp[i+1][sum+nex]=dp[i][sum]$となる
$n$は固定なので$dp[n]$の時の総和が答えとなる．
サンプルコード
n,m,K=map(int,input().split())
MOD=998244353
dp=[[0 for _ in range(K+1)] for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
for j in range(K+1):
for k in range(1,m+1):
if j+k>K:
continue
dp[i+1][j+k]+=dp[i][j]
dp[i+1][j+k]%=MOD
print(sum(dp[-1])%MOD)
D - Cylinder
問題文 概要
数列$A=(A_1,A_2,...,A_N)$に対して$(A_L,...,A_R)$に$x$はいくつあるか
数列$A$は固定であるが，$L,R,X$は変動するなかでそれぞれで求める
制約と入力
制約
$1\leq N \leq 2 \times 10^5$
$1 \leq A_i \leq N$
$1\leq Q \leq 2 \times 10^5$
各クエリについて$1\leq L \leq R \leq N,1\leq X \leq N$
入力は全て整数
入力
$N$
$A_1 \ A_2 \ \dots \ A_N$
$Q$
$Query_1$
$Query_2$
$\vdots$
$Query_N$
$Query_i$は各クエリを表す．
各クエリ
$L \ R \ X$
考察
愚直に各クエリを数列$A$から探索すると計算回数は$N^Q$必要となり，間に合わない．
前計算として，$A_i$のインデックスを管理した連想配列を準備する．
各値毎にインデクスを昇順に保持する．
連想配列の$X$の値の時の配列に$L,R$を挿入する．
挿入するインデックスを比較すると答えは求まる．
サンプルコード
import bisect
n=int(input())
a=list(map(int,input().split()))
cnt=dict()
cnt_set=set()
for i in range(n):
if a[i] in cnt_set:
cnt[a[i]].append(i+1)
else:
cnt[a[i]]=[i+1]
cnt_set.add(a[i])
q=int(input())
for i in range(q):
l,r,x=map(int,input().split())
if x not in cnt_set:
print(0)
continue
else:
L=bisect.bisect_left(cnt[x],l)
R=bisect.bisect_right(cnt[x],r)
print(R-L)