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

ABC226～235　https://qiita.com/sano192/items/6d7cd42eed478a6a7a29
ABC236～250　https://qiita.com/sano192/items/b0e21a98c0b430451d7c

この記事は 『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

ARC129 A

# 入力の受け取り
N,L,R=map(int,input().split())
 
# 2^Lk≤L<2^(Lk+1)となるようなLkを探す
Lk=0
while 2**(Lk+1)<=L:
    Lk+=1
 
# 2^Rk≤L<2^(Rk+1)となるようなRkを探す
Rk=Lk
while 2**(Rk+1)<=R:
    Rk+=1
 
# 答えの個数
ans=0
 
# i=Lk~Rk
for i in range(Lk,Rk+1):
    # 2^iが条件を満たすなら
    if (2**i)^N<N:
        # (2^(i+1)-2^i)個を答えにカウント
        ans+=2**(i+1)-2**i
 
# x=2**Lkのとき条件を満たすなら
if (2**Lk)^N<N:
    # 余分をマイナス
    ans-=L-2**Lk
   
# x=2**Rkのとき条件を満たすなら
if (2**Rk)^N<N:
    # 余分をマイナス
    ans-=(2**(Rk+1)-1)-R
 
# 答えの出力
print(ans)

ARC129 B

# 入力の受け取り
N=int(input())
 
# 初期値の割り振り
Lmax=0
Rmin=10**10
 
# 切り上げ計算のためインポート
from math import ceil
 
# N回
for k in range(N):
    # 入力の受け取り
    L,R=map(int,input().split())
    # Lの最大(最も右にあるL)
    Lmax=max(Lmax,L)
    # Rの最小(最も左にあるR)
    Rmin=min(Rmin,R)
   
    # ・Lmax≤Rminであれば(全ての区間にかぶっている場所がある場合)
    if Lmax<=Rmin:
        # dist=0
        print(0)
    # ・そうでなければ(区間にかぶりがない場合)
    else:
        # dist=((Lmax-Rmin)/2)の切り上げ)
        print(ceil((Lmax-Rmin)/2))

ARC130 A

# 入力の受け取り
N=int(input())
S=input()
 
# 何文字連続しているか記録するリスト
Slist=[]
# 今連続している文字
Now=S[0]
# 連続している文字数
Count=1
 
# i=1~(N-1)
for i in range(1,N):
    # Sのi文字目＝Nowなら
    if S[i]==Now:
        # カウントを増やす
        Count+=1
    # そうでなければ
    else:
        # リストへ記録
        Slist.append(Count)
        # 次の文字へ
        Now=S[i]
        Count=1
# 最後のカウントを追加
Slist.append(Count)
 
# 答え
ans=0
 
# x：Slistの要素
for x in Slist:
    # 答えに加算
    ans+=x*(x-1)//2
 
# 答えの出力
print(ans)

ARC130 B

# 入力の受け取り
H,W,C,Q=map(int,input().split())
 
# クエリの受け取り
querys=[]
for i in range(Q):
    t,n,c=map(int,input().split())
    querys.append([t,n,c])
 
 
# 塗られた行、列の管理
from collections import defaultdict
GyouColored=defaultdict(int)
RetuColored=defaultdict(int)
 
# 答え
Colors=[0]*(C+1)
 
# すでに塗られた行、列の数
Gyou=0
Retu=0
 
# クエリを逆順にする
querys=querys[::-1]
 
# 各クエリについて
for t,n,c in querys:
    # 行を塗る場合
    if t==1:
        # まだ塗られていない場合
        if GyouColored[n]==0:
            # (W-Retu)個のマスが色cになる
            Colors[c]+=W-Retu
            # 行nは塗られた
            GyouColored[n]=1
            # 塗られた行が増えた
            Gyou+=1
 
    # 列を塗る場合
    else:
        # まだ塗られていない場合
        if RetuColored[n]==0:
            # (H-Gyou)個のマスが色cになる
            Colors[c]+=H-Gyou
            # 列nは塗られた
            RetuColored[n]=1        
            # 塗られた列が増えた
            Retu+=1
 
# 答えの出力
print(*Colors[1:])

ARC131 A

# 入力の受け取り
A=int(input())
B=int(input())
 
# Bを2で割る
B=B/2
# 10倍する(小数点を取る)
B*=10
# 整数へ変換
B=int(B)
# 間に0を入れて出力
print(str(B)+"0"+str(A))

ARC131 B

# 入力の受け取り
H,W=map(int,input().split())
 
# マス目
Grid=[]
 
# H回
for i in range(H):
    # 入力の受け取り
    ci=input()
    # リストへ展開
    ci=list(ci)
    # マス目へ記録
    Grid.append(ci)
 
# 前後左右で使われていない色を返す
def color(R,C):
    # すでに使われた色の種類
    used=set()
 
    # 0≤R-1ならば(最上行でなければ)→使われた色を記録
    if 0<=R-1:used.add(Grid[R-1][C])
    # R+1<Hならば(最下行でなければ)→使われた色を記録
    if R+1<H:used.add(Grid[R+1][C])
    # 0≤C-1ならば(最左行でなければ)→使われた色を記録
    if 0<=C-1:used.add(Grid[R][C-1])
    # C+1<Hならば(最右行でなければ)→使われた色を記録
    if C+1<W:used.add(Grid[R][C+1])
   
    # 使われていない色のうち最も小さい番号を返す
    if "1" not in used:return "1"
    elif "2" not in used:return "2"
    elif "3" not in used:return "3"
    elif "4" not in used:return "4"
    elif "5" not in used:return "5"
 
# R=0~(H-1)
for R in range(H):
    # C=0~(W-1)
    for C in range(W):
        # マス目がまだ塗られていないなら
        if Grid[R][C]==".":
            # 色を塗る
            Grid[R][C]=color(R,C)
 
# R=0~(H-1)
for R in range(H):
    # R行目を結合して出力
    print("".join(Grid[R]))

ARC131 C

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# 「A全てのxorを取ったもの」
Axor=0
# A全てのxorを計算
for x in A:
    Axor^=x
 
# Nが奇数
if N%2==1:
    # 先手の勝ち
    print("Win")
# Nが偶数
else:
    # 1手で勝てるなら
    # ⇔「A全てのxorを取ったもの」と同じ値がAにあるなら
    if Axor in A:
        # 先手の勝ち
        print("Win")
    # 1手で勝てないなら
    else:
        # 後手の勝ち
        print("Lose")

ARC132 A

# 入力の受け取り
n=int(input())
 
# 1インデックスにするため先頭に[0]を埋めている
R=[0]+list(map(int,input().split()))
C=[0]+list(map(int,input().split()))
 
# 入力の受け取り
q=int(input())
 
# 答え
ans=""
 
# q回
for i in range(q):
    # 入力の受け取り
    r,c=map(int,input().split())
 
    # R[r]+C[c]≤nならば
    if R[r]+C[c]<=n:
        # 白色
        ans+="."
    # そうでなければ
    else:
        # 黒色
        ans+="#"
       
# 答えの出力
print(ans)

ARC132 B

# 入力の受け取り
n=int(input())
p=list(map(int,input().split()))
 
# 「1」のインデックス番号
indx1=p.index(1)
# 「n」のインデックス番号
indxn=p.index(n)
 
# (1)すでに昇順(「1」が0番目、「n」が(n-1)番目)
if indx1==0 and indxn==n-1:
    # 操作不要
    print(0)
    exit()
# (2)すでに降順(「1」が(n-1)番目、「n」が0番目)
elif indx1==n-1 and indxn==0:
    # 「全体をひっくり返す」
    print(1)
    exit()
 
# 答え
ans=10**10
 
# 操作回数
Count=0
# (3)「n」「1」の順で隣り合っている
if indx1-1==indxn:
    # 「1」を先頭に持ってくるまでの操作回数
    Count+=indxn+1
    # 答えの更新
    ans=min(Count,ans)
# (4)「1」「n」の順で隣り合っている
else:
    # 「n」を先頭に持ってくるまでの操作回数
    Count+=indx1+1
    # 「全体をひっくり返す」
    Count+=1
    # 答えの更新
    ans=min(Count,ans)
 
# 「全体をひっくり返す」
p=p[::-1]
Count=1
 
# 同じ計算をする
indx1=p.index(1)
indxn=p.index(n)
 
if indx1-1==indxn:
    Count+=indxn+1
    ans=min(Count,ans)
else:
    Count+=indx1+1
    Count+=1
    ans=min(Count,ans)
 
# 答えの出力
print(ans)

ARC133 A

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# xを決める
x=A[0]
 
# i=1~(N-1)
for i in range(1,N):
    # ・x≤A[i]ならば
    if x<=A[i]:
        # x=A[i]と更新
        x=A[i]
    # ・A[i]<xならば
    else:
        # 消す数をxで確定
        break
 
# 答え
ans=[]
 
# i=0~(N-1)
for i in range(N):
    # xでなければ
    if A[i]!=x:
        # 追加
        ans.append(A[i])
 
# 答えの出力
print(*ans)

ARC134 A

# 入力の受け取り
N,L,W=map(int,input().split())
a=list(map(int,input().split()))
 
# x/aの切り上げを計算する関数
def Ceil(x,a):
    # ・xがaで割り切れる
    if x%a==0:
        # x//aを返す
        return x//a
    # ・xがaで割り切れない
    else:
        # (x//a+1)を返す
        return x//a+1
 
# 答え
# 0~a[0]に必要な枚数
ans=Ceil(a[0],W)
 
# i=0~(N-2)
for i in range(N-1):
    # (シートの右端)<(次のシートの左端)ならば
    if a[i]+W<a[i+1]:
        # a[i]~a[i+1]に必要な枚数
        ans+=Ceil((a[i+1]-(a[i]+W)),W)
 
# a[N-1]~Lに必要な枚数
ans+=Ceil((L-(a[N-1]+W)),W)
 
# 答えの出力
print(ans)

ARC134 B

# 入力の受け取り
N=int(input())
S=input()
 
# 1文字ずつのリストへ
S=list(S)
 
# defaultdictのインポート
from collections import defaultdict
# 文字の出現個数を記録する連想配列
Count=defaultdict(int)
 
# (1)Sについてa,b,c,...が何文字あるか記録する
# x：Sの各文字について順に処理
for x in S:
    # 文字の出現個数をカウント
    Count[x]+=1
 
# S[左~右]のうち、辞書順で最も小さい文字Xを返す
def Target():
    # code=97~122
    for code in range(97,123):
        # 文字コード→文字へ変換
        Alphabet=chr(code)
        # 1個以上あるなら
        if 1<=Count[Alphabet]:
            # その文字がXとなる
            return Alphabet
 
# (2)左=0,右=(N-1)とする
l=0
r=N-1
 
# (3)S[左~右]のうち、辞書順で最も小さい文字をXとする
X=Target()
 
# (4)左<右なら(3)へ戻る
while l<r:
    # (4)Xの出てくる箇所で処理を分岐
    # ・S[左]=Xの場合
    if S[l]==X:
        # S[左]の個数を1つ減らす
        Count[S[l]]-=1
        # 左をプラス1する
        l+=1
        # S[左~右]のうち、辞書順で最も小さい文字Xを更新する
        X=Target()
 
    # ・S[右]=Xの場合
    elif S[r]==Target():
        # S[左],S[右]の個数を1つ減らす
        Count[S[l]]-=1
        Count[S[r]]-=1
        # S[左],S[右]を入れ替える
        S[l],S[r]=S[r],S[l]
        # 左をプラス1,右をマイナス1する
        l+=1
        r-=1
        # S[左~右]のうち、辞書順で最も小さい文字Xを更新する
        X=Target()
   
    # ・どちらでもない場合
    else:
        # S[右]の個数を1つ減らす
        Count[S[r]]-=1
        # 右をマイナス1する
        r-=1
 
# Sを結合して出力
print("".join(S))

ARC135 A

# 入力の受け取り
X=int(input())
 
# 余りの定義
mod=998244353
 
# defaultdictのインポート
from collections import defaultdict
 
# 個数を数える連想配列
Count=defaultdict(int)
 
# Xが1個
Count[X]=1
 
# 黒板に書いている数の種類
NumSet=set()
# 最初はXのみ
NumSet.add(X)
 
# 黒板に書いている数の種類のうち最大のものが4以下になったら終了
while 4<max(NumSet):
    # 黒板に書いている数の種類
    tmpNumSet=set()
 
    # p：黒板に書いている数それぞれについて
    for p in NumSet:
        # pが4より大きい場合
        if 4<p:
            # 2で割り切れる場合
            if p%2==0:
                # (p//2)が2個になる
                Count[p//2]+=2*Count[p]
                # 種類を記録
                tmpNumSet.add(p//2)
 
            # 2で割り切れない場合
            elif p%2==1:
                # (p//2)が1個
                Count[p//2]+=Count[p]
                # (p//2+1)が1個
                Count[p//2+1]+=Count[p]
                # 種類を記録
                tmpNumSet.add(p//2)
                tmpNumSet.add(p//2+1)
 
    # 種類の更新
    NumSet=tmpNumSet
 
# 2^(2の個数)
ans=pow(2,Count[2],mod)
# 3^(3の個数)
ans*=pow(3,Count[3],mod)
# 余りを取る
ans%=mod
# 4^(4の個数)
ans*=pow(4,Count[4],mod)
# 余りを取る
ans%=mod
 
# 答えの出力
print(ans)

ARC136 A

# 入力の受け取り
N=int(input())
S=input()
 
# 1文字ずつリストへ展開
S=list(S)
 
# i=0~(N-2)
for i in range(N-1):
    # 「BA」ならば
    if S[i]=="B" and S[i+1]=="A":
        # 「AB」へ変換
        S[i]="A"
        S[i+1]="B"
    # 「BB」ならば
    elif S[i]=="B" and S[i+1]=="B":
        # 「AX」へ変換
        # ※「A」に変換すると文字数が減るので実装が大変になる
        S[i]="A"
        S[i+1]="X"
   
# 答え
ans=""
 
# p：Sの各要素について
for p in S:
    # 「X」でなければ
    if p!="X":
        # ansの末尾へ追加
        ans+=p
 
# 答えの出力
print(ans)

ARC137 A

# pypyで提出

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

# gcdの計算用
from math import gcd

# 答え
ans=0

# l＝L,L+1,L+2,...
for l in range(L,L+1000):
    # r=R,R-1,R-2,...
    for r in range(R,R-1000,-1):
        # l<rの場合のみ
        if l<r:
            # gcd=1なら
            if gcd(l,r)==1:
                # (r-l)を計算　これまでの答えより大きければ更新
                ans=max(r-l,ans)
        # r≤lなら
        else:
            # 次のlへ
            break

# 答えの出力
print(ans)

ARC137 B

# 入力の受け取り
N=int(input())
# 1インデックスにするため0番目を埋める
A=[0]+list(map(int,input().split()))
 
# C[x]：「1~xまでの1の数」
C=[0]*(N+1)
 
# i=1~N
for i in range(1,N+1):
    # A[i]=1ならば
    if A[i]==1:
        # C[i-1]に1プラス
        C[i]=C[i-1]+1
    # A[i]=0ならば
    else:
        # C[i-1]をそのままC[i]に
        C[i]=C[i-1]
 
# (2*C[l-1]-l)の最小値
minl=10**10
# (2*C[l-1]-l)の最大値
maxl=-10**10
# スコアの最小値
minScore=10**10
# スコアの最大値
maxScore=-10**10
# r=1~N
for r in range(1,N+1):
    # (2*C[l-1]-l)を計算して最小、最大を更新
    l=r
    minl=min(minl,2*C[l-1]-l)
    maxl=max(maxl,2*C[l-1]-l)
   
    # スコアの最小、最大を更新
    minScore=min(minScore,C[N]+(1+r-2*C[r])+minl)
    maxScore=max(maxScore,C[N]+(1+r-2*C[r])+maxl)
 
# 部分列を選択しない場合(flipをしない場合)のスコア
minScore=min(C[N],minScore)
maxScore=max(C[N],maxScore)
 
# 答え：(スコアの最大値)-(スコアの最小値)+1
print(maxScore-minScore+1)

# 入力の受け取り
N=int(input())
# 1インデックスにするため0番目を埋める
A=[0]+list(map(int,input().split()))
 
# 1の個数
Count1=A.count(1)
 
# 変換
# A[i]=0ならば1
# A[i]=1ならば-1
Aconv=[0]*(N+1)
for i in range(1,N+1):
    if A[i]==1:Aconv[i]=-1
    else:Aconv[i]=1
 
# Aの累積和を計算
S=[0]*(N+1)
for i in range(1,N+1):
    S[i]=S[i-1]+Aconv[i]
 
# スコアの最小、最大値　最初はflipしなかったときのスコア
ScoreMin=Count1
ScoreMax=Count1
 
# S[l-1]の最小、最大
Smin=10**10
Smax=-10**10
# r=1~N
for r in range(1,N+1):
    # 更新
    Smin=min(S[r-1],Smin)
    Smax=max(S[r-1],Smax)
 
    # スコアの最小、最大を計算して更新
    ScoreMin=min(Count1+S[r]-Smax,ScoreMin)
    ScoreMax=max(Count1+S[r]-Smin,ScoreMax)
 
# 答えの出力
print(ScoreMax-ScoreMin+1)

ARC138 A

# 入力の受け取り
N,K=map(int,input().split())
A=list(map(int,input().split()))
 
# Aの値、インデックス番号を記録するリスト
p=[]
# i=0~(N-1)
for i in range(N):
    # [Aのインデックス番号,-インデックス番号]を記録
    p.append([A[i],-i])
 
# 小さい順にソート
p.sort()
 
# 答え
ans=10**10
 
# (K-1)以下インデックス番号のうち、最も大きいもの
indxMax=-1
 
# pの各要素について
for Ai,indx in p:
    # インデックス番号のマイナスを取る
    indx*=-1
 
    # インデックス番号がK以上　かつ　(K-1)以下番目にAiより小さい値がある　場合
    if K<=indx and indxMax!=-1:
        # 入れ替えの操作回数=(indx-indxMax)
        # 大きければ答えを更新
        ans=min((indx-indxMax),ans)
    # インデックス番号がK未満
    elif indx<K:
        # 番号が大きければ更新
        indxMax=max(indx,indxMax)
 
# 答えが更新されていなければ
if ans==10**10:
    # 目標達成不可
    print(-1)
# 更新されていれば
else:
    # 答えを出力
    print(ans)

ARC138 B

# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
 
# flip回数
flipCount=0
 
# dequeAのインポート
from collections import deque
# 初期値はA
A=deque(A)
 
# Aが空になるまで
while 0<len(A):
 
    # ・flip回数が偶数の場合
    if flipCount%2==0:
        # ・Aの末尾が0
        if A[-1]==0:
            # 末尾の0を取り除く
            A.pop()
        # Aの先頭が0
        elif A[0]==0:
            # 先頭の1を取り除く
            A.popleft()
            # flip回数をプラス1
            flipCount+=1
        # 先頭、末尾がともに1
        else:
            # 不可
            # 「No」を出力して終了
            print("No")
            exit()
 
    # ・flip回数が奇数の場合
    else:
        # ・Aの末尾が1
        if A[-1]==1:
            # 末尾の0を取り除く
            A.pop()
        # Aの先頭が1
        elif A[0]==1:
            # 先頭の1を取り除く
            A.popleft()
            # flip回数をプラス1
            flipCount+=1
        # 先頭、末尾がともに0
        else:
            # 不可
            # 「No」を出力して終了
            print("No")
            exit()
 
# 「Yes」を出力
print("Yes")

ARC139 A

# 入力の受け取り
N=int(input())
# 1インデックスにするため0番目を埋める
T=[0]+list(map(int,input().split()))
 
# Aを作る
A=[0]*(N+1)
 
# i=1~Nまで
for i in range(1,N+1):
    # kの計算
    k=(A[i-1]//(2**T[i])-1)//2+1
    # Aiの計算
    A[i]=2**T[i]+2**(T[i]+1)*k
 
# 答えの出力
print(A[N])

UnionFind

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

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

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

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

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

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

FenwickTree

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

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

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

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

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