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

ABC211~220
https://qiita.com/sano192/items/03c27d4316af25bdf645

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

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

ABC201 A

提出

# 入力の受け取り
A1,A2,A3=map(int, input().split())

# (A1,A2,A3) → A3-A2=A2-A1ならば
if A3-A2==A2-A1:
    # 「Yes」を出力
    print("Yes")
# (A1,A3,A2) → A2-A3=A3-A1ならば
elif A2-A3==A3-A1:
    print("Yes")
# (A2,A1,A3) → A3-A1=A1-A2ならば
elif A3-A1==A1-A2:
    print("Yes")
# (A2,A3,A1) → A1-A3=A3-A2ならば
elif A1-A3==A3-A2:
    print("Yes")
# (A3,A1,A2) → A2-A1=A1-A3ならば
elif A2-A1==A1-A3:
    print("Yes")
# (A3,A2,A1) → A1-A2=A2-A3ならば
elif A1-A2==A2-A3:
    print("Yes")
# そうでなければ
else:
# 「No」を出力
    print("No")

別解

# 入力をリストとして受け取り
A=list(map(int, input().split()))

# 小さい順に並び替え
A.sort()

# A[2]-A[1]=A[1]-A[0]ならば
if A[2]-A[1]==A[1]-A[0]:
    # 「Yes」を出力
    print("Yes")
# そうでないなら
else:
    # 「Noを出力」
    print("No")

ABC201 B

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

ABC201 C

提出

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

# 暗証番号としてありうるものをカウントする変数
count=0

# num=0~9999まで
for num in range(10000):
    # 暗証番号として適するならTrue,適さないならFalse
    OK=True

    # numを文字列へ変換
    num=str(num)
    # 4桁になるよう先頭に0埋め
    num=num.zfill(4)

    # i=0~9まで
    for i in range(10):
        # S[i]が「○」なら
        if S[i]=="o":
            # iがnumに含まれていなければ
            if str(i) not in num:
                # 暗証番号に適さない
                OK=False
        # S[i]が「x」なら
        if S[i]=="x":
            # iがnumに含まれるなら
            if str(i) in num:
                # 暗証番号に適さない
                OK=False

    # 暗証番号に適していれば
    if OK==True:
        # カウントする
        count+=1

# 答えの出力
print(count)

ABC202 A

提出

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

# 21-(a+b+c)を出力
print(21-(a+b+c))

ABC202 B

提出

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

# Sを反転
S=S[::-1]

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

# Sの文字をそれぞれxへ
for x in S:
    # x=「0」ならば
    if x=="0":
        # 「0」を末尾へ追加
        ans+="0"
    # x=「1」ならば
    elif x=="1":
        # 「1」を末尾へ追加
        ans+="1"
    # x=「6」ならば
    elif x=="6":
        # 「9」を末尾へ追加
        ans+="9"
    # x=「8」ならば
    elif x=="8":
        # 「8」を末尾へ追加
        ans+="8"
    # x=「9」ならば
    elif x=="9":
        # 「6」を末尾へ追加
        ans+="6"

# 答えを出力
print(ans)

別解

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

# Sを反転
S=S[::-1]

# Sをリストへ
S_list=list(S)

# i=0~(S_listの長さ)-1
for i in range(len(S_list)):
    # 6ならば9へ
    if S_list[i]=="6":S_list[i]="9"
    # 9ならば6へ
    elif S_list[i]=="9":S_list[i]="6"

# リストを結合
ans="".join(S_list)

# 答えを出力
print(ans)

ABC202 C

提出

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

# 0番目を埋めるため[0]とする
A=[0]+list(map(int, input().split()))
B=[0]+list(map(int, input().split()))
C=[0]+list(map(int, input().split()))

# B_Cjの値を格納するリスト
B_Cj=[0]*(N+1)
# j=1~Nまで
for j in range(1,N+1):
    # B_(Cj)の値を確認
    B_Cj[j]=B[C[j]]

# Aの値をカウントするリスト
# 例：A_count[2]=3だったらAに「2」が3個ある
A_count=[0]*(N+1)
# i=1~Nまで
for i in range(1,N+1):
    # Aの値を確認し、カウントしていく
    A_count[A[i]]+=1

# B_Cjの値をカウントするリスト
B_Cj_count=[0]*(N+1)
# i=1～Nまで
for i in range(1,N+1):
    # B_Cjの値を確認し、カウントしていく
    B_Cj_count[B_Cj[i]]+=1
 
# 答えを格納する変数
ans=0

# i=1~Nまで
for i in range(1,N+1):
    # (Aにiが含まれる個数)×(B_(Cj)に2が含まれる個数)
    ans+=A_count[i]*B_Cj_count[i]

# 答えの出力
print(ans)

ABC202 D

提出

# 階乗
from math import factorial
 
# nCr
# 引数：n,r→戻り値：nCr
def nCr(n,r):
    # 分子
    numerator=factorial(n)
    # 分母
    denominator=factorial(n-r)*factorial(r)
    # (分子)/(分母)を返す
    return numerator//denominator

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

# 答え
ans=""

# 『「確定した文字」＋「○○...○」のうち辞書順最初のもの』は何番目か
num=1

# A(「a」の残り個数)かB(「b」の残り個数)が0より大きい間
while 0<A or 0<B:
    # もしAが0ならば
    if A==0:
        # 「b」を末尾へ
        ans+="b"
        # 「b」の数を1個減らす
        B-=1
        # 繰り返し
        continue

    # もしBが0ならば
    if B==0:
        # 「a」を末尾へ
        ans+="a"
        # 「a」の数を減らす
        A-=1
        # 繰り返し
        continue

    # 『残り部分の最初の文字が「b」』の辞書順最初の文字が何番目か
    # ⇔num+『残り部分の最初の文字が「a」である場合の順列の数』
    # ⇔num+『「a」が(A-1)個、「b」がB個の順列の数』
    b_start=num+nCr(A-1+B,B)

    # もしKがb_startより小さいならば
    if K<b_start:
        # 末尾に「a」を追加
        ans+="a"
        # 「a」の数を1個減らす
        A-=1

    # そうでないなら(もしb_start<=Kならば)
    else:
        # 末尾に「b」を追加
        ans+="b"
        # 辞書順で(b_start)番目
        num=b_start
        # 「b」の数を1個減らす
        B-=1

# 答えの出力        
print(ans)

別解

# 再帰回数上限を10^6回へ変更
# 再帰関数を使うときは必ず書く
import sys
sys.setrecursionlimit(10**6)

# コンビネーションを計算できるようインポート
from scipy.special import comb

# 引数：A(「aの数」),B(「b」の数),num(『確定した文字列のうち、辞書順最初のもの』が何番目か),ans(確定した文字列)
def solve(A,B,num,ans):
    # 「a」,「b」の残り個数が0個なら
    if A==0 and B==0:
        # 答えを出力
        print(ans)
        # 終了
        exit()

    # 「a」の残り個数が0なら
    elif A==0:
        # 「b」を末尾に置いて関数を呼ぶ
        solve(A,B-1,num,ans+"b")
    # 「b」の残り個数が0個なら
    elif B==0:
        # 「a」を末尾に置いて関数を呼ぶ
        solve(A-1,B,num,ans+"a")

    # 『残り部分の最初の文字が「b」』の辞書順最初の文字が何番目か
    b_start=num+comb(A-1+B,B,exact=True)

    # K<b_startならば
    if K<b_start:
        # 「a」を末尾に置いて関数を呼ぶ
        solve(A-1,B,num,ans+"a")
    else:
        # 「b」を末尾に置いて関数を呼ぶ
        solve(A,B-1,b_start,ans+"b")

# 入力の受け取り
A,B,K=map(int,input().split())
# 関数を呼ぶ
solve(A,B,1,"")

ABC203 A

提出

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

# a=bの場合
if a==b:
    # cを出力
    print(c)
# b=cの場合
elif b==c:
    # cを出力
    print(a)
# c=aの場合
elif c==a:
    # cを出力
    print(b)
# それ以外(同じものがない場合)
else:
    # 0を出力
    print(0)

ABC203 B

提出

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

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

# i=1~Nまで
for i in range(1,N+1):
    # j=1~Kまで
    for j in range(1,K+1):
        # 部屋番号=100*i+jを答えに足す
        ans+=100*i+j

# 答えを出力
print(ans)

ABC203 C

提出

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

# 友達の情報を格納するリスト
friends=[]
# N回
for i in range(N):
    # 入力の受け取り
    A,B=map(int, input().split())
    # 情報を格納
    friends.append([A,B])

# 近い順にソート
friends.sort()

# 今いる村
now_village=0

# K円進む
now_village+=K

# i=1~Nまで
for i in range(N):
    # i番目の友達の村
    friend_village=friends[i][0]
    # i番目の友達がくれるお金
    money=friends[i][1]

    # もしi番目の友達が今いる村より前にいれば
    if friend_village<=now_village:
        # お金をもらってさらに進む
        now_village+=money
    # そうでなければ
    else:
        # 進めない
        # for文を抜ける
        break

# 今いる村を出力
print(now_village)

ABC204 A

提出

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

# x,yの値で場合分け
if x==0 and y==0:
    print(0)
elif x==0 and y==1:
    print(2)
elif x==0 and y==2:
    print(1)    
elif x==1 and y==0:
    print(2)
elif x==1 and y==1:
    print(1)
elif x==1 and y==2:
    print(0)    
elif x==2 and y==0:
    print(1)
elif x==2 and y==1:
    print(0)
elif x==2 and y==2:
    print(2)

別解

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

# x=yならばxを出力
if x==y:print(x)
# x≠yならx,yではないものを出力
else:print(3-x-y)

ABC204 B

提出

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

ABC204 C

提出

# 入力の受け取り
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_city):
    # 行ける都市を数える変数
    # スタート都市→スタート都市には必ず行けるから1
    count=1

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

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

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

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

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

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

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

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

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

# 答えの出力
print(ans)

ABC204 D

提出

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

ABC205 A

提出

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

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

ABC205 B

提出

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

# 数1,2,3,...Nが存在するかチェックするリスト
numbers=[False]*(N+1)

# i=0~(N-1)まで
for i in range(N):
    # A[i]が存在する⇔numbers[A[i]]=True
    numbers[A[i]]=True

# i=1~Nまで
for i in range(1,N+1):
    # numbers[i]=False⇔iが存在しないなら
    if numbers[i]==False:
        # Noを出力
        print("No")
        # 終了
        exit()

# Yesを出力
print("Yes")

別解

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

# Aをソート
A.sort()

# A=[1,2,3,...,N]ならば
if A==list(range(1,N+1)):
    # Yesを出力
    print("Yes")
# そうでなければ
else:
    # Noを出力
    print("No")

ABC205 C

提出

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

ABC205 D

提出

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

# Aの両端に0,大きい数(10^20)を追加
A=[0]+A+[10**20]

# クエリ格納用
query=[]

# Q回
for i in range(Q):
    # 入力の受け取り
    K=int(input())
    # クエリを格納
    query.append([K,i])

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

# 「A[i]より前の良い整数の数」
# 最初は0
order_left=0

# x番目のクエリ
x=0

# i=0~Nまで
for i in range(N+1):
    # 「A[i+1]より前の良い整数の数」=「A[i]より前の良い整数の数」+(A[i+1]+A[i]-1)
    order_right=order_left+A[i+1]-A[i]-1
    # x<Qの間
    while x<Q:
        # クエリの値
        K=query[x][0]
        # クエリの番号(q番目のクエリ)
        q=query[x][1]
        # 「A[i]より前の良い整数の数」<クエリの値≦「A[i+1]より前の良い整数の数」ならば
        if order_left<K<=order_right:
            # q番目のクエリの値=A[i]+(K-「A[i]より前の良い整数の数」)
            ans[q]=A[i]+(K-order_left)
            # 次のxへ
            x+=1
        # そうでない場合(「A[i+1]より前の良い整数の数」≦クエリの値)
        else:
            # 「A[i]より前の良い整数の数」=「A[i+1]より前の良い整数の数」へ更新
            order_left=order_right
            # 次のiへ
            break

# 答えを出力
for x in ans:
    print(x)

別解

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

# Aの両端に0,大きい数(10^20)を追加
A=[0]+A+[10**20]

# 「A[i]より前の良い整数の数」
A_num=[0]*(N+2)

# i=0~N
for i in range(N+1):
    # 「A[i+1]より前の良い整数の数」=「A[i]より前の良い整数の数」+(A[i+1]-A[i]-1)
    A_num[i+1]=A_num[i]+(A[i+1]-A[i]-1)

# 二分探索
# 引数：K　→　返り値：K番目の「良い整数」
def Nibutan(K):
    # 右端
    l=0
    # 左端
    r=N+1

    # 左と右の差が1の間
    while 0<r-l:
        # 真ん中
        c=(l+r)//2
        # 「A[i]より前の良い整数の数」<K≦「A[i+1]より前の良い整数の数」ならば
        if A_num[c]<K<=A_num[c+1]:
            # A[i]+(K-「A[i]より前の良い整数の数」)
            return A[c]+(K-A_num[c])
        # K<=A_num[c]ならば
        elif K<=A_num[c]:
            # 右端→真ん中へ更新
            r=c
        # それ以外(A_num[c+1]<x)ならば
        else:
            # 左端→真ん中へ更新
            l=c

# Q回
for i in range(Q):
    # 入力の受け取り
    K=int(input())
    # 計算して出力
    print(Nibutan(K))

ABC206 A

提出

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

# N<191の場合
if N<191:
    # Yay!を出力
    print("Yay!")
# N=191の場合
elif N==191:
    # so-soを出力
    print("so-so")
# それ以外(191<N)の場合
else:
    # :(を出力
    print(":(")

ABC206 B

提出

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

# 貯金額
money=0

# i=1~10^5
for i in range(1,10**5+1):
    # i日目　i円を貯金箱へ
    money+=i
    # 貯金額がN以上ならば
    if N<=money:
        # iを出力
        print(i)
        # 終了
        exit()

ABC206 C

提出

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

ABC206 D

提出

# UnionFind
class UnionFind:
    def __init__(self, n):
        self.n=n
        self.parent_size=[-1]*n
    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 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 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=int(input())
A=list(map(int, input().split()))
 
# 初期化【O(N)】：変数名=UnionFind(要素の数)
UF=UnionFind(10**6)
 
# 答えを格納する変数
ans=0
 
# i=0~(N//2-1)まで
for i in range(N//2):
    # 左側
    A_left=A[i]
    # 右側
    A_right=A[N-i-1]
    # 同一グループかの確認【だいたいO(1)】：変数名.same(要素番号1,要素番号2)
    # (同一ならTrue,違うグループならFalseを返す)
    # 左側と右側が違うグループなら
    if UF.same(A_left,A_right)==False:
        # 答えに+1
        ans+=1
        # グループの併合【だいたいO(logN)】：変数名.merge(要素番号1,要素番号2)
        UF.merge(A_left,A_right)
 
# 答えを出力
print(ans)

ABC207 A

提出

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

# (A+B),(B+C),(C+A)のうち、一番大きいものを出力
print(max(A+B,B+C,C+A))

ABC207 B

提出

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

# mathのインポート
import math

# (C*D-B)が0以下の場合
if (C*D-B)<=0:
    # -1を出力
    print(-1)

# そうでない場合((C*D-B)がプラスの場合)
else:
    # (A/(C*D-B)を切り上げ
    ans=math.ceil((A/(C*D-B)))
    # 答えの出力
    print(ans)

ABC207 C

提出

# 入力の受け取り
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の左端
        i_l=section[i][0]
        # 区間iの右端
        i_r=section[i][1]
        # 区間jの左端
        j_l=section[j][0]
        # 区間jの右端
        j_r=section[j][1]

        # (区間iの左端)≤(区間jの左端)≤(区間iの右端)
        if i_l<=j_l<=i_r:
            # 答えにカウント
            ans+=1
        # (区間iの左端)≤(区間jの右端)≤(区間iの右端)
        elif i_l<=j_r<=i_r:
            # 答えにカウント
            ans+=1        
        # (区間jの左端)≤(区間iの左端)≤(区間jの右端)
        elif j_l<=i_l<=j_r:
            # 答えにカウント
            ans+=1        
        # (区間jの左端)≤(区間iの右端)≤(区間jの右端)
        elif j_l<=i_r<=j_r:
            # 答えにカウント
            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の右端,左端
        i_l,i_r=section[i]
        j_l,j_r=section[j]
       
        # max(区間iの左端,区間jの左端)≤min(区間iの右端,区間jの右端)ならば
        # 答えにカウント
        if max(i_l,j_l)<=min(i_r,j_r):ans+=1

# 答えの出力
print(ans)

ABC208 A

提出

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

# A≤B≤6Aの時
if A<=B<=6*A:
    # 「Yes」を出力
    print("Yes")
# そうでない場合
else:
    # 「No」を出力
    print("No")

ABC208 B

提出

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

# 答えを格納する変数
ans=0
# mathのインポート
import math

# x=10~0まで、-1ずつ
for x in range(10,0,-1):
    # i!円のコイン
    coin=math.factorial(x)

    # コインよりPが大きい間
    while coin<=P:
        # コインを使う
        ans+=1
        # 使った分をマイナス
        P-=coin

# 答えを出力
print(ans)

ABC208 C

提出

# 入力の受け取り
N,K=map(int, input().split())
a=list(map(int, input().split()))
 
# aをソートした数列
a_sort=sorted(a)
 
# 国民番号→順序(小さい方から何番目か)への変換
number_order=dict()
 
# i=0~(N-1)
for i in range(N):
    # 国民番号→順序への変換
    number_order[a_sort[i]]=i+1
 
# K÷Nの商
syou=K//N
# K÷Nの余り
amari=K%N
 
# i=0~(N-1)
for i in range(N):
    # 順序が(K÷Nの余り)以下なら
    if number_order[a[i]]<=amari:
        # 商+1を出力
        print(syou+1)
    # そうでないなら(順序が(K÷Nの余り)より大きいなら)
    else:
        # 商を出力
        print(syou)

ABC208 D

提出

# pypyで提出

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

# 到達不可能時間(大きすぎるとTLEするので注意)
inf=10**10
# 時間表
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)

ABC209 A

提出

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

# A≤Bならば
if A<=B:
    # (B-A+1)を出力
    print(B-A+1)
# そうでなければ(B<Aならば)
else:
    # 0を出力
    print(0)

別解

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

# 「B-A+1」か「0」の大きい方を出力
print(max(B-A+1,0))

ABC209 B

提出

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

# 合計の値段を格納する変数
sum_price=0

# i=0~(N-1)まで
for i in range(N):
    # 奇数番目の商品=iが偶数
    # ⇔iを2で割った余りが0ならば
    if i%2==0:
        # 合計にA[i]を追加
        sum_price+=A[i]
    # 偶数番目の商品=iが奇数
    # ⇔iを2で割った余りが0でない(余りが1)
    else:
        # 合計にA[i]を追加
        sum_price+=A[i]-1

# もし合計がX以下ならば
if sum_price<=X:
    # Yesを出力
    print("Yes")
# そうでなければ(X<sum_priceならば)
else:
    # Noを出力
    print("No")

ABC209 C

提出

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

ABC209 D

提出

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

# 道路の情報受け取りリスト
connect=[[] for i in range(N+1)]

# (N-1)本の道路
for i in range(N-1):
    # 入力の受け取り
    a,b=map(int, input().split())
    # a,bがつながっていると記録
    # (例)connect[1]=[2,3,4]ならば街①と街②,3,4がつながっている
    connect[a].append(b)
    connect[b].append(a)

# (1)各街の色を記録するリストcolorsを作る
# 赤：0,青：1,まだ塗っていない：-1
colors=[-1]*(N+1)

# (2)訪問済みか記録するリストvisitedを作る
# visited[x]=Trueなら街xは訪問済み、=Falseなら未訪問
visited=[False]*(N+1)

# (3)キューを用意する
from collections import deque
que=deque()

# (4)街①を赤で塗る
colors[1]=0
# (5)街①を訪問済みにする
visited[1]=True

# (6)街①をキューに入れる
que.append(1)

# キューが空でない間
while 0<len(que):
    # (7)キューの左端から要素(街の番号)を取り出す(今いる街)
    now_town=que.popleft()
    # (8)今いる街の色を確認する
    now_color=colors[now_town]

    # (9)今いる街から行ける街を確認する
    for to_town in connect[now_town]:
        # ・もし行ける街が未訪問ならば
        if visited[to_town]==False:
            # (9-1)訪問済みに更新
            visited[to_town]=True
            # (9-2)今いる街の色と逆の色を塗る
            # 今いる街が赤色なら
            if now_color==0:
                # 青色を塗る
                colors[to_town]=1
            # 今いる街が青色なら
            if now_color==1:
                # 赤色を塗る
                colors[to_town]=0
            # (9-3)キューに追加する
            que.append(to_town)

# クエリの読み込み
for i in range(Q):
    # 入力の受け取り
    c,d=map(int, input().split())
    # 街の色が同じなら
    if colors[c]==colors[d]:
        # townを出力
        print("Town")
    # そうでないならば(街の色が違うなら)
    else:
        # Roadを出力
        print("Road")

ABC210 A

提出

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

# 買う個数がA個以下の場合
if N<=A:
    # NX円を出力
    print(N*X)
# そうでない場合(買う個数がA個より多い場合)
else:
    # AX+(N-A)Y円を出力
    print(A*X+(N-A)*Y)

ABC210 B

提出

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

# i=0~(N-1)
for i in range(N):
    # Sのi文字目が「1」の場合
    if S[i]=="1":
        # iが偶数ならば
        if i%2==0:
            # Takahashiを出力
            print("Takahashi")
        # iが奇数ならば
        else:
            # Aokiを出力
            print("Aoki")
        # 終了
        exit()

別解

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

# 最初の「1」が偶数番目
if S.find("1")%2==0:print("Takahashi")
# それ以外(最初の「1」が奇数番目)
else:print("Aoki")

ABC210 C

提出

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

# defaultdictのインポート
from collections import defaultdict
# int:デフォルトの値を0にする
colors=defaultdict(int)

# 色の種類数を数える変数
cnt=0

# i=0~(K-1)まで
for i in range(K):
    # c[i]の個数をプラス1
    colors[c[i]]+=1
    # c[i]の個数が0→1になったら
    if colors[c[i]]==1:
        # 色の種類数プラス1
        cnt+=1

# 答え　暫定答えをcntとする
ans=cnt

# i=1~(N-K)まで
for i in range(1,N-K+1):
    # c[i-1]の個数をマイナス1
    colors[c[i-1]]-=1
    # c[i-1]の個数が1→0になったら
    if colors[c[i-1]]==0:
        # 色の種類数マイナス1
        cnt-=1
    # c[i+K-1]の個数をプラス1
    colors[c[i+K-1]]+=1
    # c[i+K-1]の個数が0→1になったら
    if colors[c[i+K-1]]==1:
        # 色の種類数プラス1
        cnt+=1
    # cntのほうが大きかったら答えを更新
    ans=max(ans,cnt)

# 答えの出力
print(ans)