ABC226～235『 AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説』コピペ用コード

ABC236～250　https://qiita.com/sano192/items/b0e21a98c0b430451d7c
ARC129～139　https://qiita.com/sano192/items/485d38fa76246e866bd1

この記事は 『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説』 の提出コード一覧です。

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS

【booth(pdf)】
https://sano192.booth.pm/items/4025713

ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF

【booth(pdf)】
https://sano192.booth.pm/items/4025737

ABC226 A

# 入力の受け取り
# 文字列として受け取る
X=input()
 
# 少数第一位(=後ろから3つ目の数字)の取り出し
Syousu1=X[-3]
# 整数へ変換
Syousu1=int(Syousu1)
 
# 整数部分の取り出し
# (文字列)→(少数含む)数へ変換
X=float(X)
# (少数含む)数→整数へ変換(小数点以下は切り捨てられる)
Seisu=int(X)
 
# 少数第一位が0～4だったら
if 0<=Syousu1<=4:
    # 整数部分を出力
    print(Seisu)
# そうでなければ(少数第一位が5～9だったら)
else:
    # 整数部分+1を出力
    print(Seisu+1)

# 整数部分と小数部分に分けて受け取り
Seisu,Syousu=map(int,input().split("."))
 
# 0≤小数部分≤499ならば
if 0<=Syousu<=499:print(Seisu)
# そうでなければ
else:print(Seisu+1)

ABC226 B

# 入力の受け取り
N=int(input())
 
# 数列格納用セット
# セットにすると重複したものが入らない
seq=set()
 
# N回
for i in range(N):
    # 入力の受け取り
    LA=list(map(int,input().split()))
    # LAをタプルへ変換(listはsetへ追加できないため)
    LA=tuple(LA)
    # seqへ追加
    seq.add(LA)
 
# seqの中身の数を出力
print(len(seq))

ABC226 C

# 入力の受け取り
N=int(input())
 
# (1)各頂点から進める頂点のリスト(connect)を作る
connect=[[] for i in range(N+1)]
 
# Tの記録(0番目を埋めておく)
T=[0]
 
# i=1~N
for i in range(1,N+1):
    # リストで受け取り
    TKA=list(map(int,input().split()))
    # 0番目の要素がT
    T.append(TKA[0])
    # 1番目の要素がK
    K=TKA[1]
   
    # x=2~(K+1)
    for x in range(2,K+2):
        # i→TKA[x]へ進める
        connect[i].append(TKA[x])
 
# (2)「習得必要」技のリスト(learn)を作る
# 最初は全てFalseにしておき、習得必要な場合はTrueにする。
# 例えば技⑤が習得必要ならlearn[5]=Trueとなる。
learn=[False]*(N+1)
 
# (3)キューを用意し、Nを入れる
# キューを用意
from collections import deque
que=deque()
 
# キューにNを追加
que.append(N)
 
# (6)(4)～(5)をキューが空になるまで繰り返す
# ⇔キューの長さが0でなければ
while 0<len(que):
    # (4)キューの左端から要素を取り出し、「習得必要」にする
    now=que.popleft()
   
    # Nは習得必要⇔learn[N]=True
    learn[now]=True
 
    # (5)取り出した頂点番号から到達可能な頂点を確認する
    # to=nowから進める頂点
    for to in connect[now]:
        # 「習得必要」になっていなければ
        # ⇔learn[to]がFalseならば
        if learn[to]==False:
            # キューに追加する
            que.append(to)
 
# 答え
ans=0
 
# (7)learnがTrueになっている要素の時間を合計して出力する
# 1~Nまで
for i in range(1,N+1):
    # 習得必要なら
    if learn[i]==True:
        # 答えにT[i]を追加
        ans+=T[i]
 
# 答えを出力
print(ans)

ABC226 D

# 入力の受け取り
N=int(input())
 
# 座標の格納リスト
p=[]
 
# 覚える魔法のセット
Magic=set()
 
# N回
for i in range(N):
    # 入力の受け取り
    x,y=map(int,input().split())
    # 座標を格納
    p.append([x,y])
 
# 最大公約数の計算用
from math import gcd
 
# S=0~N-1
for S in range(N):
    # E=0~N-1
    for E in range(N):
        # 街S→街Eへ
        # S=E(スタートとゴールが同じ街なら)
        if S==E:
            # 次の点へ
            continue
       
        # 街sの座標
        xS,yS=p[S][0],p[S][1]
        # 街Eの座標
        xE,yE=p[E][0],p[E][1]
 
        # xの増加量
        xInc=xE-xS
        # yの増加量
        yInc=yE-yS
 
        # (xの増加量)と(yの増加量)の最大公約数
        d=gcd(xInc,yInc)
 
        # 魔法に記録
        # [xInc//d,yInc//d]にするとリストになってエラーになるので注意
        Magic.add((xInc//d,yInc//d))
 
# 魔法の個数を出力
print(len(Magic))

ABC227 A

# 入力の受け取り
N,K,A=map(int,input().split())
 
# 人Aにカードを配る
Human=A
 
# カードを配った回数
count=1
 
# カードを配った回数がK回になるまで繰り返し
while count<K:
    # カードを配った回数をプラス1
    count+=1
    # 人番号をプラス1
    # ⇔人(Human+1)にカードを配る
    Human+=1
 
    # 人(N+1)になったら
    if Human==N+1:
        # 人1にする
        Human=1
 
# 答えを出力
print(Human)

ABC227 B

# 入力の受け取り
N=int(input())
S=list(map(int,input().split()))
 
# あり得る面積のリスト
Area=[]
 
# a=1~1000
for a in range(1,1001):
    # b=1~1000
    for b in range(1,1001):
        # 4ab+3a+3bを計算して追加
        Area.append(4*a*b+3*a+3*b)
 
# 予想が間違っている人の人数
Count=0
 
# i=0~(N-1)まで
for i in range(N):
    # i番目の予想があり得る面積になければ
    if S[i] not in Area:
        # カウント+1
        Count+=1
 
# 答えの出力
print(Count)

ABC227 C

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

ABC228 A

# 入力の受け取り
S,T,X=map(int,input().split())
 
# S<Tならば
if S<T:
    # S<=X<Tなら
    if S<=X<T:
        # 「Yes」を出力
        print("Yes")
    # そうでなければ
    else:
        # 「No」を出力
        print("No")
 
# そうでなければ(T<Sならば)
else:
    # X<TまたはS<=Xならば
    if X<T or S<=X:
        # 「Yes」を出力
        print("Yes")
    # そうでなければ
    else:
        # 「No」を出力
        print("No")

ABC228 B

# 入力の受け取り
N,X=map(int,input().split())
A=[0]+list(map(int,input().split()))
 
# 秘密を知る友達
# 知っていたらTrue、知らなければFalse
# (例)Know[1」＝Trueなら友達1が秘密を知っている
Know=[False]*(N+1)
 
# 次に秘密を聞く友達
NextFriend=X
 
# 次に秘密を聞く友達がまだ秘密を知らないなら
while Know[NextFriend]==False:
    # 秘密を聞く
    Know[NextFriend]=True
    # 次に秘密を聞く友達を更新
    NextFriend=A[NextFriend]
 
# 答え
ans=0
 
# i=1~Nまで
for i in range(1,N+1):
    # 秘密を知っていれば
    if Know[i]==True:
        # 答えにカウント
        ans+=1
 
# 答えを出力
print(ans)

ABC228 C

# 入力の受け取り
N,K=map(int,input().split())
 
# 3日目までの合計得点を格納する
Point=[]
 
# N回
for i in range(N):
    # 点数を受け取り
    Pi1,Pi2,Pi3=map(int,input().split())
    # 合計点を格納
    Point.append(Pi1+Pi2+Pi3)
 
# 得点を大きい順でソート
PointSorted=sorted(Point,reverse=True)
 
# K位以内に入るための最低得点
# 受け取りが0インデックスなので[K-1]となることに注意
LowestPoint=PointSorted[K-1]
 
# i=0~(N-1)
for i in range(N):
    # 最終日に満点を取った場合(+300)、最低得点を上回れば
    if LowestPoint<=Point[i]+300:
        # 「Yes」を出力
        print("Yes")
    # そうでなければ(満点を取っても最低得点より小さい)
    else:
        # 「No」を出力
        print("No")

ABC228 D

# pypyで提出
 
# FenwickTree
class FenwickTree:
    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)
 
# 入力の受け取り
Q=int(input())
 
# Nの定義
N=2**20
 
# Aを作る
A=[-1]*N
 
# FenwickTreeを作る
Fen=FenwickTree(N)
 
# Fen[p]=1ならば更新されていない(A[p]=-1)
# Fen[p]=0ならば更新されている(A[p]≠-1)
# 最初は全て1にする
for i in range(N):
    Fen.add(i, 1)
 
# 二分探索
def Nibutan(l,r):
 
    # 1<右端-左端　の間
    while 1<r-l:
        # 中央
        c=(l+r)//2
        # 区間Fen[左端~中央]に「1」があれば⇔区間和が1以上であれば
        if 1<=Fen.sum(l,c):
            # 右端を更新
            r=c
        # そうでなければ
        # ⇔区間Fen[左端~中央]に「1」がなければ⇔区間和が0であれば
        else:
            # 左端を更新
            l=c
 
    # 右端を返す
    return r
 
# Q回
for i in range(Q):
    # 入力を受け取る
    t,x=map(int,input().split())
 
    # h=x mod N
    h=x%N
   
    # t=1の場合
    if t==1:
        # A[h]=-1ならば
        if A[h]==-1:
            # A[h]を更新
            A[h]=x
            # A[h]≠-1となったからFen[h]=0にする⇔-1する
            Fen.add(h,-1)
 
        # A[h]≠-1ならば
        else:
            # Fen[h~(N-1)]の区間和が1以上
            # ⇔h~(N-1)の区間にAが-1になっているものが少なくとも1つある
            if 1<=Fen.sum(h,N-1):
                # pを二分探索で探す
                p=Nibutan(h,N-1)
 
            # Fen[h~(N-1)]の区間和が1以上
            # ⇔h~(N-1)の区間にAが-1になっているものがない
            # ⇔0~(x-1)の区間を探索
            else:
                # A[0]=-1ならば
                if A[0]==-1:
                    # p=0となる
                    p=0
                # A[0]≠-1ならば
                else:
                    # pを二分探索で探す
                    p=Nibutan(0,h-1)
 
            # A[p]を更新
            A[p]=x
 
            # A[h]≠-1となったからFen[h]=0にする⇔-1する
            Fen.add(p,-1)
 
    # t=2の場合
    else:
        # 出力
        print(A[h])

# Nの定義
N=2**20
# Aを作る
A=[-1]*N
 
# A[h]が-1でないとき次に見る場所を確認するリスト
# 最初はNext=[1,2,3,...,N-1,0]
Next=list(range(1,N))+[0]
 
# 入力の受け取り
Q=int(input())
 
# Q回
for i in range(Q):
    # 入力の受け取り
    t,x=map(int,input().split())
 
    # h=x mod N
    h=x%N
 
    # t=1の場合
    if t==1:
              
        # A[h]=-1ならばそのまま入力
        if A[h]==-1:A[h]=x
 
        # A[h]≠-1の場合
        else:
            # 通った番号
            Passed=[]
            # -1にたどり着くまで
            while A[h]!=-1:
                # 通った番号を記録
                Passed.append(h)
                # 次の番号へ
                h=Next[h]
           
            # A[h]を更新
            A[h]=x
 
            # 通った番号に追加
            Passed.append(h)
 
            # 通った番号の行き先を全て更新
            for y in Passed:Next[y]=(h+1)%N
 
    # t=2の場合    
    else:print(A[h])

ABC229 A

# 入力の受け取り
S1=input()
S2=input()
 
# 黒マスが左上と右下
if S1=="#." and S2==".#":
    # 「No」を出力
    print("No")
 
# 黒マスが右上と左下
elif S1==".#" and S2=="#.":
    # 「No」を出力
    print("No")

# それ以外
else:
    # 「Yes」を出力
    print("Yes")

ABC229 B

# 入力を文字列で受け取り
A,B=map(str,input().split())
 
# 反転
A=A[::-1]
B=B[::-1]
 
# 桁数の小さい方が何桁か確認
keta=min(len(A),len(B))
 
# i=0~(桁数の小さい方)
for i in range(keta):
    # i桁目を整数へ変換
    Aint=int(A[i])
    Bint=int(B[i])
 
    # 各桁の足し算が10より大きければ
    if 10<=Aint+Bint:
        # 繰り上がりがある
        # 「Hard」を出力
        print("Hard")
        # 終了
        exit()
 
# 繰り上がりなし
# 「Easy」を出力
print("Easy")

ABC229 C

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

ABC229 D

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

ABC229 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
        return  
    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=[[] for i in range(N+1)]
 
# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int,input().split())
    # A→Bへ辺が張れる
    Edge[A].append(B)
 
# UnionFindを定義
UF=UnionFind(N+1)
 
# 答えの格納用
Ans=[0]*(N+1)
 
# 現在の連結成分の数
Count=0
 
# i=N~1
for i in range(N,0,-1):
    # 頂点iを追加
    # 連結成分が一つ増える
    Count+=1
    # 頂点x=頂点iと結ばれる頂点
    for x in Edge[i]:
        # 頂点iと頂点xが連結でないなら
        if UF.same(i,x)==False:
            # 頂点iと頂点xをつなげる
            UF.merge(i,x)
            # 連結成分が一つ減る
            Count-=1
    # 答えを格納
    Ans[i-1]=Count
 
# i=1~N
for i in range(1,N+1):
    # 答えの出力
    print(Ans[i])

ABC230 A

# 入力の受け取り
N=int(input())
 
# Nが42未満ならば
if N<42:
    # Nを文字列へ変換
    Nstr=str(N)
    # 桁数が1なら
    if len(Nstr)==1:
        # 「AGC」+「00」+「N」を出力
        print("AGC"+"00"+Nstr)
    # そうでなければ(桁数が2ならば)
    else:
        # 「AGC」+「0」+「N」を出力
        print("AGC"+"0"+Nstr)
else:
    # (N+1)を文字列へ変換
    Nstr=str(N+1)
    # 桁数が1なら
    if len(Nstr)==1:
        # 「AGC」+「00」+「N」を出力
        print("AGC"+"00"+Nstr)
    # そうでなければ(桁数が2ならば)
    else:
        # 「AGC」+「0」+「N」を出力
        print("AGC"+"0"+Nstr)

# 入力の受け取り
N=int(input())
 
# Nが42未満ならば
if N<42:print("AGC"+str(N).zfill(3))
# それ以外(Nが42以上)
else:print("AGC"+str(N+1).zfill(3))

ABC230 B

# 入力の受け取り
S=input()
 
# Sの文字数
N=len(S)
 
# Tを作る
T="oxx"*(10**5)
 
# i=0~((Tの長さ)-N-1)
for i in range(len(T)-N):
    # Tのi文字目～(i+N-1)文字目がSと一致していたら
    if T[i:i+N]==S:
        # 「Yes」を出力
        print("Yes")
        # 終了
        exit()
 
# 「No」を出力
print("No")

# 入力の受け取り
S=input()
 
# SがTに含まれるなら「Yes」
if S in "oxx"*(10**5):print("Yes")
# そうでないなら「No」
else:print("No")

ABC230 C

# 入力の受け取り
N,A,B=map(int,input().split())
P,Q,R,S=map(int,input().split())
 
# 1つ目の操作：Kの下限(左辺)
k1L=max(1-A,1-B)
# 1つ目の操作：Kの上限(右辺)
k1R=min(N-A,N-B)
 
# 2つ目の操作：kの下限(左辺)
k2L=max(1-A,B-N)
# 2つ目の操作：kの上限(右辺)
k2R=min(N-A,B-1)
 
# 左上の(行,列)
LeftUpGyou,LeftUpRetu=A+k1L,B+k1L
# 右下の(行,列)
RightRowGyou,RightLowRetu=A+k1R,B+k1R
# 右上の(行,列)
RightUpGyou,RightUpRetu=A+k2L,B-k2L
# 左下の(行,列)
LeftLowGyou,LeftLowRetu=A+k2R,B-k2R
 
# 答え：最初は全てのマスが白
# 0インデックスのため「Q-P+1」(行数)+1,「S-R+1」(列数)+1
Ans=[["."]*(S-R+1+1) for i in range(Q-P+1+1)]
 
# 行：Y=P~Q
for Y in range(P,Q+1):
    # 列：X=R~S
    for X in range(R,S+1):
        # 左上~右下の範囲にあるかチェック
        if LeftUpGyou<=Y<=RightRowGyou and LeftUpRetu<=X<=RightLowRetu:
            # 黒マスかどうかのチェック
            if Y-LeftUpGyou==X-LeftUpRetu:
                # 黒に塗る
                Ans[Y-P+1][X-R+1]="#"
        # 右上~左下の範囲にあるかチェック
        if RightUpGyou<=Y<=LeftLowGyou and LeftLowRetu<=X<=RightUpRetu:
            # 黒マスかどうかのチェック
            if LeftLowGyou-Y==X-LeftLowRetu:
                # 黒に塗る
                Ans[Y-P+1][X-R+1]="#"
 
# 行：Y=1~((Q-P+1+1)-1)
for Y in range(1,Q-P+1+1):
    # Y行,1列目~を結合して出力
    print("".join(Ans[Y][1:]))

ABC230 D

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

ABC230 E

# 入力の受け取り
N=int(input())
 
# 答え
ans=0
 
# [√N]を計算
from math import sqrt
Nroot=int(sqrt(N))
 
# [N/i]=kとなるもの
# k=1~[√N]まで
for k in range(1,Nroot+1):
    # kとなるものが([N/k]-[N/(k+1)])個
    ans+=k*(int(N/k)-int(N/(k+1)))
 
# [N/i]を計算
# i=1~([N/([√N]+1)])まで
for i in range(1,int(N/(Nroot+1))+1):
    # 答えの計算
    ans+=int(N/i)
 
# 答えを出力
print(ans)

ABC231 A

# 入力の受け取り
D=int(input())
 
# (D/100)を出力
print(D/100)

ABC231 B

# 入力の受け取り
N=int(input())
 
# 投票先
Votes=[]
 
# 候補者の種類
Candidates=set()
 
# N回
for i in range(N):
    # 入力の受け取り
    S=input()
    # 投票先を記録
    Votes.append(S)
    # セットに追加(重複しているものは入らない)
    Candidates.add(S)
 
# 答え候補者名
AnsName=""
# 得票数
AnsCount=0
 
# Candidatesの要素を順にNameへ入れて処理
for Name in Candidates:
    # 候補者Nameの得票数
    Count=Votes.count(Name)
 
    # 暫定の答え候補者より得票数が多ければ
    if AnsCount<Count:
        # 答えを更新
        AnsName=Name
        # 得票数を更新
        AnsCount=Count
 
# 答えを出力
print(AnsName)

# 入力の受け取り
N=int(input())
 
# defaultdictをインポート
from collections import defaultdict
 
# キー：候補者　値：投票数
Names=defaultdict(int)
 
# 答えの候補者名、投票数
AnsName=""
AnsVote=0
 
# N回
for i in range(N):
    # 入力の受け取り
    S=input()
 
    # 投票数を+1
    Names[S]+=1
 
    # 投票数が暫定答えの投票数を上回っていたら
    if AnsVote<Names[S]:
        # 答えを変更
        AnsName=S
        # 答えの投票数を更新
        AnsVote=Names[S]
 
# 答えを出力
print(AnsName)

ABC231 C

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

ABC231 D

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

ABC232 A

# 入力の受け取り
S=input()
 
# Sの0文字目と2文字目を整数へ変換
S0=int(S[0])
S2=int(S[2])
 
# 掛け算して出力
print(S0*S2)

ABC232 B

# 入力の受け取り
S=input()
T=input()
 
# K文字後ろへ変換後の文字を返す関数
def Conv(S,K):
    # 変換後のS
    SConverted=""
   
    # i=0~(Sの文字数-1)
    for i in range(len(S)):
        # 「文字」→「文字コード」
        Code=ord(S[i])
        # K個後ろの文字へ変換
        # 「変換先文字コード」=(「変換元文字コード｣-97+x)%26+97
        CodeCoverted=(Code+K-97)%26+97
        # 「文字コード」→「文字」へ変換して末尾へくっつける
        SConverted+=chr(CodeCoverted)
 
    return SConverted
 
# K=0~25
for K in range(26):
   
    # SとTの変換後が一致したら
    if Conv(S,K)==T:
        # 「Yes」を出力
        print("Yes")
        # 途中終了
        exit()
 
# 「No」を出力
print("No")

ABC232 C

# 入力の受け取り
N,M=map(int,input().split())
 
# 高橋くんのおもちゃについてどこがつながっているか
Takahashi=[[False]*(N+1) for i in range(N+1)]
 
# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int,input().split())
    # AとBがつながっている
    Takahashi[A][B]=True
    Takahashi[B][A]=True
 
# 青木くん側の入力内容
AokiInput=[]
# M回
for i in range(M):
    # 入力の受け取り
    C,D=map(int,input().split())
    # 入力を記録
    AokiInput.append([C,D])
 
# itertoolsをインポート
import itertools
# 順列を作成
# 例：N=4　P=(1,2,3,4),(1,2,4,3),...,(4,3,2,1)
for P in itertools.permutations(range(1,N+1)):
    # 青木くんのおもちゃについてどこがつながっているか
    Aoki=[[False]*(N+1) for i in range(N+1)]
 
    # 入力を取り出し
    for C,D in AokiInput:
        # 変換後のC
        CConv=P[C-1]
        # 変換後のD
        DConv=P[D-1]
 
        # 変換後のCと変換後のDがつながっている
        Aoki[CConv][DConv]=True
        Aoki[DConv][CConv]=True
 
    # 全てのおもちゃについてTakahashiとAokiが一致しているか
    OK=True
 
    # x=1~N
    for x in range(1,N+1):
        # y=1~N
        for y in range(1,N+1):
            # 両方ともxとyがつながっているか
            # つながっていなかったら
            if Takahashi[x][y]!=Aoki[x][y]:
                # Falseへ変更
                OK=False
   
    # Falseへ変更されていなければ
    if OK==True:
        # 「Yes」を出力
        print("Yes")
        # 終了
        exit()
 
# 「No」を出力
print("No")

ABC232 D

# 入力の受け取り
H,W=map(int,input().split())
 
# グリッド
Grid=[]
 
# H回
for i in range(H):
    # 入力の受け取り
    Ci=input()
    # 一文字ずつリストへ
    CiList=list(Ci)
    # グリッドへ追加
    Grid.append(CiList)
 
# そこに至るまでに通ったマスの数を記録
# (1)全マスに「0」を書く
GridCount=[[0]*W for i in range(H)]
 
# dequeをインポート
from collections import deque
que=deque()
 
# (2)(0,0)に「1」を書き、キューに入れる
GridCount[0][0]=1
 
# キューへ追加
que.append([0,0])
 
# (6)(3)~(5)をキューが空になるまで繰り返す
while 0<len(que):
    # (3)キューからの左端から要素を取り出す(=「今いるマス」の(行,列))
    G,R=que.popleft()
    # (4)「今いるマス」の数字を確認する
    NowCount=GridCount[G][R]
   
    # (5)下マス(行+1,列)、右マス(行,列+1)について
    # ・グリッドを飛び出していない　かつ　壁でない　場合
    if G+1<H and Grid[G+1][R]==".":
        # ・(下、右マスに書いている数)く(「今いるマス」+1)であれば
        if GridCount[G+1][R]<NowCount+1:
            # 下、右マスに(「今いるマス」+1)を書く
            GridCount[G+1][R]=NowCount+1
            # キューに下マス(行+1,列)、右マス(行,列+1)を追加
            que.append([G+1,R])
 
    # ・グリッドを飛び出していない　かつ　壁でない　場合
    if R+1<W and Grid[G][R+1]==".":
        # ・(下、右マスに書いている数)く(「今いるマス」+1)であれば
        if GridCount[G][R+1]<NowCount+1:
            # 下、右マスに(「今いるマス」+1)を書く
            GridCount[G][R+1]=NowCount+1
            # キューに下マス(行+1,列)、右マス(行,列+1)を追加
            que.append([G,R+1])
 
# 答え
ans=0
 
# 最大の数が書いているマスを探索
# G=0~(H-1)
for G in range(H):
    # R=0~(W-1)
    for R in range(W):
        # カウント数がansより大きければ更新
        ans=max(ans,GridCount[G][R])
 
# 答えを出力
print(ans)

ABC233 A

# 入力の受け取り
X,Y=map(int,input().split())
 
# Y≤Xならば
if Y<=X:
    # 「0」を出力
    print(0)
 
else:
    # ・(Y-X)が10で割り切れる
    if (Y-X)%10==0:
        # (Y-X)//10を出力
        print((Y-X)//10)
    # (Y-X)が10で割り切れない(上記以外)
    else:
        # (Y-X)//10+1を出力
        print((Y-X)//10+1)

# 入力の受け取り
X,Y=map(int,input().split())
 
# mathのインポート
import math
 
# ((Y-X)/10)と0のうち大きい方を出力
# (Y<Xで(Y-X)/10がマイナスになったときは0を出力する)
print(max(0,math.ceil((Y-X)/10)))

ABC233 B

# 入力の受け取り
L,R=map(int,input().split())
S=input()
 
# Sの(L-1)～(R-1)文字目
SCenter=S[L-1:R]
 
# 中央を反転
SCenter=SCenter[::-1]
 
# 結合を結合
S=S[:L-1]+SCenter+S[R:]
 
# 答えの出力
print(S)

ABC233 C

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

ABC233 D

# 入力の受け取り
N,K=map(int,input().split())
# A[0]を適当な数(=0)で埋めておく
A=[0]+list(map(int,input().split()))
 
# Aの累積和
ACum=[0]*(N+1)
 
# i=1~N
for i in range(1,N+1):
    # 累積和を計算
    ACum[i]=ACum[i-1]+A[i]
 
# defaultdictをインポート
from collections import defaultdict
# 出現個数を数える連想配列
Count=defaultdict(int)
 
# 答えをカウント
ans=0
 
# i=1~Nまで
for i in range(1,N+1):
    # ACum[i-1]が増える
    Count[ACum[i-1]]+=1
    # ACum[i]-Kとなるものをカウント
    ans+=Count[ACum[i]-K]
 
# 答えを出力
print(ans)

ABC233 E

# 入力の受け取り
X=input()
 
# N：Xの桁数
N=len(X)
 
# 各桁ごとの計算結果
d=[0]*(N)
# 最大桁=左から0桁目はX[0]
d[0]=int(X[0])
 
# i=1~N-1
for i in range(1,N):
    # 各桁の値を計算
    d[i]=d[i-1]+int(X[i])
 
# 桁の小さい順に確定させていく
# i=(N-1)~1
for i in range(N-1,0,-1):
    # 繰り上がり=10で割った商を足す
    d[i-1]+=d[i]//10
    # 右から1桁目が確定の値
    d[i]=str(d[i]%10)
 
# 一番大きい桁を文字列へ
d[0]=str(d[0])

# 結合
ans="".join(d)
 
# 答えの出力
print(ans)

ABC234 A

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

ABC234 B

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

ABC234 C

# 入力の受け取り
K=int(input())
 
# 2進数へ変換
Kbit=bin(N)
 
# 「1」→「2」へ変換
ans=Kbit.replace("1","2")
 
# 答えの出力
# 0文字目、1文字目は不要のため2文字目～
print(ans[2:])

ABC234 D

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

ABC234 E

# 等差数を作る関数
# 引数：a(初項),d(公差),n(桁数)　返り値：対応する等差数　作れなかったら「-1」
def MakeNum(a,d,n):
    # 等差数
    Num=""
    # n桁分
    # i=0~(n-1)
    for i in range(n):
        # i桁目
        x=a+d*i
        # 0以上9以下になっていれば
        if 0<=x<=9:
            # i桁目を記録
            Num+=str(x)
        # そうでなければ
        else:
            # 「-1」を返す
            return -1
    # 整数にして返す
    return int(Num)
 
# 等差数を記録するリスト
NumList=[]
 
# 初項：1~9
for a in range(1,10):
    # 公差：-9~9
    for d in range(-9,10):
        # 桁数：1~18
        for n in range(1,19):
            # 対応する等差数を作る
            Num=MakeNum(a,d,n)
            # 「-1」でなければ
            if Num!=-1:
                # 追加
                NumList.append(Num)
 
# ソート
NumList.sort()
 
# 入力の受け取り
X=int(input())
 
# 初めてX以上になるところを確認
i=0
while NumList[i]<X:
    i+=1
 
# 答えの出力
print(NumList[i])

ABC235 A

# 入力を受け取り
X=input()
 
# a=0文字目
a=X[0]
# b=1文字目
b=X[1]
# c=2文字目
c=X[2]
 
# a,b,cを結合
abc=a+b+c
# b,c,aを結合
bca=b+c+a
# c,a,bを結合
cab=c+a+b
 
# 整数へ変換
abc=int(abc)
bca=int(bca)
cab=int(cab)
 
# 答えの出力
print(abc+bca+cab)

ABC235 B

# 入力を受け取り
N=int(input())
H=list(map(int,input().split()))
 
# 今立っている場所のインデックス番号
i=0
 
# 右端の台でなく　かつ　右の台のほうが高ければ
while i<N-1 and H[i]<H[i+1]:
    # 右の台へ移動
    i+=1
 
# 答えの出力
print(H[i])

ABC235 C

# 入力を受け取り
N,Q=map(int,input().split())
a=list(map(int,input().split()))
 
# defaultdictのインポート
from collections import defaultdict
 
# 何回目に出てきた数かカウントする連想配列
Count=defaultdict(int)
# k回目のxが出てくるインデックス番号
Indx=defaultdict(int)
 
# i=0~(N-1)
for i in range(N):
    # Count[a[i]]をプラス1
    Count[a[i]]+=1
    # インデックス番号を記録
    # 0インデックスなのでi+1とすることに注意
    Indx[(a[i],Count[a[i]])]=i+1
 
# Q回
for i in range(Q):
    # 入力の受け取り
    x,k=map(int,input().split())
    # k回目のxが存在しない場合
    # ⇔デフォルトの値=0が記録されている場合
    if Indx[(x,k)]==0:
        # 「-1」を出力
        print(-1)
    # そうでない場合
    else:
        # 答えを出力
        print(Indx[(x,k)])

ABC235 D

# 入力の受け取り
a,N=map(int,input().split())
 
# (1)1~999999までの操作回数リストを用意する(初期値は全て-1回)
Count=[-1]*10**6
 
# dequeのインポート
from collections import deque
que=deque()
 
#  (2)操作回数リストの「1」に0回と書き、キューへ入れる
# キューに「1」を追加
que.append(1)
# 「1」への操作回数は0
Count[1]=0
 
# (6)(3)~(5)をキューが空になるまで繰り返す
while 0<len(que):
    # (3)キューからの左端から要素(=「今黒板に書いている数」)を取り出す
    Now=que.popleft()
 
    # (4)「今黒板に書いている数」の操作回数を確認する
    c=Count[Now]
 
    # (5)2種の操作を行う
    # a倍する
    To=Now*a
    # ・「今黒板に書いている数」をa倍した数が10^6未満の場合
    if To<10**6:
        # ・まだ一度も出てきていない数なら(操作回数が-1回)
        if Count[To]==-1:
            # 操作回数に(「今黒板に書いている数」の操作回数+1)を記録
            Count[To]=c+1
            # キューへ追加
            que.append(To)
   
    # ・「今黒板に書いている数」が10より大きい　かつ　10で割り切れない　場合
    if 10<=Now and Now%10!=0:
        # 文字列へ変換
        NowStr=str(Now)
        # 末尾を先頭へ持っていく
        ToStr=NowStr[-1]+NowStr[:-1]
        # 整数へ変換
        To=int(ToStr)
        # ・まだ一度も出てきていない数なら(操作回数が-1回)
        if Count[To]==-1:
            # 操作回数に(「今黒板に書いている数」の操作回数+1)を記録
            Count[To]=c+1
            # キューへ追加
            que.append(To)
 
# 答えの出力
print(Count[N])