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

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

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

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

ABC221 A

提出

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

# 答えの出力
print(32**(A-B))

ABC221 B

提出

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

# S,Tが一致していれば
if S==T:
    # 「Yes」を出力
    print("Yes")
    # 終了
    exit()

# S,Tを一文字ずつリストへ
S_list=list(S)
T_list=list(T)

# i=0~(Sの文字数-2)
for i in range(len(S)-1):
    # i文字目と(i+1)文字目を交換
    S_list[i],S_list[i+1]=S_list[i+1],S_list[i]
    # S_listとT_listが一致していれば
    if S_list==T_list:
        # Yesを出力
        print("Yes")
        # 終了
        exit()
    # 交換したものをもとに戻す
    S_list[i],S_list[i+1]=S_list[i+1],S_list[i]

# 一致しないままforを抜けたらNoを出力
print("No")

ABC221 C

提出

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

ABC221 D

提出

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

# ログイン開始日
login=[]
# ログアウト日
logout=[]
# 開始または終了が起こる日(重複除去のためリスト)
event=set()

# N回受け取り
for i in range(N):
    # A,Bの受け取り
    A,B=map(int, input().split())
    # プレイヤーiのログイン開始日
    login.append(A)
    # プレイヤーiのログアウト日(ログインをやめた日)
    logout.append(A+B)
    # ログイン開始日を追加
    event.add(A)
    # ログアウト日を追加
    event.add(A+B)

# ログイン開始日,ログアウト日をソート
login.sort()
logout.sort()

# リストへ変換
event_list=list(event)
# ソート
event_list.sort()

# ログインしている人数
players=0

# 答えの格納リスト
ans=[0]*(N+1)

# ログイン開始日の確認用
a=0
# ログアウト日の確認用
b=0

# i=0~(eventの長さ-2)
for i in range(len(event_list)-1):
    # 今何日目か
    now=event_list[i]
    # now=ログイン開始日ならば
    while a<len(login) and login[a]==now:
        # プレイヤーがひとり増える
        players+=1
        # 次のログイン開始日を確認
        a+=1
    # now=ログアウト日ならば
    while b<len(logout) and logout[b]==now:
        # プレイヤーがひとり減る
        players-=1
        # 次のログアウト日を確認
        b+=1
   
    # ans[プレイヤー人数]に次の(「開始または終了が起こる日」-「今の日数」)をプラス
    ans[players]+=event_list[i+1]-now

# 答えの出力
print(*ans[1:])

ABC222 A

提出

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

# Nの長さが1なら
if len(N)==1:
    # 先頭に"000"をつけて出力
    print("000"+N)
# Nの長さが2なら
elif len(N)==2:
    # 先頭に"00"をつけて出力
    print("00"+N)
# Nの長さが3なら
elif len(N)==3:
    # 先頭に"0"をつけて出力
    print("0"+N)
# それ以外(Nの長さが4なら)
else:
    # 「N」を出力
    print(N)

別解

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

# 0埋めして出力
print(N.zfill(4))

ABC222 B

提出

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

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

# i=0~(N-1)
for i in range(N):
    # a[i]がP未満なら
    if a[i]<P:
        # 答えにプラス1
        count+=1

# 答えを出力
print(count) 

ABC221 C

提出

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

# 手の記録リスト
hands=[]

# 2N回
for i in range(2*N):
    # 受け取り
    A=input()
    # 記録
    hands.append(A)

# [勝数,選手番号]を格納するリスト
# 選手番号は0インデックスであることに注意
# (選手1は0,選手2は1,...,選手Nは(N-1))
wins=[]

# 全員勝数0で初期化
for i in range(2*N):
    wins.append([0,i])

# 試合の結果判定
# 引数：選手Aの手,選手Bの手 → 返り値；選手Aの追加勝数,選手Bの追加勝数
def judge(A_hand,B_hand):
    if A_hand=="G" and B_hand=="G":
        return 0,0
    elif A_hand=="G" and B_hand=="C":
        return 1,0
    elif A_hand=="G" and B_hand=="P":
        return 0,1
    if A_hand=="C" and B_hand=="G":
        return 0,1
    elif A_hand=="C" and B_hand=="C":
        return 0,0
    elif A_hand=="C" and B_hand=="P":
        return 1,0
    if A_hand=="P" and B_hand=="G":
        return 1,0
    elif A_hand=="P" and B_hand=="C":
        return 0,1
    elif A_hand=="P" and B_hand=="P":
        return 0,0

# Mラウンド(i=0~(M-1))
for i in range(M):
    # k=0~(N-1)
    for k in range(N):
        # 2k位と(2k+1)位の試合
        # 選手Aの番号(0インデックス)
        playerA=wins[2*k][1]
        # 選手Bの番号(0インデックス)
        playerB=wins[2*k+1][1]
        # 選手Aの出す手
        A_hand=hands[playerA][i]
        # 選手Bの出す手
        B_hand=hands[playerB][i]
        # A,Bに追加される勝数
        A_point,B_point=judge(A_hand, B_hand)
        # Aの勝数を計算(勝ったらマイナス1)
        wins[2*k][0]-=A_point
        # Bの勝数を計算(勝ったらマイナス1)
        wins[2*k+1][0]-=B_point
    # 勝数,番号順にソート
    wins.sort()

# i=0~(2N-1)
for i in range(2*N):
    # 答えの出力
    # 選手番号は0インデックスなのでプラス1
    print(wins[i][1]+1)

ABC222 D

提出

# pypyで提出
 
# 入力の受け取り
N=int(input())
# 0番を埋めるために[0]を先頭へ追加
A=[0]+list(map(int, input().split()))
B=[0]+list(map(int, input().split()))
 
# 余りの定義
mod=998244353
 
# (1)表を作る
# dp[i][x]：「項数=i、C[i]=xとなる数列の個数」
dp=[[0]*3001 for i in range(N+1)]

# (2)すぐにわかるところを埋める
# x=A[1]~B[1]
for x in range(A[1],B[1]+1):
    # dp[1][x]に1を埋める
    dp[1][x]=1

# (3)表の小さい方から答えにたどり着くまで埋める
# i=2~N
for i in range(2,N+1):
    # (i-1)行目の累積和(Cumulative Sum)
    # 累積和リストを作成
    cum_sum=[0]*(3001)
    # 0番目：cum_sum[0]=dp[i-1][0]
    cum_sum[0]=dp[i-1][0]
    # k=1~3000
    for k in range(1,3001):
        # 「k番目までの累積和」=「(k-1)番目までの累積和」+dp[i-1][k]
        cum_sum[k]=cum_sum[k-1]+dp[i-1][k]
        # 余りを取る
        cum_sum[k]%=mod
 
    # x=0~3000
    for x in range(3001):
        # A[i]≤x≤B[i]ならば
        if A[i]<=x<=B[i]:
            # dp[i][x]=「(i-1)行目のx番目までの累積和」
            dp[i][x]=cum_sum[x]

# (4)答えを出力する
# 表のN行目を全て足す
ans=sum(dp[N])
# 余りを取る
ans%=mod
# 答えの出力
print(ans)

ABC223 A

提出

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

# Xが100で割り切れる　かつ　X=0でないならば
if X%100==0 and X!=0:
    # Yesを出力
    print("Yes")
# そうでなければ(100で割り切れない　または　X=0)
else:
    # Noを出力
    print("No")

ABC223 B

提出

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

# 作った文字を格納するリスト
S_list=[]

# Sの文字数回処理する
for i in range(len(S)):
    # 左シフト
    S=S[1:]+S[0]
    # リストへ作った文字を追加
    S_list.append(S)

# ソートする
S_list.sort()

# 辞書順最小=リストの先頭を出力
print(S_list[0])
# 辞書順最大=リストの末尾を出力
print(S_list[-1])

ABC223 C

提出

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

# 入力の受け取りリスト
A=[]
B=[]

# 片方から火をつけて燃え尽きるまでの時間
full_time=0

# N回
for i in range(N):
    # 入力の受け取り
    a,b=map(int, input().split())
    # リストへ格納
    A.append(a)
    B.append(b)
    # 時間=距離/速さを足す
    full_time+=a/b

# 両端から火をつけたとき、燃え尽きるまでにかかる時間
# ⇔片方から火をつけて燃え尽きるまでの時間の半分
time=full_time/2

# 左端からtime秒ですすめる距離
dist=0

# i=0~(N-1)
for i in range(N):
    # もし残り時間内にi本目の導火線を全て燃やせるなら
    if A[i]/B[i]<=time:
        # 時間=距離/速さを計算して残り時間から引く
        time-=A[i]/B[i]
        # A[i]cm進む
        dist+=A[i]
    # そうでなければ(もし残り時間内にi本目の導火線を全て燃やせないなら)
    else:
        # 距離=速さ*時間 進む
        dist+=B[i]*time
        # 時間がなくなったので処理を終了する
        break

# 距離を出力
print(dist)

ABC223 D

提出

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

# 「入ってくる辺の数」をカウントするリスト
count=[0]*(N+1)
# つながっている辺の情報を格納するリスト
connect=[[] for i in range(N+1)]

# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int, input().split())
    # 頂点A→頂点Bへ辺をつなぐ
    connect[A].append(B)
    # 頂点Bへ「入ってくる辺の数」をプラス1
    count[B]+=1
 
# heapqをインポート
import heapq

# キューを用意
que=[]
 
# i=1~N
for i in range(1,N+1):
    # 「入ってくる辺の数」が0の頂点があれば
    if count[i]==0:
        # キューへ追加
        que.append(i)

# キューをheap化
heapq.heapify(que)

# 記録する数列
P=[]

# キューが空になるまで
while 0<len(que):
    # 今いる頂点
    # キューから一番小さい番号のものを取り出す
    now=heapq.heappop(que)
    # Pへ記録
    P.append(now)
 
    # 今いる頂点から行ける頂点=to
    for to in connect[now]:
        # 辺を消す=toの「入ってくる辺の数」をマイナス1
        count[to]-=1
        # もし「入ってくる辺の数」が0になったら
        if count[to]==0:
            # キューへ追加
            heapq.heappush(que,to)

# 答えの長さがNならば
if len(P)==N:
    # 答えを出力
    print(*P)
# そうでなければ(N未満ならば)
else:
    # -1を出力
    print(-1)

ABC224 A

提出

# 入力を受け取る
S=input()

# 末尾はS[-1]で確認できる
# 末尾の文字が「r」ならば
if S[-1]=="r":
    # 「er」を出力
    print("er")

# そうでなければ(末尾の文字が「t」ならば)
else:
    # 「ist」を出力
    print("ist")

ABC224 B

提出

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

# Aを受け取るリスト
A=[]

# H回受け取り
for i in range(H):
    # i行目の受け取り
    h=list(map(int, input().split()))
    # リストへ格納
    A.append(h)

# i1=0~(H-1)
for i1 in range(H):
    # i2=(i1+1)~(H-1)
    for i2 in range(i1+1,H):
        # j1=0~(W-1)
        for j1 in range(W):
            # j2=(j1+1)~(W-1)
            for j2 in range(j1+1,W):
                # 条件を満たさないならば
                if A[i1][j1]+A[i2][j2]>A[i2][j1]+A[i1][j2]:
                    # 「No」を出力
                    print("No")
                    # 終了
                    exit()

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

ABC224 C

提出

# pypyで提出

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

# 座標の受け取りリスト
points=[]

# N回
for i in range(N):
    # X,Yを受け取り
    X,Y=map(int, input().split())
    # 座標をリストへ追加
    points.append([X,Y])

# 点の組を数える変数
count=0

# i=0~(N-1)
for i in range(N):
    # j=(i+1)~(N-1)
    for j in range(i+1,N):
        # k=(j+1)~(N-1)
        for k in range(j+1,N):
            # 座標を変数へ
            x1,y1=points[i][0],points[i][1]
            x2,y2=points[j][0],points[j][1]
            x3,y3=points[k][0],points[k][1]
 
            # 同一直線上になければ
            if (y3-y1)*(x2-x1)!=(y2-y1)*(x3-x1):
                # カウントする
                count+=1

# 答えの出力
print(count)

ABC225 A

提出

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

# 0文字目、1文字目、2文字目が同じなら
if S[0]==S[1]==S[2]:
    # 「1」を出力
    print(1)

# 「0文字目と1文字目」または「1文字目と2文字目」または「2文字目と0文字目」が同じなら
elif S[0]==S[1] or S[1]==S[2] or S[2]==S[0]:
    # 「3」を出力
    print(3)

# そうでなければ(すべて違う文字ならば)
else:
    # 6を出力
    print(6)

ABC225 B

提出

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

# 辺の本数を数える
count=[0]*(N+1)

# (N-1)回
for i in range(N-1):
    # 入力の受け取り
    a,b=map(int, input().split())
    # a,bから出ている辺の数を数える
    count[a]+=1
    count[b]+=1

# i=1~N
for i in range(1,N+1):
    # 頂点iから出ている辺が(N-1)本なら
    if count[i]==N-1:
        # 「Yes」を出力
        print("Yes")
        # プログラムの終了
        exit()

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

ABC225 C

提出

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

# Bを記録するリスト
B=[]

# N回受け取り
for i in range(N):
    # i行目をリストとして受け取り
    B_tmp=list(map(int, input().split()))
    # Bへ格納
    B.append(B_tmp)

# (1)Bの0行目がAのどこかの一行と一致する(2行にまたがらない)
# Bの左上はAの何行目か
A_gyou=(B[0][0]-1)//7
# Bの左上がある行の左端の値
left=A_gyou*7+1
# Bの左上がある行の右端の値
right=left+6

# retu=0~(M-1)
for retu in range(M):
    # Aの左端~右端の間になければ
    if B[0][retu]<left or right<B[0][retu]:
        # 「No」を出力
        print("No")
        # 終了
        exit()

# (2)Bの0行目は「左列+1」になっている
# retu=1~(M-1)
for retu in range(1,M):
    # 0行目i列目 が 0行目(i-1)列目+1 でなければ
    if B[0][retu]!=B[0][retu-1]+1:
        # 「No」を出力
        print("No")
        # 終了
        exit()

# (3)Bの1行目以降は「上の行+7」になっている
# gyou=1~(N-1)
for gyou in range(1,N):
    # retu=0~(M-1)
    for retu in range(M):
        # 「上の段+7」になっていなければ
        if B[gyou][retu]!=B[gyou-1][retu]+7:
            # 「No」を出力
            print("No")
            # 終了
            exit()

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

ABC225 D

提出

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

# 前の車両番号を記録 なにもなければ0
front=[0]*(N+1)
# 後ろの車両番号を記録 なにもなければ0
back=[0]*(N+1)

# Q回受け取り
for i in range(Q):
    # クエリをリストとして受け取り
    query=list(map(int, input().split()))

    # クエリ1
    if query[0]==1:
        x=query[1]
        y=query[2]

        # yの前にx
        front[y]=x
        # xの後ろにy
        back[x]=y

    # クエリ2
    elif query[0]==2:
        x=query[1]
        y=query[2]

        # 連結を外す=0にする
        front[y]=0
        back[x]=0

    # クエリ3
    else:
        x=query[1]

        # 先頭の車両番号 最初はx
        head=x

        # 先頭の車両へたどり着くまで戻る
        # ⇔前の車両番号が「0」になるまで
        while front[head]!=0:
            # headを前の車両番号で更新
            head=front[head]

        # 答えの格納用
        ans=[]

        # 今の車両
        now=head
 
        # 車両番号が0になるまで
        while now!=0:
            # 答えに今の車両を格納
            ans.append(now)
            # 後ろへ
            now=back[now]

        # 長さ、ansを出力
        print(len(ans),*ans)