More than 3 years have passed since last update.

ABC211～220 『 AtCoder ABC201～225 ARC119～128 灰・茶・緑問題超詳細解説』コピペ用コード

競プロ

Last updated at 2022-03-04Posted at 2022-02-20

ABC201~210
https://qiita.com/sano192/items/2efd871a4b2dee05c321

ABC220~225
https://qiita.com/sano192/items/8fe5e85a5b3fb15bb49b

ARC119~128,UnionFind,FenwickTree
https://qiita.com/sano192/items/9e348b69844f763caf93

ABC211 A

提出

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

# Cを計算する
C=(A-B)/3+B

# Cを出力する
print(C)

ABC211 B

提出

# それぞれが存在するか確認する変数(存在しない=0,存在する=1)
H=0
B2=0
B3=0
HR=0

# 一行ずつ受け取り
for i in range(4):
    # 入力を受け取る
    S=input()
    # 入力が一致したものを1へ変更
    if S=="H":
        H=1
    elif S=="2B":
        B2=1
    elif S=="3B":
        B3=1
    elif S=="HR":
        HR=1

# 全部1ならば
if H==1 and B2==1 and B3==1 and HR==1:
    # Yesを出力
    print("Yes")
# そうでないならば
else:
    # Noを出力
    print("No")

別解

# 入力の格納用
count=set()

# 4回
for i in range(4):
    # セットに入力を追加
    count.add(input())

# countの要素数が4
if len(count)==4:print("Yes")
# それ以外(countの要素数が4未満)
else:print("No")

ABC211 C

提出

# 入力の受け取り
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])

ABC211 D

提出

# 入力の受け取り
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_city=que.popleft()

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

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

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

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

ABC212 A

提出

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

# 0<AかつB=0：純金
if 0<A and B==0:
    print("Gold")
# A=0かつ0<B：純銀
elif A==0 and 0<B:
    print("Silver")
# 0<Aかつ0<B：合金
elif 0<A and 0<B:
    print("Alloy")

ABC212 B

提出

# 文字列として受け取り
S=input()

# 1文字ずつに分解
X1=S[0]
X2=S[1]
X3=S[2]
X4=S[3]

# (1)4桁とも同じ数字である
if X1==X2 and X2==X3 and X3==X4:
    # 答えの出力
    print("Weak")
    # 途中で終了するときはexit()
    exit()

# (2)1≤i≤3をみたす任意の整数iについて、X[i+1]が、X[i]の次の数字である
# int(X1)+1：文字列→数値に変換して+1
# %10：10で割った余り。9の次の数字を0にするため
if (int(X1)+1)%10==int(X2) and (int(X2)+1)%10==int(X3) and (int(X3)+1)%10==int(X4):
    # 答えの出力
    print("Weak")
    # 途中で終了するときはexit()
    exit()
 
# 2つの条件に該当しなければStrong
print("Strong")

別解

# 文字列として受け取り
S=input()

# 弱いパスワードの一覧
Weak=[]

# 0000,1111,2222,...,9999
for i in range(10):
    password=str(i)*4
    Weak.append(password)

# 0123,1234,2345,...,9012
for i in range(10):
    password=""
    for x in range(4):
        password+=str((i+x)%10)
    Weak.append(password)

# 答えを出力
if S in Weak:print("Weak")
else:print("Strong")

ABC212 C

提出

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

# A,Bをソート
A.sort()
B.sort()

# 答え(最小を取るので最初はバカでかい数)
ans=10**15

# i：Aのインデックス番号
# j：Bのインデックス番号
i=0
j=0

# i<N,j<Mの範囲で
while i<N and j<M:
    # |A[i]-B[j]|を計算、今までの答えより小さければ答えを更新
    ans=min(ans,abs(A[i]-B[j]))
 
    # もしA[i]<B[j]ならば
    if A[i]<B[j]:
        # Aを次へ
        i+=1
    # もしB[j]<A[i]ならば
    elif B[j]<A[i]:
        # Bを次へ
        j+=1
    # もしA[i]=B[j]ならば
    else:
        # 答えは0
        print(0)
        # 終了
        exit()

# 答えの出力
print(ans)

別解

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

# Aをソート
A.sort()

# 二分探索
# 引数：x　→　返り値：|A[i]-x|のうち最小のもの
def Nibutan(x):
    # xがA[0]より小さいならば|A[0]-x|を返す
    if x<A[0]:return abs(A[0]-x)
    # xがA[N-1]より大きいならば|A[N-1]-x|を返す
    if A[N-1]<x:return abs(A[N-1]-x)
 
    # 左端(left)：常にA[l]<xとなるようにする
    l=0
    # 右端(right)：常にA[r]<xとなるようにする
    r=N-1

    # 1<(右端-左端)の間
    while 1<r-l:
        # 中央(center)
        c=(l+r)//2
        # A[c]<xならば左端=中央と更新
        if A[c]<x:l=c
        # x<A[c]ならば右端=中央と更新
        elif x<A[c]:r=c
        # x=A[c]ならば0を返す
        else:return 0
  
    # (A[l]-x)と(A[r]-x)の小さい方を返す
    return min(abs(A[l]-x),abs(A[r]-x))

# 答え
ans=10**15

# Bのそれぞれの要素について最小差を確認
for x in B:ans=min(ans,Nibutan(x))

# 答えの出力
print(ans)

ABC212 D

提出

# 入力の受け取り
Q=int(input())
 
# heapqをimport
import heapq
 
# リスト(袋)を用意
que=list()
 
# i番目の操作で加算された数を記録するリスト
plus=[0]*(Q+1)
 
# plusの累積和
cum_plus=[0]*(Q+1)
 
# i=1~Qまで
for i in range(1,Q+1):
    # 入力の受け取り(要素数が操作1,2と3で違うからとりあえずリストで受け取る)
    query=list(map(int, input().split()))
 
    # 操作1
    if query[0]==1:
        X=query[1]
        # 今まで加算された数(=累積和の(i-1)番目)を引く
        minus=cum_plus[i-1]
        # queへ格納[Xi-(それまでに加算された数),i番目の操作でボールを入れた,マイナスした数はminus]
        heapq.heappush(que,[X-minus,i,minus])
        # 袋の中のボールへ「0」を足した
        plus[i]=0
        # 累積和の計算
        cum_plus[i]=cum_plus[i-1]+plus[i]
 
    # 操作2
    elif query[0]==2:
        X=query[1]
        # 袋の中のボールへ「X」を足した
        plus[i]=X
        # 累積和の計算
        cum_plus[i]=cum_plus[i-1]+plus[i]

    # 操作3
    else:
        # num：取り出したボールに書いている数
        # k：ボールをk番目の操作で入れた
        # minus：ボールを入れるときに引かれた数
        num,k,minus=heapq.heappop(que)
        # ad：操作2で加算された数
        # k番目の操作で袋へ入れた後、(plus[k]~plus[i-1]の和)加算されている
        # (plus[k]~plus[i-1]の和)=cum_plus[i-1]-cum_plus[k-1]
        ad=cum_plus[i-1]-cum_plus[k-1]
        # (取り出したボールに書いている数+操作1でマイナスされた数+操作2で加算された数)
        print(num+minus+ad)
        # 袋の中のボールへ「0」を足した
        plus[i]=0
        # 累積和の計算
        cum_plus[i]=cum_plus[i-1]+plus[i]

ABC213 A

提出

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

# 答えの出力
print(B^A)

ABC213 B

提出

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

# スコアと選手の番号を記録するリスト
score=[]

# i=0~(N-1)まで
for i in range(N):
    # [スコア,選手の番号(i+1)]を順に格納する
    score.append((A[i],i+1))

# 大きい順にソート
score.sort(reverse=True)

# 2番目(インデックスは1)の選手の番号を出力
print(score[1][1])

ABC213 C

提出

# 入力の受け取り
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()

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

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

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

retu_convert=dict()

for i in range(len(retu)):
    retu_convert[retu[i]]=i+1

# それぞれのカードについて行、列番号を変換して出力
for gyou,retu in cards:
    # 行番号の変換
    ans_gyou=gyou_convert[gyou]
    # 列番号の変換
    ans_retu=retu_convert[retu]
    # 答えを出力する
    print(ans_gyou,ans_retu)

ABC213 D

提出

# 再帰回数上限。再帰関数を書くときは必ず最初に書くこと
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)

ABC214 A

提出

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

# 1≤N≤125
if 1<=N<=125:
    print(4)
# 126≤N≤211
elif 126<=N<=211:
    print(6)
# それ以外(212≤N≤214)
else:
    print(8)

ABC214 B

提出

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

# 答えのカウント
ans=0

# a=0~100まで探索
for a in range(101):
    # b=0~100まで探索
    for b in range(101):
        # c=0~100まで探索
        for c in range(101):
            # 条件を満たしていれば
            if a+b+c<=S and a*b*c<=T:
                # 答えのカウントを1増やす
                ans+=1

# 答えの出力
print(ans)

ABC214 C

提出

# 入力の受け取り
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])

ABC215 A

提出

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

# Hello,World!に等しいなら
if S=="Hello,World!":
    # ACを出力
    print("AC")
# そうでないならば
else:
    # WAを出力
    print("WA")

ABC215 B

提出

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

# k=1~999まで
for k in range(1,1000):
    # もしN<2^kならば
    if N<2**k:
        # 一つ前のkが答え
        print(k-1)
        # 終了
        exit()

ABC215 C

提出

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

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

# 作れる文字を格納するセット(リストだと重複するものも入ってしまうためセットを使う)
S_set=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))):
    # 作った文字列を記録する変数
    S_tmp=""
    # pを使って文字を作成
    # 例：p=(2,0,1)ならS_tmp=Sの2文字目+Sの0文字目+Sの1文字目
    for i in p:
        S_tmp+=S[i]
    # できた文字をS_setに格納(setへの追加はappendではなくaddであることに注意)
    S_set.add(S_tmp)

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

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

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

ABC215 D

提出

# 提出はpypyで行う

# 素因数分解
# 引数：x　→　返り値：xの素因数リスト
# x=1の場合は空のリストを返す
def prime_factorize(x):
    # もしx=1ならば
    if x==1:
        # 空のリストを返す
        return []
    # 素因数を格納するリスト
    prime_list=[]
    # i=2,3,4,...で試し割り
    i=2
    # i<=√xすなわちi*i<=xの範囲で試し割り
    while i**2<=x:
        # もしiで割り切れたら
        if x%i==0:
            # iを素因数に追加
            prime_list.append(i)
            # xをiで割る
            x//=i
        # iで割り切れなかったら
        else:
            # 次のiへ
            i+=1
    # 試し割りが終わった時xが1でなければ
    if x!=1:
        # 素因数にxを追加
        prime_list.append(x)
    # 素因数のリストを返す
    return prime_list

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

# 素因数を格納するセット(重複した素数をいれないため、リストでなくセットにする)
prime_set=set()

# Aの各要素について
for x in A:
    # prime_x=xの素因数リスト
    prime_x=prime_factorize(x)
    # xの素因数をprime_setに追加
    for p in prime_x:
        prime_set.add(p)

# ans_judge[x]=Trueなら答え、=0なら答えでない
ans_judge=[True]*(M+1)

# prime_set=Aの要素が持つ素数(p)について
for p in prime_set:
    # p*1,p*2,p*3,...,p*k,...は答えでない→ans_judge[p*k]=Falseとする
    # p*kがMを超えるまで
    k=1
    while p*k<=M:
        ans_judge[p*k]=False
        k+=1

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

# 1~Mまで
for i in range(1,M+1):
    # ans_judge[i]=1ならiは答え
    if ans_judge[i]==True:
        ans.append(i)

# 答えの個数を出力
print(len(ans))
# 答えを出力
for x in ans:
    print(x)

ABC216 A

提出

# 文字として受け取り
S=input()

# 後ろから1文字目をYとする(文字列)
Y=S[-1]

# 後ろから2文字目までをXとする
X=S[0:-2]

# 文字列から整数へ変換
Y=int(Y)

# 0≤Y≤2ならば
if 0<=Y<=2:
    # X-を出力
    print(X+"-")

# 3≤Y≤6ならば
elif 3<=Y<=6:
    # Xを出力
    print(X)

# それ以外(7≤Y≤9)ならば
else:
    # X+を出力
    print(X+"+")

ABC216 B

提出

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

# 姓を格納するリスト
FamilyName=[]
# 名を格納するリスト
GivenName=[]

# N回
for i in range(N):
    # S,Tを受け取る
    S,T=map(str,input().split())
    # 姓リストにSを追加
    FamilyName.append(S)
    # 名リストにTを追加
    GivenName.append(T)

# i=1~(N-1)まで
for i in range(N):
    # j=(i+1)~(N-1)まで
    for j in range(i+1,N):
        # i番目の姓名とj番目の姓名を比較
        # 姓が同じ　かつ　名が同じなら
        if FamilyName[i]==FamilyName[j] and GivenName[i]==GivenName[j]:
            # Yesを出力
            print("Yes")
            # プログラムを終了
            exit()

# 同じ姓、名が一組もなければここまでくる
# Noを出力
print("No")

ABC216 C

提出

# 入力の受け取り
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)

ABC216 D

提出

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

# 筒の情報
cylinder=[]

for i in range(M):
    # Kを受け取り
    K=int(input())
    # リストで受け取る
    tmp_list=list(map(int, input().split()))
    # M本目の筒に情報を格納
    cylinder.append(tmp_list)

# 色iのボールが何番目の筒の一番上にあるかを記録するリスト
# cylinder_num[3]=[0,5]ならば色3のボールが0,5番目の筒の一番上にある
cylinder_num=[[] for i in range(N+1)]
 
# 色iのボールが筒の一番上に何個あるか記録するリスト
count=[0]*(N+1)
 
# 筒の一番上を順に確認する
for i in range(M):
    # i本目の筒の一番上にあるボールの色
    color=cylinder[i][-1]
    # cylinderに「色colorのボールがi番目の筒の一番上にある」と記録
    cylinder_num[color].append(i)
    # 色colorのボールが筒の一番上にある個数をプラス1
    count[color]+=1

# dequeをインポート
from collections import deque
# 一番上に2つあるボールの色番号を格納するキュー
set_que=deque()
 
# それぞれの色について一番上にいくつあるか確認
for i in range(1,N+1):
    # もし一番上に二個あるならば
    if count[i]==2:
        # キューにその色番号を追加
        set_que.append(i)

# キューが空になるまで
while 0<len(set_que):
    # キューの左端から一番上に二個あるボールの色番号を取得
    set_color=set_que.popleft()
    # set_color色のそれぞれのボール(ボール1,ボール2)が何番目の筒の一番上にあるかを取得
    ball1,ball2=cylinder_num[set_color]

    # それぞれのボールがある筒の一番上を削除(ボールを取り出す)
    cylinder[ball1].pop()
    cylinder[ball2].pop()
 
    # もしボール1が入っていた筒が空でなければ
    # 筒の一番上の情報を更新する
    if 0<len(cylinder[ball1]):
        # 次に一番上にくるボール
        color=cylinder[ball1][-1]
        # color色のボールが一番上にある数を+1
        count[color]+=1
        # color色のボールがball1番目の筒の一番上にあると情報を更新
        cylinder_num[color].append(ball1)
        # もし一番上にcolor色のボールが二個あるならば
        if count[color]==2:
            # キューにcolorを追加
            set_que.append(color)

    # もしボール2が入っていた筒が空でなければ
    # 筒の一番上の情報を更新する
    if 0<len(cylinder[ball2]):
        # 次に一番上にくるボール
        color=cylinder[ball2][-1]
        # color色のボールが一番上にある数を+1
        count[color]+=1
        # color色のボールがball2番目の筒の一番上にあると情報を更新
        cylinder_num[color].append(ball2)
        # もし一番上にcolor色のボールが二個あるならば
        if count[color]==2:
            # キューにcolorを追加
            set_que.append(color)

# キューが空になったら
# i=0~(M-1)
for i in range(M):
    # 長さが0より大きい筒が残っていたら
    if 0<len(cylinder[i]):
        # Noを出力
        print("No")
        # 終了
        exit()

# 全ての筒の長さが0ならば(全てのボールが捨てられていたら)
# Yesを出力
print("Yes")

ABC216 E

提出

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

# もし全てのカードが取れるなら
# ⇔(Aの和)≤Kならば
if sum(A)<=K:
    # 答えの格納変数
    ans=0
    # i=0~(N-1)
    for i in range(N):
        # 1~A[i]までの和をansへプラス
        ans+=A[i]*(1+A[i])//2
    # ansを出力
    print(ans)
    # 終了
    exit()

# mより上に線を引いてK枚カードが取れるか
# 引数：m　→　返り値：「取れる」→True,「取れない」→False
def Judge(m):
    # カードを取る枚数をカウント
    count=0
    # i=0~(N-1)
    for i in range(N):
        # m≤A[i]ならば
        if m<=A[i]:
            # (A[i]-m+1)枚カードを取る
            count+=A[i]-m+1

    # K枚以下なら
    if count<=K:
        # 「取れる」
        return True
    # そうでないなら(K枚より多いなら)
    else:
        # 「取れない」
        return False

# 左(left)=1
l=1
# 右(right)=バカでかい数
r=10**15

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

    # cより上に線を引いてK枚カードが取れる場合
    if Judge(c)==True:
        # 右をcへ更新
        r=c
    # そうでないなら(cより上に線を引いてK枚カードが取れない場合)
    else:
        # 左をcへ更新
        l=c

# 探索終了
# rが「取れる」mの最小値

# 答え
ans=0
# i=0~(N-1)
for i in range(N):
    # もしA[i]がrより大きければ
    if r<=A[i]:
        # rより大きなカードをすべて取れる
        # A[i]~rの和を足す
        ans+=(A[i]-r+1)*(A[i]+r)//2
        # 取った枚数をKから引く
        K-=A[i]-r+1

# 残り枚数(K)はr-1のカードを取る
ans+=(r-1)*K

# 答えを出力
print(ans)

ABC217 A

提出

# 入力を受け取る
S,T=map(str, input().split())

# もし辞書順でS<Tならば
if S<T:
    # Yesを出力
    print("Yes")
# そうでないならば(辞書順でT<Sならば)
else:
    # Noを出力
    print("No")

ABC217 B

提出

# 入力の受け取り
S1=input()
S2=input()
S3=input()

# もしABCがS1,S2,S3に含まれていなければ
if "ABC" not in [S1,S2,S3]:
    # ABCを出力
    print("ABC")
# もしARCがS1,S2,S3に含まれていなければ  
elif "ARC" not in [S1,S2,S3]:
    # ARCを出力
    print("ARC")
# もしAGCがS1,S2,S3に含まれていなければ
elif "AGC" not in [S1,S2,S3]:
    # AGCを出力
    print("AGC")
# それ以外(もしAHCがS1,S2,S3に含まれていなければ)
else:
    # AHCを出力
    print("AHC")

別解

# 入力の受け取り
S1=input()
S2=input()
S3=input()

# S=「ABC」「ARC」「AGC」「AHC」を順に入れて処理
for S in ["ABC","ARC","AGC","AHC"]:
    if S not in [S1,S2,S3]:print(S)

ABC217 C

提出

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

# P[0]を埋めるため、先頭に「0」を埋める⇔[0]+をつける
P=[0]+list(map(int, input().split()))

# Qを用意
Q=[0]*(N+1)

# i=1~Nまで
for i in range(1,N+1):
    # Q[P[i]]=iを順に埋める
    Q[P[i]]=i

# 答えを出力
# *(リスト)にすると[]なしで出力
# Q[0]は不要なのでQ[1:](1以降を出力)
print(*Q[1:])

ABC217 D

提出

# 提出は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])

ABC217 E

提出

# 入力の受け取り
Q=int(input())
# キューを用意
from collections import deque
que=deque()

# heapqを用意
import heapq
heap_que=list()

# Q回
for i in range(Q):
    # クエリの受け取り(要素数がクエリの種類によって違うためとりあえずリストで)
    query=list(map(int, input().split()))

    # クエリ①
    if query[0]==1:
        # xを取り出し
        x=query[1]
        # キューに格納
        que.append(x)

    # クエリ②
    elif query[0]==2:
        # もしheap_queに要素があれば
        if 0<len(heap_que):
            # heap_queから取り出し
            ans=heapq.heappop(heap_que)
        # heap_queが空なら
        else:
            # dequeから取り出し
            ans=que.popleft()
        # 答えを出力
        print(ans)

    # クエリ③
    else:
        # dequeの中身をheapqへ入れ直す
        for i in range(len(que)):
            heapq.heappush(heap_que,que.popleft())

ABC218 A

提出

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

# SのN文字目(S[N-1])が"o"なら
if S[N-1]=="o":
    # Yesを出力
    print("Yes")

# そうでないならば(SのN文字目(S[N-1])が"x"なら)
else:
    # Noを出力
    print("No")

ABC218 B

提出

# 入力の受け取り
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)

ABC218 C

提出

# #の個数を確認する関数
def count_sharp(X):
    # #の個数をカウントする変数
    count=0
    # 行：gyou=0~(N-1)
    for gyou in range(N):
        # 列：retu=0~(N-1)
        for retu in range(N):
            # もしx[行番号][列番号]が#なら
            if X[gyou][retu]=="#":
                # カウントにプラス1
                count+=1
    # カウント数を返す
    return count

# 90度時計回りに回転する関数
def rotate(X):
    # 回転後のグリッド
    rotate_X=[["."]*N for i in range(N)]
    # 行：gyou=0~(N-1)
    for gyou in range(N):
        # 列：retu=0~(N-1)
        for retu in range(N):
            # (行番号,列番号)→(列番号,(N-1)-行番号)
            rotate_X[retu][(N-1)-gyou]=X[gyou][retu]
    # 回転後のグリッドを返す
    return rotate_X

# 左上から探索して初めて#が出てくる行番号,列番号を返す関数
def first_sharp(X):
    # 行：gyou=0~(N-1)
    for gyou in range(N):
        # 列：retu=0~(N-1)
        for retu in range(N):
            # もしx[行番号][列番号]が#なら
            if X[gyou][retu]=="#":
                # 行番号,列番号を返して終了
                return gyou,retu

# 下方向へmove_gyou,右方向へmove_retu平行移動する関数
def Translation(X,move_gyou,move_retu):
    # 平行移動後のグリッド
    move_X=[["."]*N for i in range(N)]
    # 行：gyou=0~(N-1)
    for gyou in range(N):
        # 列：retu=0~(N-1)
        for retu in range(N):
            # 行番号+move_gyou,列番号+move_retuがグリッドの中にあれば
            if 0<=gyou+move_gyou<N and 0<=retu+move_retu<N:
                # (行番号,列番号)→(行番号+move_gyou,列番号+move_retu)
                move_X[gyou+move_gyou][retu+move_retu]=X[gyou][retu]
    # 平行移動後のグリッドを返す
    return move_X

# S,Tが一致しているか確認する関数
def check(S,T):
    # 行：gyou=0~(N-1)
    for gyou in range(N):
        # 列：retu=0~(N-1)
        for retu in range(N):
            # もしS[gyou][retu]とT[gyou][retu]が一致しなければ
            if S[gyou][retu]!=T[gyou][retu]:
                # Falseを返して終了
                return False
    # 完全に一致していればTrueを返す
    return True

# 入力の受け取り
N=int(input())
# S,Tを用意
S=[]
T=[]

# N行受け取り
for i in range(N):
    # 文字列でSを受け取り
    S_tmp=input()
    # リストに変換
    S_tmp=list(S_tmp)
    # Sへ格納
    S.append(S_tmp)

# N行受け取り
for i in range(N):
    # 文字列でTを受け取り
    T_tmp=input()
    # リストに変換
    T_tmp=list(T_tmp)
    # Tへ格納
    T.append(T_tmp)

# #の数が違う場合
if count_sharp(S)!=count_sharp(T):
    # Noを出力
    print("No")
    # 終了
    exit()

# 4回回転する(90→180→270→360(0))
for i in range(4):
    # Sを回転
    S=rotate(S)
    # S,Tの最初の#が出てくる行番号、列番号を確認
    S_FirstGyou,S_FirstRetu=first_sharp(S)
    T_FirstGyou,T_FirstRetu=first_sharp(T)
 
    # 行平行移動量=(Tの最初の#が出てくる行番号)-(Sの最初の#が出てくる行番号)
    move_gyou=T_FirstGyou-S_FirstGyou
    # 列平行移動量=(Tの最初の#が出てくる列番号)-(Sの最初の#が出てくる列番号)
    move_retu=T_FirstRetu-S_FirstRetu

    # Sを下方向へmove_gyou,右方向へmove_retu平行移動
    S_Trans=Translation(S,move_gyou,move_retu)

    # 一致しているかチェック
    if check(S_Trans,T)==True:
        # 一致していたらYesを出力
        print("Yes")
        # 終了
        exit()

# 4回転試して一致しなければNoを出力
print("No")

ABC218 D

提出

# 入力を受け取り
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)

ABC218 E

提出

# 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)

ABC219 A

提出

# 入力の受け取り
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")

ABC219 B

提出

# 入力の受け取り
S1=input()
S2=input()
S3=input()
T=input()

# Tのi文字目→S1,S2,S3へ変換する関数
# 引数：t　→　返り値S1,S2,S3
def convert(t):
    # tが"1"ならば
    if t=="1":
        # S1を返す
        return S1
    # tが2ならば
    elif t=="2":
        # S2を返す
        return S2
    # それ以外(tが"3")ならば
    else:
        # S3を返す
        return S3

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

# i=0~(Tの長さ-1)
for i in range(len(T)):
    # 変換後の文字列を末尾へ連結
    ans+=convert(T[i])

# 答えの出力
print(ans)

ABC219 C

提出

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

# 新しいアルファベット　→　通常のアルファベット
New_Normal=dict()
# 通常のアルファベット　→　新しいアルファベット
Normal_New=dict()

# それぞれの文字について変換表を作成
for i in range(26):
    # chr(97)="a"
    # chr(98)="b"
    # ...
    # Xのi文字目　→　chr(i+97)
    New_Normal[X[i]]=chr(i+97)
    # chr(i+97)　→　Xのi文字目
    Normal_New[chr(i+97)]=X[i]

# 新しいアルファベット　→　通常のアルファベットへ変換する関数
# 引数：S　→　返り値：変換後の文字列
def NewToNormal(S):
    # 結果を格納する変数
    result=""
    # i=0~(Sの文字数-1)
    for i in range(len(S)):
        # 変換してresultの末尾へ結合
        result+=New_Normal[S[i]]
    # resultを返す
    return result

# 通常のアルファベット　→　新しいアルファベットへ変換する関数
# 引数：S　→　返り値：変換後の文字列
def NormalToNew(S):
    # 結果を格納する変数
    result=""
    # i=0~(Sの文字数-1)
    for i in range(len(S)):
        # 変換してresultの末尾へ結合
        result+=Normal_New[S[i]]
    # resultを返す
    return result

# 通常のアルファベットへ変換後の名前を格納する変数
ConvNames=[]

# 入力の受け取り
# N回
for i in range(N):
    # Sの受け取り
    S=input()
    # 通常のアルファベットへ変換
    Conv_S=NewToNormal(S)
    # ConvNamesへ追加
    ConvNames.append(Conv_S)

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

for i in range(N):
    # 新しいアルファベットへ変換
    Inv_S=NormalToNew(ConvNames[i])
    # 出力
    print(Inv_S)

ABC219 D

提出

# 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)

ABC220 A

提出

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

# x=A~Bまで
for x in range(A,B+1):
    # xがCの倍数=xをCで割った余りが0の場合
    if x%C==0:
        # xを出力
        print(x)
        # プログラムを終了
        exit()
 
# A~BにCの倍数がなければここに到達する
# 「-1」を出力
print(-1)

ABC220 B

提出

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

# 10進法へ変換する関数
# 引数：x(文字列)　→　返り値：xの10進数表記
def convert_ten(x):
    # xを反転
    x=x[::-1]
    # 結果の格納用
    result=0
    # i=0~(xの桁数-1)
    for i in range(len(x)):
        # xのi桁目*(K^i) intでxのi桁目を整数へ変換
        result+=int(x[i])*(K**i)
    # 結果を返す
    return result

# A,Bを10進法へ変換
A_ten=convert_ten(A)
B_ten=convert_ten(B)

# 答えの出力
print(A_ten*B_ten)

ABC220 C

提出

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

# Aの合計
A_sum=sum(A)

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

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

# 合計(B_sum)：(Aの個数)×(Aの合計)
B_sum=A_sum*quo

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

ABC220 D

提出

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

# 余りの定義
mod=998244353

# 左端に0~9がいくつあるかカウントする配列
count=[0]*10

# A[0]が1個ある
count[A[0]]=1

# i=1~(N-1)まで
for i in range(1,N):
    # 新しいカウント用配列
    new_count=[0]*10
    # x=0~9
    for x in range(10):
        y=A[i]
        # 操作F：x+yの結果
        F=(x+y)%10
        # 操作G：x*yの結果
        G=(x*y)%10
        # count[x]の個数だけ新しいカウントに追加
        new_count[F]+=count[x]
        new_count[G]+=count[x]
        # 余りを取る
        new_count[F]%=mod
        new_count[G]%=mod
    # countに更新
    count=new_count

# 答えの出力
for x in count:
    print(x)

別解

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

# 余りの定義
mod=998244353

# 表の定義
dp=[[0]*10 for i in range(N)]

# 初期値
dp[0][A[0]]=1

# i=0~(N-2)
for i in range(N-1):
    # j=0~9
    for j in range(10):
        # 遷移
        dp[i+1][(j+A[i+1])%10]+=dp[i][j]
        dp[i+1][(j*A[i+1])%10]+=dp[i][j]
        # 余りを取る
        dp[i+1][(j+A[i+1])%10]%=mod
        dp[i+1][(j*A[i+1])%10]%=mod

# 答えの出力
for x in dp[N-1]:
    print(x)

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up

ABC211～220 『 AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』コピペ用コード

ABC211 A

ABC211 B

ABC211 C

ABC211 D

ABC212 A

ABC212 B

ABC212 C

ABC212 D

ABC213 A

ABC213 B

ABC213 C

ABC213 D

ABC214 A

ABC214 B

ABC214 C

ABC215 A

ABC215 B

ABC215 C

ABC215 D

ABC216 A

ABC216 B

ABC216 C

ABC216 D

ABC216 E

ABC217 A

ABC217 B

ABC217 C

ABC217 D

ABC217 E

ABC218 A

ABC218 B

ABC218 C

ABC218 D

ABC218 E

ABC219 A

ABC219 B

ABC219 C

ABC219 D

ABC220 A

ABC220 B

ABC220 C

ABC220 D

ABC211～220 『 AtCoder ABC201～225 ARC119～128 灰・茶・緑問題超詳細解説』コピペ用コード