本記事は拙著『AtCoder 最速で緑になる基礎・典型50問詳細解説』のコピペ用コード集ですです。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP

【booth(pdf)】
https://booth.pm/ja/items/4102300

冒頭5問をサンプルとして無料公開しています。
https://qiita.com/sano192/items/6361ed72106cb6dd5843

1 入力と出力 ABC205 A Dif:6

提出

# 入力の受け取り
A,B=map(int, input().split())

# A×(1/100)×Bを出力
print(A*(1/100)*B)

2 条件分岐1 ABC219 A Dif:6

提出

# 入力の受け取り
X=int(input())

# 初級の場合
if 0<=X<40:
    # 40-Xを出力
    print(40-X)
# 中級の場合
elif 40<=X<70:
    # 70-Xを出力
    print(70-X)
# 上級の場合
elif 70<=X<90:
    # 90-Xを出力
    print(90-X)
# エキスパートの場合
else:
    # "expert"を出力
    print("expert")

3 関数 ABC234 A Dif:7

提出

# 入力の受け取り
t=int(input())

# 関数の定義
# 引数；x　返り値：x^2+2x+3
def f(x):
    return x**2+2*x+3

# 答えの計算
ans=f(f(f(t)+t)+f(f(t)))

# 答えの出力
print(ans)

4 for文 ABC204 B Dif:9

提出

# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))

# 答え
ans=0

# i=0~N-1まで
for i in range(N):
    # A[i]が10より大きければ
    if 10<A[i]:
        # A[i]-10をansにプラスする
        ans+=A[i]-10

# 答えの出力
print(ans)

別解

# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))

# 答えの格納用変数
ans=0

# xへAの値を順に入れる
for x in A:
    # 0と(x-10)の大きい方を足す
    ans+=max(0,x-10)

# 答えの出力
print(ans)

5 文字列操作 ABC232 A Dif:9

提出

# 入力の受け取り
S=input()

# Sの0文字目と2文字目を整数へ変換
S0=int(S[0])
S2=int(S[2])

# 掛け算して出力
print(S0*S2)

6 文字コード変換 ABC218 B Dif:14

提出

# 入力の受け取り
P=list(map(int, input().split()))

# 答えを格納する変数
ans=""

# i=0~25
for i in range(26):
    # 文字コード「P[i]+96」の文字をansの末尾へ追加
    ans+=chr(P[i]+96)

# 答えを出力
print(ans)

別解

# 入力の受け取り
P=list(map(int, input().split()))

def convert(x):
    if x==1:return "a"
    if x==2:return "b"
    if x==3:return "c"
    if x==4:return "d"
    if x==5:return "e"
    if x==6:return "f"
    if x==7:return "g"
    if x==8:return "h"
    if x==9:return "i"
    if x==10:return "j"
    if x==11:return "k"
    if x==12:return "l"
    if x==13:return "m"
    if x==14:return "n"
    if x==15:return "o"
    if x==16:return "p"
    if x==17:return "q"
    if x==18:return "r"
    if x==19:return "s"
    if x==20:return "t"
    if x==21:return "u"
    if x==22:return "v"
    if x==23:return "w"
    if x==24:return "x"
    if x==25:return "y"
    if x==26:return "z"

ans=""

# i=0~25
for i in range(26):
    # P[i]を変換してansの末尾へ追加
    ans+=convert(P[i])

# 答えを出力
print(ans)

7 リスト操作 ABC241 A Dif:15

提出

# 入力の受け取り
a=list(map(int,input().split()))

# 最初に画面に表示されているのは「0」
k=0

# ボタンを押す
k=a[k]

# ボタンを押す
k=a[k]

# ボタンを押す
k=a[k]

# 答えを出力
print(k)

8 set ABC240 B Dif:19

提出

# 入力の受け取り
N=int(input())
a=list(map(int,input().split()))

# リスト→セットへ変換
aSet=set(a)

# 長さを出力
print(len(aSet))

9 図形 ABC246 A Dif:28

提出

# 入力の受け取り
x1,y1=map(int,input().split())
x2,y2=map(int,input().split())
x3,y3=map(int,input().split())

# x1=x2の場合
if x1==x2:
    x4=x3
# x2=x3の場合
elif x2==x3:
    x4=x1
# x3=x1の場合
elif x3==x1:
    x4=x2

# y1=y2の場合
if y1==y2:
    y4=y3
# y2=y3の場合
elif y2==y3:
    y4=y1
# y3=y1の場合
elif y3==y1:
    y4=y2

# 答えの出力
print(x4,y4)

10 二次元配列、ソート1 ABC201 B Dif:32

提出

# 入力の受け取り
N=int(input())

# 山の高さ、名前を格納するリスト
Mountains=[]

# N回
for i in range(N):
    # 入力の受け取り
    S,T=map(str, input().split())
    # Tを整数へ変換
    T=int(T)
    # T,Sの順に格納
    Mountains.append([T,S])

# 大きい順に並び替え
Mountains.sort(reverse=True)

# 1番目のリストの、1番目の要素を出力
print(Mountains[1][1])

11 二重ループ ABC234 B Dif:46

提出

# 入力の受け取り
N=int(input())

# 座標の格納用
x=[]
y=[]

# i=0~(N-1)
for i in range(N):
    # 入力の受け取り
    xi,yi=map(int,input().split())
    # 座標の格納
    x.append(xi)
    y.append(yi)

# mathのインポート
import math

# 答え
ans=0

# i=0~(N-1)
for i in range(N):
    # j=(i+1)~(N-1)
    for j in range(i+1,N):
        # 距離の計算
        length=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
        # そこまでの値より大きければ更新
        ans=max(ans,length)

# 答えの出力
print(ans)

12 条件分岐2 ABC205 C Dif:63

提出

# 入力の受け取り
A,B,C=map(int, input().split())

# C：偶数
if C%2==0:
    # A：0以上(+)
    if 0<=A:
        # B：0以上(+)
        if 0<=B:
            # |A|<|B|
            if abs(A)<abs(B):
                # 「<」を出力
                print("<")
            # |A|=|B|
            if abs(A)==abs(B):
                # 「=」を出力
                print("=")
            # |A|>|B|
            if abs(A)>abs(B):
                # 「>」を出力
                print(">")
        # B：0未満(-)
        if B<0:
            # |A|<|B|
            if abs(A)<abs(B):
                # 「<」を出力
                print("<")
            # |A|=|B|
            if abs(A)==abs(B):
                # 「=」を出力
                print("=")
            # |A|>|B|
            if abs(A)>abs(B):
                # 「>」を出力
                print(">")

    # A：0未満(-)
    if A<0:
        # B：0以上(+)
        if 0<=B:
            # |A|<|B|
            if abs(A)<abs(B):
                # 「<」を出力
                print("<")
            # |A|=|B|
            if abs(A)==abs(B):
                # 「=」を出力
                print("=")
            # |A|>|B|
            if abs(A)>abs(B):
                # 「>」を出力
                print(">")
        # B：0未満(-)
        if B<0:
            # |A|<|B|
            if abs(A)<abs(B):
                # 「<」を出力
                print("<")
            # |A|=|B|
            if abs(A)==abs(B):
                # 「=」を出力
                print("=")
            # |A|>|B|
            if abs(A)>abs(B):
                # 「>」を出力
                print(">")

# C：奇数
if C%2==1:
    # A：0以上(+)
    if 0<=A:
        # B：0以上(+)
        if 0<=B:
            # |A|<|B|
            if abs(A)<abs(B):
                # 「<」を出力
                print("<")
            # |A|=|B|
            if abs(A)==abs(B):
                # 「=」を出力
                print("=")
            # |A|>|B|
            if abs(A)>abs(B):
                # 「>」を出力
                print(">")
        # B：0未満(-)
        if B<0:
            # |A|<|B|
            if abs(A)<abs(B):
                # 「>」を出力
                print(">")
            # |A|=|B|
            if abs(A)==abs(B):
                # 「>」を出力
                print(">")
            # |A|>|B|
            if abs(A)>abs(B):
                # 「>」を出力
                print(">")

    # A：0未満(-)
    if A<0:
        # B：0以上(+)
        if 0<=B:
            # |A|<|B|
            if abs(A)<abs(B):
                # 「<」を出力
                print("<")
            # |A|=|B|
            if abs(A)==abs(B):
                # 「<」を出力
                print("<")
            # |A|>|B|
            if abs(A)>abs(B):
                # 「<」を出力
                print("<")
        # B：0未満(-)
        if B<0:
            # |A|<|B|
            if abs(A)<abs(B):
                # 「>」を出力
                print(">")
            # |A|=|B|
            if abs(A)==abs(B):
                # 「=」を出力
                print("=")
            # |A|>|B|
            if abs(A)>abs(B):
                # 「<」を出力
                print("<")

別解

A,B,C=map(int, input().split())

if C%2==0:
    if abs(A)<abs(B):print("<")
    elif abs(A)==abs(B):print("=")
    else:print(">")
else:
    if 0<=A:
        if 0<=B:
            if abs(A)<abs(B):print("<")
            elif abs(A)==abs(B):print("=")
            else:print(">")
        else:print(">")
    else:
        if 0<=B:print("<")
        else:
            if abs(A)<abs(B):print(">")
            elif abs(A)==abs(B):print("=")
            else:print("<")

13 周期性 ABC220 C Dif:119

提出

# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
X=int(input())

# Aの合計
Asum=sum(A)

# 必要なAの数：X//(Aの合計)
quo=X//Asum

# 項数(k)：(Aの個数)×(Aの要素数)
k=N*quo

# 合計(Bsum)：(Aの個数)×(Aの合計)
Bsum=Asum*quo

# Xを超えるまでAの要素を順に足していく
# i=0~(N-1)まで
for i in range(N):
    # 合計に+A[i]
    Bsum+=A[i]
    # 項数に+1
    k+=1
    # X<合計になったら
    if X<Bsum:
        # 答えを出力
        print(k)
        # 終了
        exit()

14 逆順操作 ABC216 C Dif:145

提出

# 入力の受け取り
N=int(input())

# 答え(最初は空)
ans=""

# Nが0より大きい間
while 0<N:
    # Nが偶数なら
    if N%2==0:
        # ansの左端にBを追加
        ans="B"+ans
        # 2で割る
        N//=2
    # それ以外(Nが奇数なら)
    else:
        # ansの左端にAを追加
        ans="A"+ans
        # 1を引く
        N-=1

# 答えを出力
print(ans)

15 貪欲法 ABC229 C Dif:165

提出

# 入力の受け取り
N,W=map(int,input().split())

# チーズの情報
Cheese=[]

# N回
for i in range(N):
    # 入力の受け取り
    A,B=map(int,input().split())
    # 情報の格納
    Cheese.append([A,B])

# 美味しさの大きい順にソート
Cheese.sort(reverse=True)

# 答え
ans=0

# i=0～(N-1)まで
for i in range(N):
    # i種類目のチーズの美味しさ
    Delicious=Cheese[i][0]
    # i種類目のチーズの重さ
    Weight=Cheese[i][1]

    # 重さ≤Wなら
    if Weight<=W:
        # 全部載せる
        ans+=Delicious*Weight
        # 載せられる残りの重さ
        W-=Weight
    # そうでないなら(W<重さなら)
    else:
        # W[g]分載せる
        ans+=Delicious*W
        # これ以上載せられないからforを抜ける
        break

# 答えの出力
print(ans)

16 インタラクティブ ABC244 C Dif:165

提出

# 入力の受け取り
N=int(input())

# すでに使った数の記録
Used=[False]*(2*N+2)

# 最初は「1」を出力
print(1)

# 「1」は使用済み
Used[1]=True

# N回
for i in range(N+1):
    # 青木くんの入力を受け取り
    x=int(input())
    # 「x」は使った
    Used[x]=True

    # x=「0」の場合
    if x==0:
        # 終了
        exit()

    # k=1~(2k+1)
    for k in range(1,2*N+2):
        # まだ使っていないなら
        if Used[k]==False:
            # 「k」を出力
            print(k)
            # 「k」は使った
            Used[k]=True
            # forループを抜ける
            break

17 連想配列1 ABC206 C Dif:171

提出

# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))

# defaultdictのインポート
from collections import defaultdict

# 要素の出現回数を数える連想配列countを用意
count=defaultdict(int)

# Aのそれぞれの要素(a)について
for i in range(N):
    # 出現回数を+1
    count[A[i]]+=1

# 全組み合わせ=NC2=N*(N-1)//2
ans=N*(N-1)//2

# countの値(x)それぞれについて
for x in count.values():
    # Ai=Ajとなる組の数x*(x-1)//2を引く
    ans-=x*(x-1)//2

# 答えの出力
print(ans)

18 itertools ABC215 C Dif:178

提出

# 入力の受け取り(Kも文字列として)
S,K=map(str,input().split())

# Kを整数に変換
K=int(K)

# 作れる文字を格納するセット(リストだと重複するものも入ってしまうためセットを使う)
Sset=set()

# itertoolsをインポート
import itertools
# p=(0,1,2),(0,2,1),(1,0,2),(1,2,0),...
for p in itertools.permutations(range(len(S))):
    # 作った文字列を記録する変数
    Stmp=""
    # pを使って文字を作成
    # 例：p=(2,0,1)ならStmp=Sの2文字目+Sの0文字目+Sの1文字目
    for i in p:
        Stmp+=S[i]
    # できた文字をSsetに格納(setへの追加はappendではなくaddであることに注意)
    Sset.add(Stmp)

# ソートするためにリストへ変換
Slist=list(Sset)

# 辞書順にソート
Slist.sort()

# K-1番目の要素を出力
print(Slist[K-1])

19 二分探索1 ABC231 C Dif:194

提出

# 入力の受け取り
N,Q=map(int,input().split())
A=list(map(int,input().split()))

# Aをソート
A.sort()

# 二分探索
# 引数：x 返り値：「身長がx以上の中で最も小さい人は何番目か」
def Nibutan(x):
    # 左端
    l=0
    # 右端
    r=N-1

    # 1<右端-左端の間
    while 1<r-l:
        # 中央
        c=(l+r)//2

        # A[c]<xならば(条件を満たさない場合)
        if A[c]<x:
            # 左端を中央へ更新
            l=c
        # そうでなければ(x≤A[c] 条件を満たす場合)
        else:
            # 右端を中央へ更新
            r=c
       
    # 右端を返す
    return r

# Q回
for i in range(Q):
    # 入力の受け取り
    x=int(input())

    # xがAの中で最小の要素以下である場合
    if x<=A[0]:
        # N人
        print(N)
    # xがAの中で最大の要素より大きい場合
    elif A[N-1]<x:
        print(0)
    # それ以外
    else:
        # 答えの出力
        print(N-Nibutan(x))

別解

# 入力の受け取り
N,Q=map(int,input().split())
A=list(map(int,input().split()))

# Aをソート
A.sort()

# クエリの記録
query=[]

# Q回
for i in range(Q):
    # 入力の受け取り
    x=int(input())
    # [x,i番目のクエリ]と記録
    query.append([x,i])

# クエリをxの小さい順にソート
query.sort()
# 答えの格納用リスト
Ans=[0]*Q

# インデックス：初期値は0
k=0
# 各クエリについて
for x,i in query:
 
    # A[k]<xである限り
    while k<N and A[k]<x:
        # kを先に進める
        k+=1

    # A[k]はx以上
    # i番目のクエリの答えを記録
    Ans[i]=N-k

# 答えの出力
for a in Ans:print(a)

20 ソート2 ABC209 C Dif:285

提出

# 入力の受け取り
N=int(input())
C=list(map(int, input().split()))

# mod=10^9+7と定義
mod=10**9+7

# Cをソート
C.sort()

# 答えを格納する変数
ans=1

# i=0~(N-1)まで
for i in range(N):
    # もしC[i]-i=0ならば
    if C[i]-i==0:
        # 0を出力
        print(0)
        # 終了
        exit()

    # ansにC[i]-iをかける
    ans*=C[i]-i
    # 余りを取る
    ans%=mod

# 答えを出力
print(ans)

21 シミュレーション1 ABC214 C Dif:319

提出

# 入力の受け取り
N=int(input())
S=list(map(int, input().split()))
T=list(map(int, input().split()))

# i番目のすぬけ君が初めて宝石をもらう時間
# 初期値は大きい数
time=[10**15]*N

# 1週目
for i in range(N):
    # 次のすぬけ君の番号。i=N-1のとき、次のすぬけ君の番号=Nではなく=0とするためNで割った余りを取る
    next=(i+1)%N
    # 高橋君からもらうのが早いか、隣のすぬけ君からもらうのが早いか
    time[next]=min(T[next],time[i]+S[i])

# 2周目
for i in range(N):
    next=(i+1)%N
    # 1周目で計算した時間が早いか、隣のすぬけ君からもらうのが早いか
    time[next]=min(time[next],time[i]+S[i])

# 答えの出力
for i in range(N):
  print(time[i])

22 bit全探索 ABC221 C Dif:379

提出

# 入力の受け取り(文字列)
N=input()

# 答え 初期値は0
ans=0

# bitnum=(000000),(000001),(000010),(000011),...,(111111)まで
for bitnum in range(1<<len(N)):
    # グループA,Bを用意
    A=[]
    B=[]

    # shift=0~(Nの桁数-1)まで
    for shift in range(len(N)):
    # bitnumのshift桁目が「0」か「1」か確認
    # 右にshift分シフト演算して「1」とアンド演算
        # 0ならば
        if bitnum>>shift & 1==0:
            # グループAへ追加
            A.append(N[shift])
        # 1ならば
        else:
            # グループBへ追加
            B.append(N[shift])

    # グループAまたはグループBが空なら
    if A==[] or B==[]:
        # 次のbitnum
        continue

    # 大きい順に並び替え
    A.sort(reverse=True)
    B.sort(reverse=True)

    # A,Bを結合
    A_join="".join(A)
    B_join="".join(B)
 
    # 整数にして掛け算
    tmp_ans=int(A_join)*int(B_join)
 
    # ansよりtmp_ansが大きかったらansを更新
    ans=max(ans,tmp_ans)

# 答えの出力
print(ans)

23 区間の処理 ABC207 C Dif:397

提出

# 入力の受け取り
N=int(input())

# 区間の格納リスト
section=[]

# N回
for i in range(N):
    # 入力の受け取り
    t,l,r=map(int, input().split())
    # t=1の場合
    if t==1:
        # 区間[l,r]を追加
        section.append([l,r])
    # t=2の場合
    elif t==2:
        # 区間[l,r-0.1]を追加
        section.append([l,r-0.1])
    # t=3の場合
    elif t==3:
        # 区間[l+0.1,r]を追加
        section.append([l+0.1,r])
    # t=4の場合
    elif t==4:
        # 区間[l+0.1,r-0.1]を追加
        section.append([l+0.1,r-0.1])

# 答えの格納用変数
ans=0

# i=0~(N-1)まで
for i in range(N):
    # j=(i+1)~(N-1)まで
    for j in range(i+1,N):
        # 区間iの左端
        il=section[i][0]
        # 区間iの右端
        ir=section[i][1]
        # 区間jの左端
        jl=section[j][0]
        # 区間jの右端
        jr=section[j][1]

        # (区間iの左端)≤(区間jの左端)≤(区間iの右端)
        if il<=jl<=ir:
            # 答えにカウント
            ans+=1
        # (区間iの左端)≤(区間jの右端)≤(区間iの右端)
        elif il<=jr<=ir:
            # 答えにカウント
            ans+=1        
        # (区間jの左端)≤(区間iの左端)≤(区間jの右端)
        elif jl<=il<=jr:
            # 答えにカウント
            ans+=1        
        # (区間jの左端)≤(区間iの右端)≤(区間jの右端)
        elif jl<=ir<=jr:
            # 答えにカウント
            ans+=1

# 答えの出力
print(ans)

別解

# 入力の受け取り
N=int(input())

# 区間の格納リスト
section=[]

# N回
for i in range(N):
    # 入力の受け取り
    t,l,r=map(int, input().split())
    # t=1の場合
    if t==1:section.append([l,r])
    # t=2の場合
    elif t==2:section.append([l,r-0.1])
    # t=3の場合
    elif t==3:section.append([l+0.1,r])
    # t=4の場合
    else:section.append([l+0.1,r-0.1])

# 答えの格納用変数
ans=0

# i=0~(N-1)まで
for i in range(N):
    # j=(i+1)~(N-1)まで
    for j in range(i+1,N):
        # 区間i,jの右端,左端
        il,ir=section[i]
        jl,jr=section[j]
      
        # max(区間iの左端,区間jの左端)≤min(区間iの右端,区間jの右端)ならば
        # 答えにカウント
        if max(il,jl)<=min(ir,jr):ans+=1

# 答えの出力
print(ans)

24 座標圧縮 ABC213 C Dif:481

提出

# 入力の受け取り
H,W,N=map(int, input().split())

# カードの[行番号,列番号]を受け取るリスト
cards=[]
# 行番号だけ受け取るリスト
Gyou=[]
# 列番号だけ受け取るリスト
Retu=[]

# N回
for i in range(N):
    # 入力の受け取り
    A,B=map(int, input().split())
    # カードの[行番号,列番号]を受け取り
    cards.append([A,B])
    # 行番号を受け取り
    Gyou.append(A)
    # 列番号を受け取り
    Retu.append(B)

# 重複の削除(setにする)
Gyou=set(Gyou)
# リストに直す(setはソートできない)
Gyou=list(Gyou)
# ソートする
Gyou.sort()

# 変換先を記録する連想配列
GyouConvert=dict()

# 重複削除後の行の個数分
for i in range(len(Gyou)):
    # もとの行番号→インデックス番号+1と変換できるように記録(小さい方から何番目にあるか？)
    GyouConvert[Gyou[i]]=i+1

#列も同じことをする
Retu=set(Retu)
Retu=list(Retu)
Retu.sort()

RetuConvert=dict()

for i in range(len(Retu)):
    RetuConvert[Retu[i]]=i+1

# それぞれのカードについて行、列番号を変換して出力
for Gyou,Retu in cards:
    # 行番号の変換
    AnsGyou=GyouConvert[Gyou]
    # 列番号の変換
    AnsRetu=RetuConvert[Retu]
    # 答えを出力する
    print(AnsGyou,AnsRetu)

25 heap ABC234 D Dif:503

提出

# 入力の受け取り
N,K=map(int,input().split())
P=list(map(int,input().split()))

# heapqのインポート
import heapq

# (1)heap queueを用意する
que=[]
 
# (2)P1~PKをheap queueへ入れる
for i in range(K):
    heapq.heappush(que,P[i])

# (3)heap queueの最小値を出力する
print(que[0])

# i=K~(N-1)
for i in range(K,N):
    # (4)heap queueから最小値を取り出す
    x=heapq.heappop(que)
    # (5)(heap queueの最小値)とPiのうち大きい方をheap queueへ戻す
    heapq.heappush(que,max(x,P[i]))
    # (6)(heap queueの最小値)を出力する
    print(que[0])
    # (7)次のiへ((4)へ戻る)

26 deque ABC237 D Dif:544

提出

# 入力の受け取り
N=int(input())
S=input()

# deque のインポート
from collections import deque

# キューを用意
que=deque()

# Nを追加
que.append(N)

# i=(N-1)~0 -1ずつ
for i in range(N-1,-1,-1):
    # Sのi文字目が「R｣
    if S[i]=="R":
        # 先頭(左端)へ「i」を追加
        que.appendleft(i)
    # そうでない場合(Sのi文字目が「L」)
    else:
        # 末端(右端)へ「i」を追加
        que.append(i)  

# 答えの出力
# ([]がいらない場合は先頭に「*」をつける)
print(*que)

27 DP1 ABC211 C Dif:559

提出

# 入力の受け取り
S=input()
# 文字数=N
N=len(S)

# Sの0文字目を?にする
S="?"+S
# T=?chokudai(?は0文字目)
T="?chokudai"

# 余りの定義
mod=10**9+7

# (1)表を作る
dp=[[0]*9 for i in range(N+1)]
 
# (2)すぐにわかるところを埋める
# i=0~N
for i in range(N+1):
    # k=0
    dp[i][0]=1

# (3)表の小さい方から答えにたどり着くまで埋める
# Sのi文字目までを使う
for i in range(1,N+1):
    # chokudaiのk文字目までを作る
    for k in range(1,9):
        # 1≤i≤N,1≤k≤8,Sのi文字目=chokudaiのk文字目の場合
        if S[i]==T[k]:
            # dp[i-1][k]：Sの(i-1)文字目までを使ってchokudaiのk文字目を作る場合(Sのi文字目を使わない)
            # dp[i-1][k-1]：Sの(i-1)文字目までを使ってchokudaiの(k-1)文字目を作る場合(Sのi文字目を使う)
            dp[i][k]=dp[i-1][k]+dp[i-1][k-1]
 
        # 1≤i≤N,1≤k≤8,Sのi文字目≠chokudaiのk文字目の場合
        else:
            # dp[i-1][k-1]：Sの(i-1)文字目までを使ってchokudaiの(k-1)文字目を作る場合(Sのi文字目を使う)
            dp[i][k]=dp[i-1][k]
                   
    # 余りを取る
    dp[i][k]%=mod

# SのN文字目までを使ってchokudaiの8文字目までを作る方法の数
print(dp[N][8])

28 全探索2 ABC233 C Dif:604

提出

# 入力の受け取り
N,X=list(map(int,input().split()))

# L,aの格納リスト
L=[]
a=[]

# N回
for i in range(N):
    # 一旦リストで受け取り
    tmp=list(map(int,input().split()))
    # リストの0番目=L
    L.append(tmp[0])
    # リストの1番目~=a
    a.append(tmp[1:])

# 全ての掛け算パターンの結果
Pro=[1]

# i=0~(N-1)
for i in range(N):
    # 一時的に結果を格納するリスト
    tmpPro=[]

    # i番目の袋のa全てについて
    for ai in a[i]:
        # ここまでの全ての掛け算パターンの結果
        for p in Pro:
            # 掛け算して格納
            tmpPro.append(ai*p)

    # ProをtmpProで更新
    Pro=tmpPro

# 結果がXとなったパターンを数える
ans=Pro.count(X)

# 答えを出力
print(ans)

29 BFS1 ABC204 C Dif:629

提出

# 入力の受け取り
N,M=map(int, input().split())

# 道路の情報を格納するリスト
connect=[[] for i in range(N+1)]

# M回受け取り
for i in range(M):
    # 入力の受け取り
    A,B=map(int, input().split())
    # connect[A]にBを追加
    # 都市1から都市2,3,4にいけるならconnect[1]=2,3,4
    connect[A].append(B)

# dequeをインポート
from collections import deque

# BFS
# 引数：スタート都市→返り値：スタート都市から行ける都市の数
def BFS(start):
    # 行ける都市を数える変数
    # スタート都市→スタート都市には必ず行けるから1
    count=1

    # 訪問済み都市のリスト
    # 訪問済みならTrue、未訪問ならFalse
    visited=[False]*(N+1)

    # スタート都市は訪問済みにする
    visited[start]=True

    # キューを用意
    que=deque()
    # キューへスタート都市を追加
    que.append(start)
  
    # キューが空になるまで
    while 0<len(que):
        # 今いる都市
        now=que.popleft()

        # 今いる都市から行ける都市を順にtoへ
        for to in connect[now]:
            # もしtoが未訪問なら
            if visited[to]==False:
                # countにプラス1
                count+=1

                # toを訪問済みにする
                visited[to]=True

                # キューへtoを追加
                que.append(to)

    # 行ける都市の数を返す
    return count

# 答えを格納する変数
ans=0

# x=1~N
for x in range(1,N+1):
    # xをスタート地点としたときに行ける都市の数を順に足し算
    ans+=BFS(x)

# 答えの出力
print(ans)

30 規則性利用 ABC238 C Dif:637

提出

# 余りを定義
mod=998244353

# 入力の受け取り
N=int(input())

# A~Bまでの和
# 引数：A,B→返り値：A~Bまでの和
def S(A,B):
    return (B-A+1)*(A+B)//2

# 答え
ans=0

# x~1~18
for x in range(1,19):
    # 10^x≤Nならば
    if 10**x<=N:
        # 「1~9*10**(x-1)までの和」
        ans+=S(1,9*10**(x-1))
        # 余りを取る
        ans%=mod
    # 10^(x-1)≤N<10^xならば
    else:
        # 「1～(N-10^(x-1)+1)までの和」
        ans+=S(1,N-10**(x-1)+1)
        # 余りを取る
        ans%=mod
        # forを抜ける
        break

# 答えの出力
print(ans)

31 全探索3 ABC227 C Dif:692

提出

# pypyで提出

# 入力の受け取り
N=int(input())

# 答えのカウント
ans=0

# 初期値
A=1
# A≤(Nの三乗根)⇔A^3≤Nの間
while A**3<=N:
    # 初期値
    B=A
    # B≤√(N/A)⇔A*B^2≤Nの間
    while A*B**2<=N:
        # ありうるCの個数=(N/AB)の切り捨て-B+1
        ans+=int(N/(A*B))-B+1
        # 次のBへ
        B+=1
    # 次のAへ
    A+=1

# 答えの出力
print(ans)

32 DFS1 ABC213 D Dif:710

提出

# 再帰回数上限。再帰関数を書くときは必ず最初に書くこと
import sys
sys.setrecursionlimit(10**6)

# 入力受け取り
N=int(input())

# 辺の情報格納
connect=[[] for i in range(N+1)]

# 辺の情報受け取り
for i in range(N-1):
    A,B=map(int, input().split())
    connect[A].append(B)
    connect[B].append(A)
# connect[1]=[2,3,4]ならば1と2,3,4がつながっている、というように確認できる

# 小さい順に回るからソート
for i in range(N+1):
    connect[i].sort()

# 答えの格納リスト
ans=[]

# DFS(今いる都市,前にいた都市)
def DFS(now,pre):
    # 今いる都市を答えに入れる
    ans.append(now)
    # to=今いる都市から行ける都市
    for to in connect[now]:
        # もしtoが前にいた都市と違うなら
        if to!=pre:
            # 更に先へ探索する
            DFS(to,now)
            # 戻ってきたら答えへ格納
            ans.append(now)

# 最初の都市=1,前にいた都市=-1(前にいた都市がないので存在しない番号)としてスタート
DFS(1,-1)

# 答えの出力
print(*ans)

33 連想配列2 ABC218 D Dif:715

提出

# 入力を受け取り
N=int(input())

# 座標の格納用リスト
points=[]

# defaultdictを用意 初期値は0
from collections import defaultdict
# (x,y)が存在したらp[(x,y)]=1
p=defaultdict(int)

# M行受け取り
for i in range(N):
    # x,yを受け取り
    x,y=map(int, input().split())
    # 座標をpointsへ格納
    points.append([x,y])
    # p[(x,y)]=1を記録
    p[(x,y)]=1

# 答えを格納する変数
ans=0

# p1=0~(N-1)
for p1 in range(N):
    # p2=(p1+1)~(N-1)
    for p2 in range(p1+1,N):
        # p1のx座標,y座標
        p1_x,p1_y=points[p1]
        # p1のx座標,y座標
        p2_x,p2_y=points[p2]
 
        # x座標またはy座標が同じ場合は
        if p1_x==p2_x or p1_y==p2_y:
            # 次の点へ
            continue
        # 座標(p1_x,p2_y)と座標(p2_x,p1_y)の点が存在すれば
        if p[(p1_x,p2_y)]==1 and p[(p2_x,p1_y)]==1:
            # 答えにプラス1
            ans+=1

# 二重に数えているので2で割る
ans//=2
# 答えを出力
print(ans)

34 UnionFind1 ATC B

提出

class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent_size=[-1]*n
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y]=x
    def same(self,a,b):
        return self.leader(a) == self.leader(b)
    def size(self,a):
        return abs(self.parent_size[self.leader(a)])
    def groups(self):
        result=[[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]
 
# 入力の受け取り
N,Q=map(int,input().split())
 
# UnionFindを用意
UF=UnionFind(N+1)
 
# Q回
for i in range(Q):
    # 入力の受け取り
    P,A,B=map(int,input().split())
 
    # P=0の場合
    if P==0:
        # A,Bを連結
        UF.merge(A,B)
   
    # P=1の場合
    else:
        # A,Bが連結なら
        if UF.same(A,B):
            # 「Yes」を出力
            print("Yes")
        # 連結でないなら
        else:
            # 「No」を出力
            print("No")

35 UnionFind2 ABC231 D Dif:726

提出

class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent_size=[-1]*n
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y]=x
    def same(self,a,b):
        return self.leader(a) == self.leader(b)
    def size(self,a):
        return abs(self.parent_size[self.leader(a)])
    def groups(self):
        result=[[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

# 入力の受け取り
N,M=map(int,input().split())

# UnionFind 初期化
UF=UnionFind(N+1)

# 辺の本数をカウント
count=[0]*(N+1)

# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int,input().split())

    # 辺の本数をカウント
    count[A]+=1
    count[B]+=1
   
    # 辺の本数が3本以上なら
    if 3<=count[A] or 3<=count[B]:
        # 「No」を出力
        print("No")
        # 終了
        exit()

    # A,Bが連結の場合
    if UF.same(A,B)==True:
        # 「No」を出力
        print("No")
        # 終了
        exit()

    # そうでなければ(連結出ない場合)
    else:
        # A,Bに辺を張る(連結する)
        UF.merge(A,B)

# 「Yes」を出力
print("Yes")

別解

# 再帰回数上限。再帰関数を使うときは必ず最初に書くこと
import sys
sys.setrecursionlimit(10**6)

# 入力の受け取り
N,M=map(int,input().split())

# つながっている頂点の記録
Connect=[[] for i in range(N+1)]

# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int,input().split())

    # A→B、B→Aへ行ける
    Connect[A].append(B)
    Connect[B].append(A)
 
    # 辺の本数が3本以上なら
    if 3<=len(Connect[A]) or 3<=len(Connect[B]):
        # 「No」を出力
        print("No")
        # 終了
        exit()

# まだ訪問済みでない頂点
visited=[False]*(N+1)

# DFS(今いる頂点、直前にいた頂点)
def DFS(Now,Pre):
    # 今いる頂点を訪問済みにする
    visited[Now]=True

    # to=Nowから行ける頂点
    for to in Connect[Now]:
        # 直前にいた頂点でなければ
        if to!=Pre:
            # 訪問済みでなければ
            if visited[to]==False:
                # 次のDFSを開始
                DFS(to,Now)
            # 訪問済みであれば
            # ⇔ループになった
            else:
                # 「No」を出力
                print("No")
                # 終了
                exit()                

# i=1~N
for i in range(1,N+1):
    # 訪問済みでなければ
    if visited[i]==False:
        # DFSを開始
        # (直前にいた頂点はないので0にしておく)
        DFS(i,0)

# 「Yes」を出力
print("Yes")

36 尺取法1、区間和 ABC229 D Dif:745

提出

# 入力の受け取り
S=input()
K=int(input())

S="?"+S

# Sの長さ
N=len(S)

# 「.」の累積個数
Count=[0]*N

# i=1~(N-1)
for i in range(1,N):
    # S[i]=「X」ならば
    if S[i]=="X":
        # 一つ左と同じ
        Count[i]=Count[i-1]
    # そうでないなら(S[i]=「.」)
    else:
        # 一つ左+1
        Count[i]=Count[i-1]+1

# 答え
ans=0

# 右
r=1

# l=1~(N-1)
for l in range(1,N):
    # r<Nの間
    while r<N:
        # [左,右]にある「.」の数=Count[r]-Count[l-1]
        Period=Count[r]-Count[l-1]

        # [左,右]にある「.」の数≤Kならば
        # ⇔[左,右]にある「.」を全て「X」に変えられるなら
        if Period<=K:
            # 右を移動
            r+=1
        # そうでないなら([左,右]にある「.」を全て「X」に変えられないなら)
        else:
            # whileを抜ける
            break

    # [左,右-1]の長さを計算し、今までの答えより大きければ更新
    ans=max(ans,r-l)

# 答えの出力
print(ans)

37 BFS2 ABC211 D Dif:755

提出

# 入力の受け取り
N,M=map(int, input().split())

# 道路の情報を格納する変数
connect=[[] for i in range(N+1)]
# 道路の情報を受け取って格納
for i in range(M):
    A,B=map(int, input().split())
    connect[A].append(B)
    connect[B].append(A)

# 余りの定義
mod=10**9+7

# まだ到達していない都市の移動時間(infinity：無限大)
# 大きめの数にする
inf=10**15

# (1)各都市の最短移動時間を記録するリストtimeを作る(初期値は大きな数)
time=[inf]*(N+1)
# 都市①の最短移動時間は「0」
time[1]=0

# (2)各都市にたどり着くまでの経路数を記録するリストcountを作る
count=[0]*(N+1)
# 都市①に行く経路数は「1」
count[1]=1

# (3)キューを用意
from collections import deque
que=deque()
# キューに都市①を入れる
que.append(1)

# (6)(4)~(5)をキューが空になるまで繰り返す
while 0<len(que):
    # (4)キューの左端から要素(都市の番号)を取り出す(今いる街)
    now=que.popleft()

    # (5)今いる都市から行ける都市を確認する
    # nowから行ける都市を順にtoへ格納
    for to in connect[now]:
        # もし行ける都市の移動時間がinfならば(まだ更新されていない)
        if time[to]==inf:
            # (5-1)「経路数」=「今いる都市の経路数」
            count[to]=count[now]
            # (5-2)「最短移動時間」=「今いる都市の最短移動時間+1」
            time[to]=time[now]+1
            # (5-3)キューに追加
            que.append(to)

        # そうでないなら(移動時間が更新済み)
        else:
            # 「最短移動時間」=「今いる都市の最短移動時間+1」(最短経路)ならば
            if time[to]==time[now]+1:
                # (5-4)「経路数」+=「今いる都市の経路数」
                count[to]+=count[now]

        # 余りを取る
        count[to]%=mod

# (7)答えを出力する
# Nが未到達であれば(「最短移動時間」が更新されていなければ)
if time[N]==inf:
    # たどり着けないため「0」を出力
    print(0)
  
# そうでないならば
else:
    # count[N]を出力
    print(count[N])

38 シミュレーション2 ABC243 D Dif:758

提出

# 入力の受け取り
N,X=map(int,input().split())
S=input()

# 移動の記録
Move=[]

# i=0~(N-1)
for i in range(N):
    # ・記録が空の場合
    if len(Move)==0:
        # S[i]を記録
        Move.append(S[i])
   
    # ・記録が空でない場合
    else:
        # ・S[i]が「L」または「R」
        if S[i]=="L" or S[i]=="R":
            # S[i]を記録
            Move.append(S[i])
        # ・S[i]が「U」
        else:
            # ・S[i]が「U」かつ記録の末尾が「L」または「R」(「LU」「RU」になる場合)
            if Move[-1]=="L" or Move[-1]=="R":
                # 記録の末尾を消す
                Move.pop()
            # ・S[i]が「U」かつ記録の末尾が「U」
            else:
                # 「U」を記録
                Move.append("U")

# シミュレーション
for s in Move:
    # 「L」ならば2Xへ移動
    if s=="L":
        X*=2
    # 「R」ならば(2X+1)へ移動
    elif s=="R":
        X=2*X+1
    # 「U」ならばX//2へ移動
    else:
        X//=2

# 答えの出力
print(X)

39 DP2 ABC248 C Dif:787

提出

# pypyで提出

# 入力の受け取り
N,M,K=map(int,input().split())

# 余りの定義
mod=998244353

# (1)表を作る
dp=[[0]*(K+1) for i in range(N+1)]

# (2)すぐにわかるところを埋める
# ・(x≤M)dp[1][x]=1
# ・(M<x)dp[1][x]=0
for x in range(1,M+1):
    dp[1][x]=1

# (3)表の小さい方から答えにたどり着くまで埋める
# i=2~N
for i in range(2,N+1):
    # x=1~K
    for x in range(1,K+1):
        # j=1~(x-1)
        for j in range(1,x):
            # ・(2≤i,1≤j≤x-1)x-j≤Mならばdp[i][x]+=dp[i-1][j]
            if x-j<=M:
                dp[i][x]+=dp[i-1][j]
                # 余りを取る
                dp[i][x]%=mod

# (4)答えを出力する
# 答え
ans=0

# x=1~K
for x in range(1,K+1):
    # dp[N][1]~dp[N][K]の和
    ans+=dp[N][x]
    # 余りを取る
    ans%=mod

# 答えを出力
print(ans)

40 二分探索2 ABC248 D Dif:793

提出

# pypyで提出
 
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# 1,2,3,...が何番目にあるかの記録 左端には「0」を入れておく
Aindx=[[0] for i in range(10**6)]
 
# i=0~(N-1)
for i in range(N):
    # インデックス番号を記録
    # 1インデックスなので「i+1」を記録することに注意
    Aindx[A[i]].append(i+1)
 
# i=0~(N-1)
for i in range(10**6):
    # 右端に∞=10^6を追加
    Aindx[i].append(10**6)
 
# Xがあるインデックス番号のうちL以上で最小のもの
def NibutanLeft(X,L):
    # (1)左=区間の最小、右=区間の最大とする
    # 左
    l=0
    # 右(=長さ-1)
    r=len(Aindx[X])-1
 
    # (4)1<(右-左)となっている間(2)~(4)を繰り返す
    while 1<r-l:
        # (2)中央=(左+右)//2が条件を満たすか確認
        # 中央=(左+右)//2
        c=(l+r)//2
 
        # (3)(2)の結果より左または右を更新する
        # ・(中央)番目の数がL以上
        if L<=Aindx[X][c]:
            # 左=中央と更新
            r=c
        # ・(中央)番目の数がLより小さい
        else:
            # 右=中央と更新
            l=c
 
    # 右を返す
    return r
 
# Xがあるインデックス番号のうちR以下で最大のもの
def NibutanRight(X,R):
    # (1)左=区間の最小、右=区間の最大とする
    # 左
    l=0
    # 右(=長さ-1)
    r=len(Aindx[X])-1
 
    # (4)1<(右-左)となっている間(2)~(4)を繰り返す
    while 1<r-l:
        # (2)中央=(左+右)//2が条件を満たすか確認
        # 中央=(左+右)//2
        c=(l+r)//2
 
        # (3)(2)の結果より左または右を更新する
        # ・(中央)番目の数がR以下
        if Aindx[X][c]<=R:
            # 左=中央と更新
            l=c
        # ・(中央)番目の数がRより大きい
        else:
            # 右=中央と更新
            r=c
 
    # 右を返す
    return l
 
# 入力の受け取り
Q=int(input())

# Q回
for i in range(Q):
    # 入力の受け取り
    L,R,X=map(int,input().split())
 
    # 「Xがあるインデックス番号のうちL以上で最小のもの」
    Lindx=NibutanLeft(X, L)
    # 「Xがあるインデックス番号のうちR以下で最大のもの」
    Rindx=NibutanRight(X, R)
    # 答えを出力
    print(Rindx-Lindx+1)

別解

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))

# 1,2,3,...が何番目にあるかの記録 左端には「0」を入れておく
Aindx=[[0] for i in range(10**6)]

# i=0~(N-1)
for i in range(N):
    # インデックス番号を記録
    # 1インデックスなので「i+1」を記録することに注意
    Aindx[A[i]].append(i+1)

# i=0~(N-1)
for i in range(10**6):
    # 右端に∞=10^6を追加
    Aindx[i].append(10**6)

# 入力の受け取り
Q=int(input())

# bisectをインポート
import bisect

# Q回
for i in range(Q):
    # 入力の受け取り
    L,R,X=map(int,input().split())

    # Lを大小関係を保ったままリストに挿入する位置のインデックス(同じ数があれば左側へ)
    Lindx=bisect.bisect_left(Aindx[X], L)
    # Rを大小関係を保ったままリストに挿入する位置のインデックス(同じ数があれば右側へ)
    Rindx=bisect.bisect_right(Aindx[X], R)
    # 答えを出力
    print(Rindx-Lindx)

41 尺取法2、エラトステネスの篩 ABC250 D Dif:797

提出

# エラトステネスの篩
def Eratosthenes(N):
    # 素数であるかの判定リスト
    IsPrime=[True]*(N+1)

    # i=2,3,4,...
    i=2
    # i≤√Nまで⇔i^2≤Nまで
    while i**2<=N:
        # iが素数でなければ
        if IsPrime[i]==False:
            # 次のiへ
            i+=1
            continue
       
        # k=2,3,4,...
        k=2
        while i*k<=N:
            # iの倍数は素数でない
            IsPrime[i*k]=False
            # 次のkへ
            k+=1

        # 次のkへ
        i+=1

    # 素数リスト
    PList=[]

    # i=2~N
    for i in range(2,N+1):
        # iが素数ならば
        if IsPrime[i]==True:
            # リストへ入れる
            PList.append(i)

    # リストを返す
    return PList

# 入力の受け取り
N=int(input())
# 10^6以下の素数リストを作成
P=Eratosthenes(10**6)

# 答え
ans=0

# 素数リストの長さ
lenP=len(P)

# 最後の素数の番号(0インデックス)
k=lenP-1

# i=0~(lenP-1)
for i in range(lenP):
 
    # p=i番目の素数(0インデックス)
    # q=k番目の素数(0インデックス)
    # p*q^3≤Nとなるまでkを減らしていく
    while i<k and N<P[i]*P[k]**3:
        k-=1

    # k≤iとなったら
    if k<=i:
        # 答えの出力
        print(ans)
        # 途中終了
        exit()

    # i+1,i+2,...,k番目の素数までqとして使用できる
    # ⇔(k-i)個
    ans+=k-i

別解

def Eratosthenes(N):
    IsPrime=[True]*(N+1)
 
    i=2
    while i**2<=N:
        if IsPrime[i]==False:
            i+=1
            continue
       
        k=2
        while i*k<=N:
            IsPrime[i*k]=False
            k+=1
 
        i+=1
 
    PList=[]
 
    for i in range(2,N+1):
        if IsPrime[i]==True:
            PList.append(i)
 
    return PList

# 入力の受け取り
N=int(input())
# 素数リストを作る
P=Eratosthenes(10**6)

# 素数リストの長さ
lenP=len(P)

# 二分探索
def Nibutan(i):
    # 左
    l=0
    # 右
    r=lenP-1

    # 1<(右-左)ならば
    while 1<(r-l):
        # 中央=(左+右)//2
        c=(l+r)//2

        # P[i]=i番目の素数
        # P[c]=c番目の素数
        # 条件を満たすなら
        if P[i]*P[c]**3<=N:
            # 左=中央と更新
            l=c
        # 条件を満たさないなら
        else:
            # 右=中央と更新
            r=c

    # 左を返す
    return l

# 答え
ans=0

# i=0~(素数リストの長さ-1)
for i in range(lenP):
    # P[i]*P[k]^3≤Nとなるもののうち最大のk
    k=Nibutan(i)
    # i<kならば
    if i<k:
        # (k-i)個プラス
        ans+=k-i
    # そうでないなら
    else:
        # 探索終了
        break

# 答えを出力
print(ans)

42 FenwickTree ACL B

提出

class FenwickTree:
    def __init__(self,N):
        self.N=N
        self.F=[0]*N
 
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.F[i-1]+=x
            i+=i&-i
 
    def sum_r(self,r):
        s=0
        while 0<r:
            s+=self.F[r-1]
            r-=r&-r
        return s
 
    def sum(self,l,r):
        return self.sum_r(r+1)-self.sum_r(l)
 
    def select(self,i):
        return self.sum(i,i)
 
# 入力の受け取り
N,Q=map(int,input().split())
a=list(map(int,input().split()))
 
# 長さ(N+1)のFenwickTreeを用意
# 初期値は全て0
FT=FenwickTree(N+1)
 
# i=0~(N-1)
for i in range(N):
    # i番目にa[i]を足す
    FT.add(i, a[i])
 
# Q回
for i in range(Q):
    # 入力の受け取り
    q,a,b=map(int,input().split())
 
    # q=0の場合
    if q==0:
        # a番目にbを足す(p番目にxを足す)
        FT.add(a, b)
    # q=1の場合
    else:
        # a~(b-1)番目の区間和を出力(l~(r-1)番目の区間和を出力)
        print(FT.sum(a, b-1))

43 想定解multiset ABC217 D Dif:802

提出

# 提出はpypyで行う

# Fenwick_Tree
class Fenwick_Tree:
    def __init__(self,n):
        self._n=n
        self.data=[0]*n
    def add(self,p,x):
        p+=1
        while p<=self._n:
            self.data[p-1] +=x
            p+=p&-p
    def _sum(self,r):
        s=0
        while 0<r:
            s+=self.data[r-1]
            r-=r&-r
        return s
    def sum(self,l,r):
        r+=1
        return self._sum(r)-self._sum(l)
    def select(self,p):
        return self.sum(p,p)

# 入力の受け取り
L,Q=map(int, input().split())

# クエリの記録用リスト
query=[]

# カットする場所を予め記録するリスト
cut=[]

# Q回
for i in range(Q):
    # 入力の受け取り
    c,x=map(int, input().split())
    # クエリを記録
    query.append([c,x])
    # c=1ならば
    if c==1:
        # cutに場所を記録
        cut.append(x)

# cutに「0」を追加
cut.append(0)
# cutに「L」を追加
cut.append(L)

# cutをソート
cut.sort()

# cutの長さをNとする
N=len(cut)

# x(カットする場所)→インデックス番号への変換
cut_index=dict()

# 変換表の作成
for i in range(N):
    cut_index[cut[i]]=i

# FenwickTreeの作成
Fenwick=Fenwick_Tree(N)

# 左端(0)に「1」を立てる(1を足す)
Fenwick.add(0,1)
# 右端(Lのインデックス番号)に「1」を立てる(1を足す)
Fenwick.add(N-1,1)

# xがどのインデックス番号の間にあるか確認する二分探索
# 引数：x→返り値：cut[l]<x<cut[r]を満たす最大のl、最小のr
def Nibutan_x(x):
    # 左(left)=0
    l=0
    # 右(right)=N-1
    r=N-1

    # 1<(右-左)の間
    while 1<r-l:
        # 中央(center)=(l+r)//2
        c=(l+r)//2
        # cut[c]<xなら
        if cut[c]<x:
            # 左=c
            l=c
        # x<cut[c]なら
        else:
            # 右端=c
            r=c

    # 左、右を返す
    return l,r

# xより左で1が立っている場所のうち、一番近いものを二分探索
# 引数：x→返り値：Fenwickの区間和[k~x]が1以上となるもののうち、最大のk
def Nibutan_l(x):
    # 左(left)=0
    l=0
    # 右(right)=x
    r=x

    # 1<(右-左)の間
    while 1<r-l:
        # 中央(center)=(l+r)//2
        c=(l+r)//2
        # 区間和[c~x]が1以上
        # ⇔区間c~xに「1」が1つ以上立っている
        if 1<=Fenwick.sum(c,x):
            # 左=中央
            l=c
        # 区間和[c~x]が1未満(=0)
        # ⇔区間c~xに「1」が立っていない
        else:
            # 右=中央
            r=c

    # 区間和[r~x]が1ならば
    if Fenwick.sum(r,x)==1:
        # rを返す
        return r
    # そうでなければ
    else:
        # lを返す
        return l

# xより右で1が立っている場所のうち、一番近いものを二分探索
# 引数：x→返り値：Fenwickの区間和[x~k]が1以上となるもののうち、最小のk
def Nibutan_r(x):
    # 左(left)=x
    l=x
    # 右(right)=N-1
    r=N-1

    # 1<(右-左)の間
    while 1<r-l:
        # 中央(center)=(l+r)//2
        c=(l+r)//2
        # 区間和[x~c]が1以上
        # ⇔区間x~cに「1」が1つ以上立っている
        if 1<=Fenwick.sum(x,c):
            # 右=中央
            r=c
        # 区間和[x~c]が1未満(=0)
        # ⇔区間x~cに「1」が立っていない
        else:
            # 左=中央
            l=c

    # 区間和[x~l]が1ならば
    if Fenwick.sum(x,l)==1:
        # lを返す
        return l
    # そうでなければ
    else:
        # rを返す
        return r

# クエリを読み込み
for c,x in query:
    # c=1の場合
    if c==1:
        # cut_index[i]の部分に「1」を立てる(+1する)
        Fenwick.add(cut_index[x],1)
    # c=2の場合
    else:
        # xがどのインデックス番号の間にあるか確認する二分探索
        l_x,r_x=Nibutan_x(x)
        # xより左で「1」が立っている場所のうち、一番近い場所のインデックス番号を二分探索
        l_index=Nibutan_l(l_x)
        # xより右で「1」が立っている場所のうち、一番近い場所のインデックス番号を二分探索
        r_index=Nibutan_r(r_x)
        # 右の値-左の値
        print(cut[r_index]-cut[l_index])

別解

import bisect
from array import array

# 入力の受け取り
L,Q=map(int,input().split())

# カット位置を記録するarray
# array(型コード,値)
cut=array("i",[0,L])

# Q回
for i in range(Q):
    # 入力の受け取り
    c,x=map(int,input().split())
    # c=1の場合
    if c==1:
        # xをx以上で最小の要素の次に挿入
        bisect.insort(cut,x)
    # それ以外(c=2の場合)
    else:
        # x以上で最小の要素のインデックス番号を取得
        index=bisect.bisect(cut,x)
        # 長さを出力
        print(cut[index]-cut[index-1])

44 DP3 ABC204 D Dif:832

提出

# pypyで提出

# 入力の受け取り
N=int(input())
# Tは先頭に[0]を追加して受け取り
T=[0]+list(map(int, input().split()))

# Tの合計
T_sum=sum(T)

# (1)表を作る
# 『i番目までの数を組み合わせてKを作れるか』
# 例：『3番目までの数を組み合わせて「7」を作れる』→ dp[3][7]=True
dp=[[False]*(T_sum+1) for i in range(N+1)]

# (2)すぐにわかるところを埋める
# 『0番目までの数を組み合わせて「0」を作れる
dp[0][0]=True

# (3)表の小さい方から答えにたどり着くまで埋める
# i=1~N
for i in range(1,N+1):
    # K=0~T_sum Kを作れるか確認
    for K in range(T_sum+1):
        # 『(i-1)番目までの数を組み合わせてKを作れる』(→dp[i-1][K]=True)ならば
        if dp[i-1][K]==True:
            # 『i番目までの数を組み合わせてKを作れる』(→dp[i][K]=True)
            dp[i][K]=True
        # 0<=K-T[i] かつ『(i-1)番目までの数を組み合わせてK-T[i]を作れる』ならば(dp[i-1][K-T[i]]=True)
        if 0<=K-T[i] and dp[i-1][K-T[i]]==True:
            # 『i番目までの数を組み合わせてKを作れる』(→dp[i][K]=True)            
            dp[i][K]=True

# 答えを格納する変数(初期値はバカでかい数)
ans=10**15

# (4)答えを出力する
# K=0~T_sum
for K in range(T_sum+1):
    # 『N番目までの数を組み合わせてKを作れる』ならば
    if dp[N][K]==True:
        # max(K,T_sum-K)が料理をすべて作るのにかかる時間=答えの候補
        # それまでのansより小さければ更新
        ans=min(ans,max(K,T_sum-K))

# 答えの出力
print(ans)

45 区間スケジューリング ABC230 D Dif:963

提出

# 入力の受け取り
N,D=map(int,input().split())

# 区間の情報
Section=[]

# N回
for i in range(N):
    # 入力の受け取り
    L,R=map(int,input().split())
    # 情報を格納
    Section.append([L,R])

# 右端の列番号を基準にソート
Section.sort(key=lambda x:x[1])

# 最初の壁の右端にパンチを打つ
X=Section[0][1]

# 答え
ans=1

# i=1~(N-1)
for i in range(1,N):
    # i番目の壁の左端、右端
    Li,Ri=Section[i][0],Section[i][1]
    # 最後のパンチでi番目の壁を壊せていなければ
    # ⇔最後にパンチした位置+(D-1)<左端
    if X+D-1<Li:
        # 右端にパンチを打つ
        X=Ri
        # 回数をカウント
        ans+=1

# 答えの出力
print(ans)

46 UnionFind3 ABC218 E Dif:1004

提出

# UnionFind
class UnionFind:
    def __init__(self,n):
        self.n=n
        self.parent_size=[-1]*n
    def leader(self,a):
        if self.parent_size[a]<0: return a
        self.parent_size[a]=self.leader(self.parent_size[a])
        return self.parent_size[a]
    def merge(self,a,b):
        x,y=self.leader(a),self.leader(b)
        if x == y: return
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        self.parent_size[x] += self.parent_size[y]
        self.parent_size[y]=x
    def same(self,a,b):
        return self.leader(a) == self.leader(b)
    def size(self,a):
        return abs(self.parent_size[self.leader(a)])  
    def groups(self):
        result=[[] for _ in range(self.n)]
        for i in range(self.n):
            result[self.leader(i)].append(i)
        return [r for r in result if r != []]

# 入力の受け取り
N,M=map(int, input().split())

# 辺の情報格納用リスト
edge=[]

# M行受け取り
for i in range(M):
    A,B,C=map(int, input().split())
    # 後のソートのためC先頭で格納
    edge.append([C,A,B])

# (1)辺をCの小さい順に並び替える
edge.sort()

# 報酬
ans=0

# (2)すべての辺を取り除き、報酬と罰金の合計を計算する
for i in range(M):
    ans+=edge[i][0]

# UnionFindを初期化(頂点数(N+1)個(0~N))
UF=UnionFind(N+1)

# edgeの各要素について
for C,A,B in edge:
    # (3)Cが小さい方から辺を確認していく
    # ・Cが0以下なら
    if C<=0:
        # 頂点Ai,Biを連結し、罰金|C|を報酬にプラスする(Cがマイナスの辺は取り除く理由がない)
        # 連結
        UF.merge(A,B)
        # 罰金=|C|をプラス
        ans+=abs(C)

    # そうでないならば(cが0より大きいなら)
    else:
        # ・頂点Ai,Biが非連結なら
        if UF.same(A,B)==False:
            # 頂点Ai,Biを連結し、報酬からCを引く
            # 報酬からCを引く
            ans-=C
            # A,Bを連結
            UF.merge(A,B)

# 答えを出力
print(ans)

47 DFS2 ABC239 E Dif:1084

提出

# 入力の受け取り
N,Q=map(int,input().split())
# 1インデックスにするため先頭に「0」を追加
X=[0]+list(map(int,input().split()))
# 辺の情報格納用
edge=[[] for i in range(N+1)]

# (N-1)回
for i in range(N-1):
    # 入力の受け取り
    A,B=map(int,input().split())
    # 辺の情報を格納
    edge[A].append(B)
    edge[B].append(A)

# 部分木の頂点に書いている数を大きい順に格納したリスト
# 1インデックスにするため0番目は埋めておく
P=[[0]]

# (1)「部分木に含まれる数を大きい順にソートした二次元配列」をPとし、自分自身に書いている数をPへ記録する
for i in range(1,N+1):
    # Pへ自分自身に書いている数を追加
    P.append([X[i]])

# (2)キューを用意する
que=list()

# (3)スタート地点=頂点①をキューへ入れる
# (今いる頂点,今いる頂点の親,訪問回数)
que.append((1,0,1))

# (4)キューが空になるまで(3)を繰り返す
while 0<len(que):
    # (4)キューの「右端から」要素を取り出す
    # (今いる頂点,今いる頂点の親,訪問回数)
    now,parent,count=que.pop()

    # ・1回目の訪問ならば
    if count==1:
        # (4-1)「今いる頂点」を2回目の訪問としてキューへ記録
        que.append((now,parent,2))
        # (4-2)「今いる頂点から行ける(親でない)頂点」をキューへ1回目の訪問として記録
        # to：今いる頂点から行ける頂点
        for to in edge[now]:
            # 親でなければ
            if to!=parent:
                # キューへ記録
                que.append((to,now,1))

    # ・2回目の訪問ならば
    else:
        # to：今いる頂点から行ける頂点
        for to in edge[now]:
            # (4-3)「今いる頂点」のPへ子の頂点のPを追加
            # 親ならば
            if to==parent:
                # 次の頂点へ
                continue
            P[now]+=P[to]
            # (4-4)大きい順にソート
            P[now].sort(reverse=True)
            # (4-5)20番目以降の要素を捨てる
            P[now]=P[now][:20]

# Q回
for i in range(Q):
    # 入力の受け取り
    V,K=map(int,input().split())
    # Kをマイナス1(P[v]は先頭が0番目、次が1番目、...のため)
    K-=1
    # 答えを出力
    print(P[V][K])

48 DP4 ABC219 D Dif:1085

提出

# pypyで提出

# 入力の受け取り
N=int(input())
X,Y=map(int, input().split())

# バカでかい数を作っておく(infinity)
inf=10**15

# (1)表を作る
# dp[i][x][y]：「i種類目までの弁当を使い、x個のたこ焼きとy個のたい焼きを手に入れるために必要な弁当の最小個数」
# 初期値はinf
dp=[[[inf]*(Y+1) for i in range(X+1)] for j in range(N+1)]

# (2)すぐにわかるところを埋める
# 「0種類目までの弁当を使い、0個のたこ焼きと0個のたい焼きを手に入れる最小個数」=0
dp[0][0][0]=0

# (3)表の小さい方から答えにたどり着くまで埋める
# i=1~N
for i in range(1,N+1):
    # 入力の受け取り
    A,B=map(int, input().split())
    # たこ焼きの数：x=0~X
    for x in range(X+1):
        # たい焼きの数：y=0~Y
        for y in range(Y+1):
            # 「買わない場合」(すでに埋まっている数のほうが小さい場合は更新しない)      
            dp[i][x][y]=min(dp[i][x][y],dp[i-1][x][y])
 
            # 「買う場合」(すでに埋まっている数のほうが小さい場合は更新しない)
            # たこ焼きの数がX以上→Xへ変換
            x_plus=min(x+A,X)
            # たい焼きの数がY以上→Yへ変換
            y_plus=min(y+B,Y)
            dp[i][x_plus][y_plus]=min(dp[i][x_plus][y_plus],dp[i-1][x][y]+1)

# 答え：「N種類目までの弁当を使い、X個のたこ焼きとY個のたい焼きを手に入れるために必要な弁当の最小個数」
ans=dp[N][X][Y]

# (4)答えを出力する
# もし答えがinfだったら(X個以上のたこ焼き、Y個以上のたい焼きを手に入れられない場合)
if ans==inf:
    # -1を出力
    print(-1)
# そうでないならば
else:
    # 答えを出力
    print(ans)

49 二分探索3 ABC246 D Dif:1148

提出

# pypyで提出

# 入力の受け取り
N=int(input())

# 関数にする
def f(a,b):
    return a**3+a**2*b+a*b**2+b**3

# 答え
ans=10**20

# b=0,1,2,...10^6
# (10^6より少し大きめにしている)
for b in range(10**6+100):

    # (1)左=区間の最小、右=区間の最大　とする
    # 左
    l=0
    # 右
    r=10**6+100

    # 1<(右-左)の間
    while 1<r-l:
        # (2)中央=(左+右)//2が条件を満たすか確認
        c=(r+l)//2

        # (3)(2)の結果より左または右を更新する
        # 計算結果がN未満なら
        if f(c,b)<N:
            # 左=中央と更新
            l=c
        # 計算結果がN以上なら
        else:
            # 右=中央と更新
            r=c

    # N≤f(l,b)ならば
    if N<=f(l,b):
        # f(l,b)がansより小さければ更新
        ans=min(ans,f(l,b))
    # そうでなければ(f(l,b)<N⇔f(r,b)≤N)
    else:
        # f(r,b)がansより小さければ更新
        ans=min(ans,f(r,b))    

# 答えの出力
print(ans)

50 ワーシャルフロイド法 ABC208 D Dif:1190

提出

# pypyで提出

# 入力の受け取り
N,M=map(int, input().split())

# 到達不可能時間(大きすぎるとTLEするので注意)
inf=10**15
# 時間表
time=[[inf]*(N+1) for i in range(N+1)]

# i=1~Nまで
for i in range(1,N+1):
    # 都市①→都市①,都市②→都市②、...を時間0へ
    time[i][i]=0

# M回
for i in range(M):
    # 入力の受け取り
    A,B,C=map(int, input().split())
    # 時間表の更新
    time[A][B]=C

# 答えを格納する変数
ans=0

# k=1~N
for k in range(1,N+1):
    # 新しい時間表
    new_time=[[0]*(N+1) for i in range(N+1)]

    # スタート都市：1~N
    for start in range(1,N+1):
        # ゴール都市：1~N
        for goal in range(1,N+1):
            # 新しい時間表を更新
            # 「(K-1)以下の都市を通って良いパターン」と「都市kを経由するパターン」の小さい方
            new_time[start][goal]=min(time[start][goal],time[start][k]+time[k][goal])

           
    # スタート都市：1~N
    for start in range(1,N+1):
        # ゴール都市：1~N
        for goal in range(1,N+1):
             # 新しい時間表でスタート→ゴールが到達不能でなければ
            if new_time[start][goal]!=inf:
                # 新しい時間を答えにプラス
                ans+=new_time[start][goal]
 
    # 古い時間表を新しい時間表へ更新
    time=new_time

# 答えの出力
print(ans)

クラス解説：UnionFind

# UnionFind
class UnionFind:
    # UnionFind(N)：要素数Nで初期化。
    # 引数：N(要素数)　→　返り値：なし
    def __init__(self,N):
        # 要素数
        self.N=N
        # 根の番号　と　木の要素数
        # マイナスの場合:グループの要素数(自身が根)
        # プラスの場合:根の番号
        self.parent_size=[-1]*N

    # leader(a)：aの根を返す
    # 引数：a　→　返り値：aの根
    def leader(self,a):
        # aが根ならa自身を返す
        if self.parent_size[a]<0: return a
        # aが根でないなら根に向かって木をたどる＋根の更新
        self.parent_size[a]=self.leader(self.parent_size[a])
        # 根を返す
        return self.parent_size[a]

    # merge(a,b)：aとbを連結
    # 引数：a,b　→　返り値：なし
    def merge(self,a,b):
        # a,bの根をx,yへ
        x,y=self.leader(a),self.leader(b)
        # 根が同じなら終了
        if x == y: return
        # 木の要素数を比較　小さい方を大きい方につなげるため
        # x<yならばx,yを入れ替える(xを大きい方にしたい)
        if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
        # 要素数の更新：小さい方の要素数を大きい方の要素数に足す
        self.parent_size[x] += self.parent_size[y]
        # 要素数が小さい方の根を大きい方の根につなげる
        self.parent_size[y]=x

    # same(a,b)：aとbの根が同じか確認
    # 引数：a,b　→　返り値：True(根が同じ)　False(根が違う)
    def same(self,a,b):
        # 根を比較し、同じならTrueを返す
        return self.leader(a) == self.leader(b)

    # size(a)：aが属する木の要素数
    # 引数：a　→　返り値：aが属する木の要素数
    def size(self,a):
        # 根の絶対値(=要素数)を返す
        return abs(self.parent_size[self.leader(a)])

    # groups()：それぞれの木の内容を二次元配列として返す
    # 引数：なし　→　返り値：木の内容
    def groups(self):
        # グループの格納リストを作る
        result=[[] for _ in range(self.N)]
        # リストの生成
        for i in range(self.N):
            result[self.leader(i)].append(i)
        # 空の要素を消す
        return [r for r in result if r!=[]]

クラス解説：FenwickTree

# FenwickTree
class FenwickTree:
    # 「FenwickTree(N)：要素数Nで初期化」
    # 引数：N→返り値：なし
    def __init__(self,N):
        self.N=N
        # F：長さNのリスト
        self.F=[0]*N

    # 「add(i,x)：i番目の要素にxを加算」
    # 引数：i,x→返り値：なし
    def add(self,i,x):
        # 1インデックスにするため1を加算
        i+=1
        # i≤Nの間
        while i<=self.N:
            # xを加算
            # iはプラス1されているのでF[i-1]に加算
            self.F[i-1]+=x
            # 次のi
            i+=i&-i

    # 「sum_r(r)：区間[0,r)の区間和を計算」
    # 引数：r→返り値：区間[0,r)の区間和
    def sum_r(self,r):
        # 合計
        s=0
        # 0<rの間
        while 0<r:
            # sに加算
            s+=self.F[r-1]
            # 次のr
            r-=r&-r
        # 合計を返す
        return s

    # 「sum(l,r)：区間[l,r]の区間和を計算」
    # 引数：l,r→返り値：区間[l,r]の区間和
    def sum(self,l,r):
        # 「区間[l,r]の区間和」=「区間[0,r+1)の区間和」-「区間[0,l)の区間和」
        return self.sum_r(r+1)-self.sum_r(l)

    # 「select(i)：i番目の要素を出力」
    # 引数：i→返り値：i番目の要素
    def select(self,i):
        # 区間[i,i]の区間和
        return self.sum(i,i)