ABC226～235 https://qiita.com/sano192/items/6d7cd42eed478a6a7a29
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
ABC236 A
# 入力の受け取り
S=input()
a,b=map(int,input().split())
# a,b文字目を入れ替え
# ⇔「Sの1~(a-1)文字目」+「Sのb文字目」+「Sの(a+1)~(b-1)文字目」+「Sのb文字目」+「Sの(b+1)~末尾文字目」
ans=S[:a-1]+S[b-1]+S[a:b-1]+S[a-1]+S[b:]
# 答えの出力
print(ans)
ABC236 B
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# 枚数を数えるリスト
Count=[0]*(N+1)
# i=0~(4N-2)
for i in range(4*N-1):
# A[i]をプラス一枚カウント
Count[A[i]]+=1
# i=1~N
for i in range(1,N+1):
# 枚数が3ならば
if Count[i]==3:
# iが抜かれたカード
print(i)
# 途中終了
exit()
ABC236 C
# 入力の受け取り
N,M=map(int,input().split())
S=list(map(str,input().split()))
T=list(map(str,input().split()))
# defaultdictをインポート
from collections import defaultdict
# 急行が止まる駅
# 「1」なら止まる
# 「0」(デフォルト値)なら止まらない
Stations=defaultdict(int)
# i=0~(M-1)
for i in range(M):
# 「1」を記録
Stations[T[i]]=1
# i=0~(N-1)
for i in range(N):
# S[i]が止まる駅
if Stations[S[i]]==1:
# 「Yes」を出力
print("Yes")
# 止まらない駅
else:
# 「No」を出力
print("No")
# 入力の受け取り
N,M=map(int,input().split())
S=list(map(str,input().split()))
T=set(map(str,input().split()))
# x：Sの要素それぞれについて
for x in S:
# Tに含まれるなら「Yes」、含まれないなら「No」
if x in T:print("Yes")
else:print("No")
ABC236 D
# pypyで提出
# 再起回数上限を10^6へ変更
import sys
sys.setrecursionlimit(10**6)
# 入力の受け取り
N=int(input())
# 「相性」の表
A=[[0]*(2*N+1) for i in range(2*N+1)]
# i=1~(2N-1)
for i in range(1,2*N):
# 入力を受け取る
Atmp=list(map(int,input().split()))
# 表に記載
for j in range(len(Atmp)):
A[i][j+(i+1)]=Atmp[j]
A[j+(i+1)][i]=Atmp[j]
# 答え
ans=0
# 引数：Pairs(ペアの一覧)
def DFS(Pairs):
# ansを更新できるように
global ans
# 全員ペアができていれば
# ⇔Pairsの長さが2Nならば
if len(Pairs)==2*N:
# 「楽しさ」の計算
Score=0
# i=0~(2N-1)まで 2ずつ増加
for i in range(0,2*N,2):
# ペアになる人
x=Pairs[i]
y=Pairs[i+1]
# 「相性」から「楽しさ」を計算
Score^=A[x][y]
# 「楽しさ」が大きかったら答えを更新
ans=max(ans,Score)
# 次に追加する人が偶数番目
# ⇔Pairsの長さが偶数
elif len(Pairs)%2==0:
# 選ばれていない中で一番小さい番号の人を選ぶ
i=1
while i in Pairs:
i+=1
# Pairsへ追加
Pairs.append(i)
# 次のDFSへ
DFS(Pairs)
# 前のDFSが終わったらPairsから消す
Pairs.pop()
# 次に追加する人が奇数番目
# ⇔Pairsの長さが奇数
else:
# 選ばれていない人を一人ずつ全て選ぶ
for i in range(1,2*N+1):
# まだ選ばれていないなら
if i not in Pairs:
# 追加
Pairs.append(i)
# 次のDFSへ
DFS(Pairs)
# 前のDFSが終わったらPairsから消す
Pairs.pop()
# ペアになる人を記録するリスト(最初は空)
# 最終的にPairsの(0番目と1番目),(2番目と3番目),...,((2N-2)番目と(2N-1))をペアとする
Pairs=[]
# DFSを開始
DFS(Pairs)
# 答えの出力
print(ans)
ABC237 A
#入力の受け取り
N=int(input())
# -2^31以上2^31未満ならば
if(-2)**31<=N<2**31:
# 「Yes」 を出力
print("Yes")
#そうでないならば
else:
# 「No を出力」
print("No")
ABC237 B
# 入力の受け取り
H,W=map(int,input().split())
#空のリストを作る
A=[]
# H回
for i in range (H):
# 一行ずつリストとして受け取り
# tmp=tmporary(一時的な)の意味
Atmp=list(map(int,input().split()))
# Aへ追加
A.append(Atmp)
# W*Hの二次元配列を作成
B=[[0]*H for i in range(W)]
# i=0~(W-1)
for i in range (W):
#j=0*(H-1)
for j in range (H):
#Bの値を更新
B[i][j]=A[j][i]
# i=0~(W-1)
for i in range (W):
# 一行ずつ出力
print(*B[i])
ABC237 C
# 入力の受け取り
S=input()
# 先頭にある「a」の数
aFront=0
# i=0~(Sの文字数-1)
for i in range(len(S)):
# i文字目が「a」なら
if S[i]=="a":
#カウント
aFront+=1
# そうでないなら
else:
# for を抜ける
break
# 末尾にある「a」の数
aBack=0
# i=(Sの文字数-1)~0 -1ずつ
for i in range(len(S)-1,-1,-1):
# i文字目が「a」なら
if S[i]=="a":
#カウント
aBack+=1
# そうでないなら
else:
# for を抜ける
break
# 「末尾の「a」の個数」<「先頭の「a」の個数」
if aBack<aFront:
# 「No」を出力
print("No")
# 終了
exit()
# (「末尾の「a」の個数」-「先頭の「a」の個数」)分先頭に「a」を追加
S="a"*(aBack-aFront)+S
# Sの文字数
N=len(S)
# i=0~(N-1)
for i in range(N):
# 回文か判定
# 1文字目と(N-i-1)文字目が違うなら
if S[i]!=S[N-i-1]:
# 「No」を出力
print("No")
# 終了
exit()
# ここまで来たら回文
# 「Yes」を出力
print("Yes")
ABC237 D
# 入力の受け取り
N=int(input())
S=input()
# deque のインポート
from collections import deque
# キューを用意
que=deque()
# Nを追加
que.append(N)
# i=(N-1)~0 -1ずつ
for i in range(N-1,-1,-1):
# Sのi文字目が「R｣
if S[i]=="R":
# 先頭(左端)へ「i」を追加
que.appendleft(i)
# そうでない場合(Sのi文字目が「L」)
else:
# 末端(右端)へ「i」を追加
que.append(i)
# 答えの出力
# ([]がいらない場合は先頭に「*」をつける)
print(*que)
ABC238 A
# 入力の受け取り
n=int(input())
# 2≤n≤4の場合
if 2<=n<=4:
# 「No」を出力
print("No")
# それ以外の場合
else:
# 「Yes」を出力
print("Yes")
ABC238 B
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# カットされた角度の格納
Angle=[]
# 現在の角度
Now=0
# i=0~(N-1)
for i in range(N):
# 現在の角度へA[i]をプラス
Now+=A[i]
# 角度を記録
Angle.append(Now)
# i=0~(N-1)
for i in range(N):
# 360で割った余りを取る
Angle[i]%=360
# 小さい順に並び替え
Angle.sort()
# 「360」を追加
Angle=[0]+Angle+[360]
# 答え
ans=0
# i=1~(N+1)
for i in range(1,N+2):
# 現在までの「答え」と(Angle[i]-Angle[i-1])の差を比較
# 大きい方を新しい答えとする
ans=max(ans,Angle[i]-Angle[i-1])
# 答えを出力
print(ans)
ABC238 C
# 余りを定義
mod=998244353
# 入力の受け取り
N=int(input())
# A~Bまでの和
# 引数：A,B → 返り値：A~Bまでの和
def S(A,B):
return (B-A+1)*(A+B)//2
# 答え
ans=0
# x~1~18
for x in range(1,19):
# 10^x≤Nならば
if 10**x<=N:
# 「1~9*10**(x-1)までの和」
ans+=S(1,9*10**(x-1))
# 余りを取る
ans%=mod
# 10^(x-1)≤N<10^xならば
else:
# 「1～(N-10^(x-1)+1)までの和」
ans+=S(1,N-10**(x-1)+1)
# 余りを取る
ans%=mod
# forを抜ける
break
# 答えの出力
print(ans)
ABC238 D
# 入力の受け取り
N=int(input())
# 各テストケース
for T in range(N):
# 入力の受け取り
a,s=map(int,input().split())
# 繰り上がりの初期化
up=0
# 答え
ans="Yes"
# N：桁数 s,aのうち桁数の大きい方
N=max(a.bit_length(),s.bit_length())
# i桁目
for i in range(N):
# 「aのi桁目」
ai=a>>i & 1
# 「sのi桁目」
si=s>>i & 1
# 条件から答えと繰り上がりを計算
if ai==0:
if up==1 and si==0:
up=1
else:
up=0
else:
if up+si==1:
ans="No"
break
up=1
# 最後の桁で繰り上がりがあれば
if i==N-1 and up==1:
ans="No"
print(ans)
ABC239 A
# 入力の受け取り
H=int(input())
# ルートの計算のためsqrtをインポート
import math
# 答えの出力
print(math.sqrt(H*(12800000+H)))
ABC239 B
# 入力の受け取り
X=int(input())
# Xを10で割った商を出力
print(X//10)
ABC239 C
# 入力の受け取り
x1,y1,x2,y2=map(int,input().split())
# (x1,y1)との距離が√5の格子点：(x3,y3)=(x1+2,y1+1)
x3=x1+2
y3=y1+1
# ((x2,y2)と(x3,y3)の距離)^2=5ならば
if (x3-x2)**2+(y3-y2)**2==5:
# 「Yes」を出力
print("Yes")
# 終了
exit()
x3=x1+2
y3=y1-1
if (x3-x2)**2+(y3-y2)**2==5:
print("Yes")
exit()
x3=x1-2
y3=y1+1
if (x3-x2)**2+(y3-y2)**2==5:
print("Yes")
exit()
x3=x1-2
y3=y1-1
if (x3-x2)**2+(y3-y2)**2==5:
print("Yes")
exit()
x3=x1+1
y3=y1+2
if (x3-x2)**2+(y3-y2)**2==5:
print("Yes")
exit()
x3=x1+1
y3=y1-2
if (x3-x2)**2+(y3-y2)**2==5:
print("Yes")
exit()
x3=x1-1
y3=y1+2
if (x3-x2)**2+(y3-y2)**2==5:
print("Yes")
exit()
x3=x1-1
y3=y1-2
if (x3-x2)**2+(y3-y2)**2==5:
print("Yes")
exit()
# 「No」を出力
print("No")
x1,y1,x2,y2=map(int,input().split())
# 距離が√5になっているか判定
def Judge(x3,y3):
if (x2-x3)**2+(y2-y3)**2==5:
print("Yes")
exit()
# i：-1,1
for i in [-1,1]:
# k：-2,2
for k in [-2,2]:
Judge(x1+i,y1+k)
Judge(x1+k,y1+i)
print("No")
ABC239 D
# 入力の受け取り
A,B,C,D=map(int,input().split())
# 1~200までの素数
P=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]
# 高橋の選ぶ数：taka=A~B
for TakaNum in range(A,B+1):
# 高橋が勝っている間はTrue
TakaWin=True
# 青木くんの選ぶ数：ao=C~D
for AokiNum in range(C,D+1):
# 和が素数なら(素数リストの中にあるなら)
if TakaNum+AokiNum in P:
# 高橋君の負け
TakaWin=False
# 次の数へ
break
# 青木くんの選んだ数全てについて高橋くんが勝ちなら
if TakaWin==True:
# 「takahashi」を出力
print("Takahashi")
# 終了
exit()
# 「Aoki」を出力
print("Aoki")
A,B,C,D=map(int,input().split())
# エラトステネスの篩
def Eratosthenes(N):
# 素数であるかの判定リスト
IsPrime=[True]*(N+1)
# i=2,3,4,...
i=2
# i≤√Nまで⇔i^2≤Nまで
while i**2<=N:
# iが素数でなければ
if IsPrime[i]==False:
# 次のiへ
i+=1
continue
# k=2,3,4,...
k=2
while i*k<=N:
# iの倍数は素数でない
IsPrime[i*k]=False
# 次のkへ
k+=1
# 次のkへ
i+=1
# 素数リスト
PList=[]
# i=2~N
for i in range(2,N+1):
# iが素数ならば
if IsPrime[i]==True:
# リストへ入れる
PList.append(i)
# リストを返す
return PList
P=Eratosthenes(200)
for TakaNum in range(A,B+1):
TakaWin=True
for AokiNum in range(C,D+1):
if TakaNum+AokiNum in P:
TakaWin=False
break
if TakaWin:
print("Takahashi")
exit()
print("Aoki")
ABC239 E
# 入力の受け取り
N,Q=map(int,input().split())
# 1インデックスにするため先頭に「0」を追加
X=[0]+list(map(int,input().split()))
# 辺の情報格納用
edge=[[] for i in range(N+1)]
# (N-1)回
for i in range(N-1):
# 入力の受け取り
A,B=map(int,input().split())
# 辺の情報を格納
edge[A].append(B)
edge[B].append(A)
# 部分木の頂点に書いている数を大きい順に格納したリスト
# 1インデックスにするため0番目は埋めておく
P=[[0]]
# (1)「部分木に含まれる数を大きい順にソートした二次元配列」をPとし、自分自身に書いている数をPへ記録する
for i in range(1,N+1):
# Pへ自分自身に書いている数を追加
P.append([X[i]])
# (2)キューを用意する
que=list()
# (3)スタート地点=頂点①をキューへ入れる
# (今いる頂点,今いる頂点の親,訪問回数)
que.append((1,0,1))
# (4)キューが空になるまで(3)を繰り返す
while 0<len(que):
# (4)キューの「右端から」要素を取り出す
# (今いる頂点,今いる頂点の親,訪問回数)
now,parent,count=que.pop()
# ・1回目の訪問ならば
if count==1:
# (4-1)「今いる頂点」を2回目の訪問としてキューへ記録
que.append((now,parent,2))
# (4-2)「今いる頂点から行ける(親でない)頂点」をキューへ1回目の訪問として記録
# to：今いる頂点から行ける頂点
for to in edge[now]:
# 親でなければ
if to!=parent:
# キューへ記録
que.append((to,now,1))
# ・2回目の訪問ならば
else:
# to：今いる頂点から行ける頂点
for to in edge[now]:
# (4-3)「今いる頂点」のPへ子の頂点のPを追加
# 親ならば
if to==parent:
# 次の頂点へ
continue
P[now]+=P[to]
# (4-4)大きい順にソート
P[now].sort(reverse=True)
# (4-5)20番目以降の要素を捨てる
P[now]=P[now][:20]
# Q回
for i in range(Q):
# 入力の受け取り
V,K=map(int,input().split())
# Kをマイナス1(P[v]は先頭が0番目、次が1番目、...のため)
K-=1
# 答えを出力
print(P[V][K])
ABC240 A
# 入力の受け取り
a,b=map(int,input().split())
# a=1ならば
if a==1:
# b=2または10ならば
if b==2 or b==10:
# 「Yes」を出力
print("Yes")
# そうでないなら
else:
# 「No」を出力
print("No")
# それ以外(aが1でない)
else:
# b=(a+1)ならば
if b==a+1:
# 「Yes」を出力
print("Yes")
# そうでないなら
else:
# 「No」を出力
print("No")
ABC240 B
# 入力の受け取り
N=int(input())
a=list(map(int,input().split()))
# リスト→セットへ変換
aSet=set(a)
# 長さを出力
print(len(aSet))
ABC240 C
# 入力の受け取り
N,X=map(int,input().split())
# i回目のジャンプで到達できる座標
P=set()
# 最初は座標0にいる
P.add(0)
# N回
for i in range(1,N+1):
# 入力の受け取り
a,b=map(int,input().split())
# i回目のジャンプで到達できる座標セット
NewP=set()
# Now=(i-1)回目のジャンプで到達できる座標
for Now in P:
# +aした座標がX以下なら
if Now+a<=X:
# 新しい到達できる座標セットに記録
NewP.add(Now+a)
# +bした座標がX以下なら
if Now+b<=X:
# 新しい到達できる座標セットに記録
NewP.add(Now+b)
# 到達できる座標セットを更新
P=NewP
# XがPにあれば
if X in P:
# 「Yes」を出力
print("Yes")
# そうでなければ(XがPになければ)
else:
# 「No」出力
print("No")
ABC240 D
# 入力の受け取り
N=int(input())
a=list(map(int,input().split()))
# 筒
que=[]
# 同じ数字のボールがいくつ下に続いているか
Count=[]
# 今筒の中にあるボールの数
ans=0
# i=0~(N-1)
for i in range(N):
# 筒にボールを落とす
que.append(a[i])
# 筒の中のボールが1個増える
ans+=1
# 筒に2つ以上ボールがある かつ 1番上のボールと2番目のボールの数字が同じ
if 2<=len(que) and que[-1]==que[-2]:
# 同じ数字のボールが続いている個数を+1
Count.append(Count[-1]+1)
# (1番上のボールの数字)個続いたら
if Count[-1]==que[-1]:
# (1番上のボールの数字)個消える(=取り出す)
# ⇔(1番上のボールの数字)回取り出し
for j in range(que[-1]):
# 筒から取り出す
que.pop()
# countも消す
Count.pop()
# ボールが1個減った
ans-=1
# そうでないなら
else:
# 2番目と1番目のボールは別の数字だから「1」を記録
Count.append(1)
# 答えを出力
print(ans)
ABC240 E
# 入力の受け取り
N=int(input())
# 辺の情報
edge=[[] for i in range(N+1)]
for i in range(N-1):
# 入力の受け取り
u,v=map(int,input().split())
edge[u].append(v)
edge[v].append(u)
# ①→②,③,④がつながっているなら
# edge[1]=[2,3,4]
# 区間
LR=[[10**9,-1] for i in range(N+1)]
# (1)キューを用意する
# 「今いる頂点、今いる頂点の親、訪問回数」を記録
# (2)スタート地点=頂点①をキューへ入れる
# (①の親はいないから0にしておく。訪問回数は1回目)
que=[(1,0,1)]
# 「葉」に割当する区間の左右番号
LeafCount=1
# (4)キューが空になるまで(3)を繰り返し
while 0<len(que):
# (3)キューの「右端から」要素を取り出す
# 今いる頂点、今いる頂点の親、訪問回数
Now,Parent,Visit=que.pop()
# ・1回目の訪問ならば
if Visit==1:
# (3-1)「今いる頂点」を2回目の訪問としてキューへ記録
que.append((Now,Parent,2))
# To：「今いる頂点」から行ける頂点
for To in edge[Now]:
# 親でなければ
if To!=Parent:
# (3-2)「今いる頂点から行ける頂点」のうち、「親」でないものをキューへ1回目の訪問
que.append((To,Now,1))
# ・2回目の訪問ならば
else:
# ・「葉」であれば(頂点①でない かつ 出ている辺の本数が1本)
if Now!=1 and len(edge[Now])==1:
# (3-3)区間の割当([1,1],[2,2],...)
LR[Now]=[LeafCount,LeafCount]
# カウントを増やす
LeafCount+=1
# (3-4)「子」の情報から「親」の区間更新
# 「親」Li=(現在のLi)と(子のLi)の小さい方
LR[Parent][0]=min(LR[Parent][0],LR[Now][0])
# 「親」Ri=(現在のRi)と(子のRi)の大きい方
LR[Parent][1]=max(LR[Parent][1],LR[Now][1])
# i=1~N
for i in range(1,N+1):
# 答えを出力
print(*LR[i])
ABC241 A
# 入力の受け取り
a=list(map(int,input().split()))
# 最初に画面に表示されているのは「0」
k=0
# ボタンを押す
k=a[k]
# ボタンを押す
k=a[k]
# ボタンを押す
k=a[k]
# 答えを出力
print(k)
ABC241 B
# 入力の受け取り
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
# i=0~(M-1)
for i in range(M):
# B[i]がAに含まれるなら
if B[i] in A:
# Aに含まれるB[i]のうち先頭のものを削除
A.remove(B[i])
# そうでないならば(B[i]がAに含まれない)
else:
# 「No」を出力
print("No")
# 途中終了
exit()
# 「Yes」を出力
print("Yes")
ABC241 C
# pypyで提出
# 入力の受け取り
N=int(input())
# マス目の情報格納用
Grid=[]
# N回
for i in range(N):
# 文字列で受け取り
S=input()
# リストへ展開
S=list(S)
# Gridへ追加
Grid.append(S)
# 右方向へ「#」を数える
# 引数：行番号,列番号 → 返り値「#」の数
def SearchRight(G,R):
# 「#」の数
count=0
# i=0~5まで
for i in range(6):
# マス(行番号,列番号)=「#」ならば
if Grid[G][R+i]=="#":
# カウント
count+=1
# 数を返す
return count
# 下方向
def SearchDown(G,R):
count=0
for i in range(6):
if Grid[G+i][R]=="#":
count+=1
return count
# 右下方向
def SearchRightDown(G,R):
count=0
for i in range(6):
if Grid[G+i][R+i]=="#":
count+=1
return count
# 左下方向
def SearchLeftDown(G,R):
count=0
for i in range(6):
if Grid[G+i][R-i]=="#":
count+=1
return count
# G=0~(N-1)
for G in range(N):
# R=0~(N-1)
for R in range(N):
# 5マス右がマス目の中に収まっているならば
if R+5<N:
# 「#」の数が4つ以上なら
if 4<=SearchRight(G, R):
# 「Yes」を出力
print("Yes")
# 終了
exit()
# 5マス下がマス目の中に収まっているならば
if G+5<N:
if 4<=SearchDown(G, R):
print("Yes")
exit()
# 5マス右下がマス目の中に収まっているならば
if R+5<N and G+5<N:
if 4<=SearchRightDown(G, R):
print("Yes")
exit()
# 5マス左下がマス目の中に収まっているならば
if G+5<N and 0<=R-5:
if 4<=SearchLeftDown(G, R):
print("Yes")
exit()
# 「No」を出力
print("No")
# pypyで提出
N=int(input())
Grid=[]
for i in range(N):
S=input()
Grid.append(S)
# 「#」を数える
# 引数：行番号,列番号,行方向(0 or 1),列方向(-1 or 0 or 1)
def CountSharp(G,R,Gd,Rd):
# 「#」の数
count=0
# i=0~5まで
for i in range(6):
# マス(行番号+Gd*i,列番号+Rd*i)=「#」ならば
if Grid[G+Gd*i][R+Rd*i]=="#":
# カウント
count+=1
# 「#」が4個以上なら
if 4<=count:
print("Yes")
exit()
# G=0~(N-1)
for G in range(N):
# R=0~(N-1)
for R in range(N):
# 右方向
if R+5<N:CountSharp(G, R, 0, 1)
# 下方向
if G+5<N:CountSharp(G, R, 1, 0)
# 右下方向
if G+5<N and R+5<N:CountSharp(G, R, 1, 1)
# 左下方向
if G+5<N and 0<=R-5:CountSharp(G, R, 1, -1)
# 「No」を出力
print("No")
ABC241 D
# pypyで出力
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())
# クエリの情報格納用
querys=[]
# Aを用意(重複除去のためセット)
A=set()
# Q回
for i in range(Q):
# クエリを読み込み
tmp=list(map(int,input().split()))
# 記録
querys.append(tmp)
# xをAへ追加
x=tmp[1]
A.add(x)
# Aの長さをNとする
N=len(A)
# リストへ変換してソート
A=list(A)
A.sort()
# 変換用連想配列
Conv=dict()
# i=0~(Aの長さ-1)
for i in range(len(A)):
# 変換表を作成
# 「x」→「Aの小さい方から○番目」
Conv[A[i]]=i
# 左方向への区間和計算
# 引数：変換後のxのインデックス,k → 返り値：k≤区間和[m,x(のインデックス)]となるうち、最大のm
def NibutanLeft(xIndex,k):
# 左端(left)
l=0
# 右端(right)
r=xIndex
# 1<右-左の間
while 1<r-l:
# 中央(center)
c=(l+r)//2
# 区間和[c,xIndex]を計算
# k以上なら
if k<=FT.sum(c,xIndex):
# 左=中央と更新
l=c
# k以下なら
else:
# 右=中央と更新
r=c
# k≤区間和[r,xIndex]ならば
if k<=FT.sum(r,xIndex):
# rが一番近い
return r
# k≤区間和[l,xIndex]ならば
elif k<=FT.sum(l,xIndex):
# lが一番近い
return l
# どちらでもない
else:
# k≤区間和[m,x(のインデックス)]となるmが存在しない
return -1
# 右方向への区間和計算
def NibutanRight(xIndex,k):
l=xIndex
r=N-1
while 1<r-l:
c=(l+r)//2
if k<=FT.sum(xIndex,c):
r=c
else:
l=c
if k<=FT.sum(xIndex,l):
return l
elif k<=FT.sum(xIndex,r):
return r
else:
return -1
# FenwickTreeを用意
FT=FenwickTree(N)
# Q回
for i in range(Q):
# クエリ①
if querys[i][0]==1:
x=querys[i][1]
# FTに加算
FT.add(Conv[x],1)
# クエリ②
elif querys[i][0]==2:
x=querys[i][1]
k=querys[i][2]
if FT.sum(0, Conv[x])<k:
print(-1)
else:
# FTについてk≤区間和[m,x(のインデックス)]となるうち、最大のm
m=NibutanLeft(Conv[x],k)
# 答えを出力
print(A[m])
# クエリ③
else:
x=querys[i][1]
k=querys[i][2]
if FT.sum(Conv[x], N-1)<k:
print(-1)
else:
m=NibutanRight(Conv[x],k)
# 答えを出力
print(A[m])
ABC242 A
# 入力の受け取り
A,B,C,X=map(int,input().split())
# X≤Aの場合
if X<=A:
# 確率は1
print(1)
# A<X≤Bの場合
elif A<X<=B:
# 確率はC/(B-A)
print(C/(B-A))
# それ以外(B<X)の場合
else:
# 確率は0
print(0)
ABC242 B
# 入力の受け取り
S=input()
# (1)Sを1文字ずつリストに格納する
S=list(S)
# (2)Sをソートする
S.sort()
# (3)リストを結合する
S="".join(S)
# 答えの出力
print(S)
ABC242 C
# pypyで提出
# 余りの定義
mod=998244353
# 入力の受け取り
N=int(input())
# (1)表を作る
dp=[[0]*10 for i in range(N+1)]
# (2)すぐにわかるところを埋める
# i=1~9
for i in range(1,10):
# ・(1≤i≤9)
dp[1][i]=1
# (3)表の小さい方から答えにたどり着くまで埋める
# d=2~N
for d in range(2,N+1):
# i=1~9
for i in range(1,10):
# (2≤d,i=1)
if i==1:
dp[d][i]=dp[d-1][i]+dp[d-1][i+1]
# (2≤d,1≤i≤8)
elif 2<=i<=8:
dp[d][i]=dp[d-1][i-1]+dp[d-1][i]+dp[d-1][i+1]
# (2≤d,i=9)
else:
dp[d][i]=dp[d-1][i-1]+dp[d-1][i]
# 余りを取る
dp[d][i]%=mod
# (4)答えを出力する
# N行目を全て足す
ans=sum(dp[N])%mod
# 答えの出力
print(ans)
ABC243 A
# 入力の受け取り
V,A,B,C=map(int,input().split())
# シャンプーを使う
# i=0~(10^10)
for i in range(10**10):
# 父が使う
V-=A
# 残量がマイナスになったら
if V<0:
# 「F」を出力
print("F")
# 途中終了
exit()
# 母が使う
V-=B
# 残量がマイナスになったら
if V<0:
# 「M」を出力
print("M")
# 途中終了
exit()
# 高橋君が使う
V-=C
# 残量がマイナスになったら
if V<0:
# 「T」を出力
print("T")
# 途中終了
exit()
ABC243 B
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
# 1番目の答え
ans1=0
# i=0~(N-1)
for i in range(N):
# A[i]=B[i]ならば
if A[i]==B[i]:
# カウント
ans1+=1
# 答えを出力
print(ans1)
# 2番目の答え
ans2=0
# i=0~(N-1)
for i in range(N):
# j=0~(N-1)
for j in range(N):
# A[i]=B[j] かつ i≠j ならば
if A[i]==B[j] and i!=j:
# カウント
ans2+=1
# 答えの出力
print(ans2)
ABC243 C
# 入力の受け取り
N=int(input())
# 座標
p=[]
# 人がいるy座標の記録セット
ySet=set()
# N回
for i in range(N):
# 入力の受け取り
X,Y=map(int,input().split())
# 座標を記録
p.append([X,Y])
# y座標を記録
ySet.add(Y)
# 入力の受け取り
S=input()
# defaultdictをインポート
from collections import defaultdict
# 左に動く人のx座標の記録
directL=defaultdict(list)
# 右に動く人のy座標の記録
directR=defaultdict(list)
# i=0~(N-1)
for i in range(N):
# 人iのx,y座標
x,y=p[i]
# S[i]が「L」ならば
if S[i]=="L":
# 左に動く人として記録
directL[y].append(x)
# そうでなければ(S[i]が「R」ならば)
else:
# 右に動く人として記録
directR[y].append(x)
# 各yについて
for y in ySet:
# 左に動く人と右に動く人がそれぞれ1人以上いれば
if 1<=len(directL[y]) and 1<=len(directR[y]):
# 「右に動く人の最小x座標」<「左に動く人の最大x座標)」
if min(directR[y])<max(directL[y]):
# 「Yes」を出力
print("Yes")
# 終了
exit()
# 「No」を出力
print("No")
ABC243 D
# 入力の受け取り
N,X=map(int,input().split())
S=input()
# 移動の記録
Move=[]
# i=0~(N-1)
for i in range(N):
# ・記録が空の場合
if len(Move)==0:
# S[i]を記録
Move.append(S[i])
# ・記録が空でない場合
else:
# ・S[i]が「L」または「R」
if S[i]=="L" or S[i]=="R":
# S[i]を記録
Move.append(S[i])
# ・S[i]が「U」
else:
# ・S[i]が「U」かつ記録の末尾が「L」または「R」(「LU」「RU」になる場合)
if Move[-1]=="L" or Move[-1]=="R":
# 記録の末尾を消す
Move.pop()
# ・S[i]が「U」かつ記録の末尾が「U」
else:
# 「U」を記録
Move.append("U")
# シミュレーション
for s in Move:
# 「L」ならば2Xへ移動
if s=="L":
X*=2
# 「R」ならば(2X+1)へ移動
elif s=="R":
X=2*X+1
# 「U」ならばX//2へ移動
else:
X//=2
# 答えの出力
print(X)
ABC244 A
# 入力の受け取り
N=int(input())
S=input()
# Sの（N-1)文字目を出力
print(S[N-1])
# 入力の受け取り
N=int(input())
S=input()
# Sの右から1文字目を出力
print(S[-1])
ABC244 B
# 入力の受け取り
N=int(input())
T=input()
# 方向：最初は東
direct="East"
# 今いる座標
X=0
Y=0
# i=0~(N-1)
for i in range(N):
# T[i]=「S」のとき
if T[i]=="S":
# 東向きの場合
if direct=="East":
X+=1
# 南向きの場合
elif direct=="South":
Y-=1
# 西向きの場合
elif direct=="West":
X-=1
# 北向きの場合
elif direct=="North":
Y+=1
# そうでない場合(T[i]=「R」の場合)
else:
# 方向を変える
if direct=="East":
direct="South"
elif direct=="South":
direct="West"
elif direct=="West":
direct="North"
elif direct=="North":
direct="East"
# 答えの出力
print(X,Y)
# 入力の受け取り
N=int(input())
T=input()
# 方向：0=東,1=南,2=西,3=北
d=0
# 今いる座標
X,Y=0,0
# i=0~(N-1)
for i in range(N):
# T[i]=「S」のとき
if T[i]=="S":
# 向きによって分岐
if d==0:X+=1
elif d==1:Y-=1
elif d==2:X-=1
else:Y+=1
# そうでない場合
else:
# 1プラスして4で割った余りを取る(3の次が1になる)
d=(d+1)%4
# 答えの出力
print(X,Y)
ABC244 C
# 入力の受け取り
N=int(input())
# すでに使った数の記録
Used=[False]*(2*N+2)
# 最初は「1」を出力
print(1)
# 「1」は使用済み
Used[1]=True
# N回
for i in range(N+1):
# 青木くんの入力を受け取り
x=int(input())
# 「x」は使った
Used[x]=True
# x=「0」の場合
if x==0:
# 終了
exit()
# k=1~(2k+1)
for k in range(1,2*N+2):
# まだ使っていないなら
if Used[k]==False:
# 「k」を出力
print(k)
# 「k」は使った
Used[k]=True
# forループを抜ける
break
ABC244 D
# 入力の受け取り
S1,S2,S3=map(str,input().split())
T1,T2,T3=map(str,input().split())
# (1)3色すべて同じ位置
if S1==T1 and S2==T2 and S3==T3:
print("Yes")
# (2)1色のみ同じ位置で2色は逆
elif S1==T1 or S2==T2 or S3==T3:
print("No")
# (3)すべて違う位置
else:
print("Yes")
ABC244 E
# pypyで提出
# 余りの定義
mod=998244353
# 入力の受け取り
N,M,K,S,T,X=map(int,input().split())
# (1)表を作る
# 「i回の移動でjにたどり着く方法のうち、Xを偶数回/奇数回通る方法の数」
# 初期値は全て0
dp=[[[0]*2 for i in range(N+1)] for j in range(K+1)]
# 辺の格納
edge=[]
# M回
for i in range(M):
# 入力の受け取り
U,V=map(int,input().split())
# 辺の記録
edge.append([U,V])
# (2)すぐにわかるところを埋める
# ・(p=S) dp[0][p][偶]=1
dp[0][S][0]=1
# (3)表の小さい方から答えにたどり着くまで埋める
# i=1~K
for i in range(1,K+1):
# 各辺の組について
for U,V in edge:
# U→V
# V=Xの場合⇔Xを通る回数が増える⇔偶奇が入れ替わる
# ・(1≤i,U→V,V=X) dp[i][V][偶]+=dp[i-1][U][奇]
# ・(1≤i,U→V,V=X) dp[i][V][奇]+=dp[i-1][U][偶]
if V==X:
dp[i][V][0]+=dp[i-1][U][1]
dp[i][V][1]+=dp[i-1][U][0]
# V≠Xの場合⇔Xを通る回数が増えない⇔偶奇は同じ
# ・(1≤i,U→V,V≠X) dp[i][V][偶]+=dp[i-1][U][偶]
# ・(1≤i,U→V,V≠X) dp[i][V][奇]+=dp[i-1][U][奇]
else:
dp[i][V][0]+=dp[i-1][U][0]
dp[i][V][1]+=dp[i-1][U][1]
# 余りを取る
dp[i][V][0]%=mod
dp[i][V][1]%=mod
# 逆向きV→Uについても同様の処理を行う
if U==X:
dp[i][U][0]+=dp[i-1][V][1]
dp[i][U][1]+=dp[i-1][V][0]
else:
dp[i][U][0]+=dp[i-1][V][0]
dp[i][U][1]+=dp[i-1][V][1]
dp[i][U][0]%=mod
dp[i][U][1]%=mod
# (4)答えを出力する
print(dp[K][T][0])
ABC245 A
# 入力の受け取り
A,B,C,D=map(int,input().split())
# A<Cの場合
if A<C:
# 「Takahashi」を出力
print("Takahashi")
# C<Aの場合
elif C<A:
# 「Aoki」を出力
print("Aoki")
# それ以外(A=Cの場合)
else:
# B≤Dの場合
if B<=D:
# 「Takahashi」を出力
print("Takahashi")
# それ以外(D<Bの場合)
else:
# 「Aoki」を出力
print("Aoki")
ABC245 B
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# x=0,1,2,...,2000
for x in range(2001):
# xがAに含まれないならば
if x not in A:
# xを出力
print(x)
# 終了
exit()
ABC245 C
# 入力の受け取り(A,Bは先頭に「0」を埋めている)
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
B=[0]+list(map(int,input().split()))
# (1)表を作る
dp=[[False]*(N+1) for i in range(2)]
# (2)すぐにわかるところを埋める
# dp[A][0]=True,dp[B][0]=True
dp[0][1]=True
dp[1][1]=True
# (3)表の小さい方から答えにたどり着くまで埋める
# i=1~(N-1)
for i in range(1,N):
# dp[A][i]=Trueならば
# ⇔X[i]=A[i]の場合
if dp[0][i]==True:
# |X[i]-A[i+1]|=|A[i]-A[i+1]|≤Kならば
if abs(A[i]-A[i+1])<=K:
# dp[A][i+1]=True
dp[0][i+1]=True
# |X[i]-B[i+1]|=|A[i]-B[i+1]|≤Kならば
if abs(A[i]-B[i+1])<=K:
# dp[B][i+1]=True
dp[1][i+1]=True
# dp[B][i]=Trueならば
# ⇔X[i]=B[i]の場合
if dp[1][i]==True:
# |X[i]-A[i+1]|=|B[i]-A[i+1]|≤Kならば
if abs(B[i]-A[i+1])<=K:
# dp[A][i+1]=True
dp[0][i+1]=True
# |X[i]-A[i+1]|=|B[i]-B[i+1]|≤Kならば
if abs(B[i]-B[i+1])<=K:
# dp[B][i+1]=True
dp[1][i+1]=True
# (4)答えを出力する
# dp[A][N-1]=True または dp[B][N-1]=Trueならば
if dp[0][N]==True or dp[1][N]==True:
# 「Yes」を出力
print("Yes")
# どちらもFalseならば
else:
# 「No」を出力
print("No")
ABC245 D
# 入力の受け取り
N,M=map(int,input().split())
A=list(map(int,input().split()))
C=list(map(int,input().split()))
# Bを作る
B=[0]*(M+1)
# i=0~M
for i in range(M+1):
# x=A[N-1]B[M-(i-1)]+A[N-2]B[M-(i-2)]+...+A[N-k]B[M-(i-k)]+...A[N-i]B[M]
x=0
# k=1~i
for k in range(1,i+1):
# (N-k)がマイナスでなければ
if 0<=N-k:
x+=A[N-k]*B[M-(i-k)]
# マイナスならば
else:
# 次のforを抜ける
break
# 計算
B[M-i]=(C[M+N-i]-x)//A[N]
# 答えの出力
print(*B)
ABC246 A
# 入力の受け取り
x1,y1=map(int,input().split())
x2,y2=map(int,input().split())
x3,y3=map(int,input().split())
# x1=x2の場合
if x1==x2:
x4=x3
# x2=x3の場合
elif x2==x3:
x4=x1
# x3=x1の場合
elif x3==x1:
x4=x2
# y1=y2の場合
if y1==y2:
y4=y3
# y2=y3の場合
elif y2==y3:
y4=y1
# y3=y1の場合
elif y3==y1:
y4=y2
# 答えの出力
print(x4,y4)
ABC246 B
# 入力の受け取り
A,B=map(int,input().split())
# mathをインポート
import math
# 計算
x=A/math.sqrt(A**2+B**2)
y=B/math.sqrt(A**2+B**2)
# 答えの出力
print(x,y)
ABC246 C
# 入力の受け取り
N,K,X=map(int,input().split())
A=list(map(int,input().split()))
# i=0~(N-1)
for i in range(N):
# A[i]//X≤Kならば
if A[i]//X<=K:
# (A[i]//X)枚クーポンを使う
K-=A[i]//X
# 割引する
A[i]-=(A[i]//X)*X
# K<A[i]//Xならば(クーポンが足りなくてX円未満にできない場合)
else:
# 残りのクーポン(K枚)を全て使う
A[i]-=K*X
# クーポンを全て使ったので0枚になる
K=0
# 大きい順に並び替え
A.sort(reverse=True)
# 初期値 i=0
i=0
# クーポンがまだ残っている限り
while i<N and 0<K:
# A[i]にクーポンを使う=0円になる
A[i]=0
# クーポンを1枚使った
K-=1
# 次のiへ
i+=1
# Aの合計=答え
print(sum(A))
ABC246 D
# pypyで提出
# 入力の受け取り
N=int(input())
# 関数にする
def f(a,b):
return a**3+a**2*b+a*b**2+b**3
# 答え
ans=10**20
# b=0,1,2,...10^6
# (10^6より少し大きめにしている)
for b in range(10**6+100):
# (1)左=区間の最小、右=区間の最大 とする
# 左
l=0
# 右
r=10**6+100
# 1<(右-左)の間
while 1<r-l:
# (2)中央=(左+右)//2が条件を満たすか確認
c=(r+l)//2
# (3)(2)の結果より左または右を更新する
# 計算結果がN未満なら
if f(c,b)<N:
# 左=中央と更新
l=c
# 計算結果がN以上なら
else:
# 右=中央と更新
r=c
# N≤f(l,b)ならば
if N<=f(l,b):
# f(l,b)がansより小さければ更新
ans=min(ans,f(l,b))
# そうでなければ(f(l,b)<N⇔f(r,b)≤N)
else:
# f(r,b)がansより小さければ更新
ans=min(ans,f(r,b))
# 答えの出力
print(ans)
ABC247 A
# 入力の受け取り
S=input()
# 「0」+「Sの0文字目」+「Sの1文字目」+「Sの2文字目」
S="0"+S[0]+S[1]+S[2]
# 答えを出力
print(S)
ABC247 B
# 入力の受け取り
N=int(input())
# 姓のリスト
sList=[]
# 名のリスト
tList=[]
# N回
for i in range(N):
# 入力の受け取り
s,t=map(str,input().split())
# リストへ格納
sList.append(s)
tList.append(t)
# i=0~(N-1)
for i in range(N):
# (1)i≠jとなるsi,ti(他の人の姓、名)のリストを作る
# 「i番目の人以外の姓、名が入ったリスト」
OtherNameList=[]
# j=0~(N-1)
for j in range(N):
# i≠jならば(自分以外の姓、名をリストに入れるため)
if i!=j:
# j番目の人の姓をリストに追加
OtherNameList.append(sList[j])
# j番目の人の名をリストに追加
OtherNameList.append(tList[j])
# si,tiが両方ともにリストへ含まれていないかを確認する
if sList[i] in OtherNameList and tList[i] in OtherNameList:
# 含まれていたら「No」
print("No")
# 終了
exit()
# 「Yes」を出力
print("Yes")
ABC247 C
# 入力の受け取り
N=int(input())
# S1
S=[1]
# i=2~N
for i in range(2,N+1):
# Siを作る
S=S+[i]+S
# 答えの出力
print(*S)
ABC247 D
# 入力の受け取り
Q=int(input())
# dequeをインポート
from collections import deque
# dequeを用意
que=deque()
# Q回
for i in range(Q):
# 入力の受け取り(クエリ1,2で要素数が違うのでリストで受け取り)
query=list(map(int,input().split()))
# クエリ1
if query[0]==1:
# x,cを割り振り
x=query[1]
c=query[2]
# 「数」「個数」の順で記録
que.append([x,c])
# クエリ2
else:
# cを割り振り
c=query[1]
# 答え
ans=0
# c(取り出す個数)が0より大きい間
while 0<c:
# queの左端の要素を取り出し
# Num:数(Number)
# Count:個数
Num,Count=que.popleft()
# 「個数」≤「取り出す個数」なら
if Count<=c:
# 全て取り出す
# 「数」*「個数」を答えに加算
ans+=Num*Count
# 「個数」個取り出した
# 残りの取り出す個数をマイナス
c-=Count
# 「取り出す個数」<「個数」なら
else:
# c個取り出して終わり
# 答えに「数」*cを加算
ans+=Num*c
# 取り出した個数をマイナスして左端に戻す
que.appendleft([Num,Count-c])
# 取り出す個数を0にする
c=0
# 出力
print(ans)
ABC248 A
# 入力の受け取り
S=input()
# 「0」がSに含まれないならば
if "0" not in S:
# 「0」を出力
print(0)
elif "1" not in S:
print(1)
elif "2" not in S:
print(2)
elif "3" not in S:
print(3)
elif "4" not in S:
print(4)
elif "5" not in S:
print(5)
elif "6" not in S:
print(6)
elif "7" not in S:
print(7)
elif "8" not in S:
print(8)
elif "9" not in S:
print(9)
# 入力の受け取り
S=input()
# i=0~9
for i in range(10):
# i(を文字列にしたもの)がSに含まれないならば
if str(i) not in S:
# iを出力
print(i)
ABC248 B
# 入力の受け取り
A,B,K=map(int,input().split())
# AがB以上ならば
if B<=A:
# 「0」を出力
print(0)
# 途中終了
exit()
# i=1,2,3,...
for i in range(1,100):
A*=K
# スライムの数がB以上になったら
if B<=A:
# 「i」を出力
print(i)
# 途中終了
exit()
ABC248 C
# pypyで提出
# 入力の受け取り
N,M,K=map(int,input().split())
# 余りの定義
mod=998244353
# (1)表を作る
dp=[[0]*(K+1) for i in range(N+1)]
# (2)すぐにわかるところを埋める
# ・(x≤M)dp[1][x]=1
# ・(M<x)dp[1][x]=0
for x in range(1,M+1):
dp[1][x]=1
# (3)表の小さい方から答えにたどり着くまで埋める
# i=2~N
for i in range(2,N+1):
# x=1~K
for x in range(1,K+1):
# j=1~(x-1)
for j in range(1,x):
# ・(2≤i,1≤j≤x-1)x-j≤Mならばdp[i][x]+=dp[i-1][j]
if x-j<=M:
dp[i][x]+=dp[i-1][j]
# 余りを取る
dp[i][x]%=mod
# (4)答えを出力する
# 答え
ans=0
# x=1~K
for x in range(1,K+1):
# dp[N][1]~dp[N][K]の和
ans+=dp[N][x]
# 余りを取る
ans%=mod
# 答えを出力
print(ans)
ABC248 D
# pypyで提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# 1,2,3,...が何番目にあるかの記録 左端には「0」を入れておく
Aindx=[[0] for i in range(10**6)]
# i=0~(N-1)
for i in range(N):
# インデックス番号を記録
# 1インデックスなので「i+1」を記録することに注意
Aindx[A[i]].append(i+1)
# i=0~(N-1)
for i in range(10**6):
# 右端に∞=10^6を追加
Aindx[i].append(10**6)
# Xがあるインデックス番号のうちL以上で最小のもの
def NibutanLeft(X,L):
# (1)左=区間の最小、右=区間の最大 とする
# 左
l=0
# 右(=長さ-1)
r=len(Aindx[X])-1
# (4)1<(右-左)となっている間(2)~(4)を繰り返す
while 1<r-l:
# (2)中央=(左+右)//2が条件を満たすか確認
# 中央=(左+右)//2
c=(l+r)//2
# (3)(2)の結果より左または右を更新する
# ・(中央)番目の数がL以上
if L<=Aindx[X][c]:
# 左=中央と更新
r=c
# ・(中央)番目の数がLより小さい
else:
# 右=中央と更新
l=c
# 右を返す
return r
# Xがあるインデックス番号のうちR以下で最大のもの
def NibutanRight(X,R):
# (1)左=区間の最小、右=区間の最大 とする
# 左
l=0
# 右(=長さ-1)
r=len(Aindx[X])-1
# (4)1<(右-左)となっている間(2)~(4)を繰り返す
while 1<r-l:
# (2)中央=(左+右)//2が条件を満たすか確認
# 中央=(左+右)//2
c=(l+r)//2
# (3)(2)の結果より左または右を更新する
# ・(中央)番目の数がR以下
if Aindx[X][c]<=R:
# 左=中央と更新
l=c
# ・(中央)番目の数がRより大きい
else:
# 右=中央と更新
r=c
# 右を返す
return l
# 入力の受け取り
Q=int(input())
# Q回
for i in range(Q):
# 入力の受け取り
L,R,X=map(int,input().split())
# 「Xがあるインデックス番号のうちL以上で最小のもの」
Lindx=NibutanLeft(X, L)
# 「Xがあるインデックス番号のうちR以下で最大のもの」
Rindx=NibutanRight(X, R)
# 答えを出力
print(Rindx-Lindx+1)
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# 1,2,3,...が何番目にあるかの記録 左端には「0」を入れておく
Aindx=[[0] for i in range(10**6)]
# i=0~(N-1)
for i in range(N):
# インデックス番号を記録
# 1インデックスなので「i+1」を記録することに注意
Aindx[A[i]].append(i+1)
# i=0~(N-1)
for i in range(10**6):
# 右端に∞=10^6を追加
Aindx[i].append(10**6)
# 入力の受け取り
Q=int(input())
# bisectをインポート
import bisect
# Q回
for i in range(Q):
# 入力の受け取り
L,R,X=map(int,input().split())
# Lを大小関係を保ったままリストに挿入する位置のインデックス(同じ数があれば左側へ)
Lindx=bisect.bisect_left(Aindx[X], L)
# Rを大小関係を保ったままリストに挿入する位置のインデックス(同じ数があれば右側へ)
Rindx=bisect.bisect_right(Aindx[X], R)
# 答えを出力
print(Rindx-Lindx)
ABC249 A
# 入力の受け取り
A,B,C,D,E,F,X=map(int,input().split())
# 残り時間
Time=X
# 高橋くんの進んだ距離
Taka=0
# ・0<(残り時間)である間
while 0<Time:
# ・(進む時間)≤(残り時間)ならば
if A<=Time:
# (進んだ距離)に(進む時間*速度)をプラス
Taka+=A*B
# (残り時間)から(進む時間+休む時間)をマイナス
Time-=A+C
# ・(残り時間)<(進む時間)ならば
else:
# (進んだ距離)に(残り時間*速度)をプラス
Taka+=Time*B
# (残り時間)=0とする
Time=0
# 残り時間
Time=X
# 青木くんの進んだ距離
Aoki=0
# ・0<(残り時間)である間
while 0<Time:
# ・(進む時間)≤(残り時間)ならば
if D<=Time:
# (進んだ距離)に(進む時間*速度)をプラス
Aoki+=D*E
# (残り時間)から(進む時間+休む時間)をマイナス
Time-=D+F
# ・(残り時間)<(進む時間)ならば
else:
# (進んだ距離)に(残り時間*速度)をプラス
Aoki+=Time*E
# (残り時間)=0とする
Time=0
# (青木くんが進んだ距離)<(高橋くんが進んだ距離)の場合
if Aoki<Taka:
# 「Takahashi」を出力
print("Takahashi")
# (高橋くんが進んだ距離)<(青木くんが進んだ距離)の場合
elif Taka<Aoki:
# 「Aoki」を出力
print("Aoki")
# (青木くんが進んだ距離)=(高橋くんが進んだ距離)の場合
else:
# 「Draw」を出力
print("Draw")
ABC249 B
# 入力の受け取り
S=input()
# 「大文字が存在するか？」を管理する変数
OmoziExist=False
# 「小文字が存在するか？」を管理する変数
KomoziExist=False
# x：Sの各文字
for x in S:
# xが大文字なら
if x.isupper()==True:
# 「大文字が存在するか？」をTrueに
OmoziExist=True
# そうでない場合(xが小文字)
else:
# 「小文字が存在するか？」をTrueに
KomoziExist=True
# 大文字が存在しない または 小文字が存在しないならば
if OmoziExist==False or KomoziExist==False:
# 「No」を出力
print("No")
# 途中終了
exit()
# Sの文字数
N=len(S)
# i=0~(N-1)
for i in range(N):
# k=(i+1)~(N-1)
for k in range(i+1,N):
# 重複⇔(Sのi文字目)=(Sのk文字目)
if S[i]==S[k]:
# 「No」を出力
print("No")
# 途中終了
exit()
# 「Yes」を出力
print("Yes")
# 入力の受け取り
S=input()
ans="Yes"
# Sが全て大文字または小文字なら「No」
if S.isupper() or S.islower():ans="No"
# Sをsetに展開した長さとSの文字数が一致していなければ「No」
if len(set(S))!=len(S):ans="No"
print(ans)
ABC249 C
# 入力の受け取り
N,K=map(int,input().split())
# Sを格納するリスト
SList=[]
# i=0~(N-1)
for i in range(N):
# 入力の受け取り
S=input()
# リストへ格納
SList.append(S)
# 答え
ans=0
# bitnum=(000...0)~(111...1)(長さNの2進数)
for bitnum in range(1<<N):
# 暫定答え(tmp=tmporary：一時的な)
anstmp=0
# 選ばれた文字列の格納リスト
Choosed=[]
# shift=0~(N-1)
for shift in range(N):
# (bitnumをshift個右シフト) & 1 =1ならば
if bitnum>>shift & 1:
# 文字列を選ぶ
# ⇔(Shift)番目の文字列をChoosedに格納
Choosed.append(SList[shift])
# code=97~122
for code in range(97,123):
# Alphabet=「a」「b」...「z」
Alphabet=chr(code)
# Alphabetが含まれる文字列の数をカウント
InCount=0
# T=Choosedに含まれる文字列を順に格納
for T in Choosed:
# TにAlphabetが含まれるなら
if Alphabet in T:
# カウントする
InCount+=1
# カウント=Kならば
if InCount==K:
# Alphabetが選んだ文字列のうちちょうどK個に含まれる
anstmp+=1
# ans_tmpのほうが大きければansを更新
ans=max(anstmp,ans)
# 答えを出力
print(ans)
ABC249 D
# pypyで提出
# 入力の受け取り
N=int(input())
A=list(map(int,input().split()))
# 1,2,3,..がいくつ含まれるかカウントするリスト
Count=[0]*10**6
# i=0~(N-1)
for i in range(N):
# 1,2,3,..がいくつ含まれるかカウント
Count[A[i]]+=1
# 答え
ans=0
# i=0~(N-1)
for i in range(N):
# Aj=1,2,3,...で試し割り
Aj=1
# Aj≤√A[i]⇔Aj^2≤A[i]の間
while Aj**2<=A[i]:
# 割り切れたら
if A[i]%Aj==0:
# Akを確認
Ak=A[i]//Aj
# Aj=Akならば
if Aj==Ak:
# (Ajの個数)*(Akの個数)
ans+=Count[Aj]*Count[Ak]
# Aj≠Akならば
else:
# (Ajの個数)*(Akの個数)*2
# AjとAkを入れ替えできるため2倍する
ans+=Count[Aj]*Count[Ak]*2
# 次のAjへ
Aj+=1
# 答えを出力
print(ans)
ABC250 A
# 入力の受け取り
H,W=map(int,input().split())
R,C=map(int,input().split())
# 答えの個数
ans=0
# 上マスが枠内にあるか
if 1<=R-1:
# 答えにプラス1
ans+=1
# 下マスが枠内にあるか
if R+1<=H:
ans+=1
# 左マスが枠内にあるか
if 1<=C-1:
ans+=1
# 右マスが枠内にあるか
if C+1<=W:
ans+=1
# 答えの出力
print(ans)
ABC250 B
# 入力の受け取り
N,A,B=map(int,input().split())
# 外側の行
# NGyou=1~N
for NGyou in range(1,N+1):
# 奇数の場合
# ⇔2で割った余りが1
if NGyou%2==1:
# a=1~A
for a in range(1,A+1):
# 行の中身
Gyou=""
# 外側の列
# NRretu=1~N
for NRetu in range(1,N+1):
# 奇数の場合
# ⇔2で割った余りが1
if NRetu%2==1:
# 白マスがB個
Gyou+="."*B
# 偶数の場合
else:
# 黒マスがB個
Gyou+="#"*B
# 出力
print(Gyou)
# 偶数の場合
else:
# a=1~A
for a in range(1,A+1):
# 行の中身
Gyou=""
# 外側の列
# NRretu=1~N
for NRetu in range(1,N+1):
# 奇数の場合
# ⇔2で割った余りが1
if NRetu%2==1:
# 黒マスがB個
Gyou+="#"*B
# 偶数の場合
else:
# 白マスがB個
Gyou+="."*B
# 出力
print(Gyou)
ABC250 C
# 入力の受け取り
N,Q=map(int,input().split())
# A=[0,1,2,...,N]
A=list(range(N+1))
# indx=[0,1,2,...,N]
indx=list(range(N+1))
# Q回
for i in range(Q):
# 入力の受け取り
x=int(input())
# xのインデックス番号を確認
xIndx=indx[x]
# 右端でない⇔xのインデックス番号≠Nの場合
if xIndx!=N:
# xの右のボールに書いている番号
RightX=A[xIndx+1]
# 入れ替える
A[xIndx],A[xIndx+1]=A[xIndx+1],A[xIndx]
# インデックス番号を更新する
indx[x]=xIndx+1
indx[RightX]=xIndx
# 右端⇔xのインデックス番号=Nの場合
else :
# xの左のボールに書いている番号
LeftX=A[xIndx-1]
# 入れ替える
A[xIndx],A[xIndx-1]=A[xIndx-1],A[xIndx]
# インデックス番号を更新する
indx[x]=xIndx-1
indx[LeftX]=xIndx
# Aを出力
# 0番目は不要なので1番目~
# 「*」をつけると[]なしで出力できる
print(*A[1:])
ABC250 D
# エラトステネスの篩
def Eratosthenes(N):
# 素数であるかの判定リスト
IsPrime=[True]*(N+1)
# i=2,3,4,...
i=2
# i≤√Nまで⇔i^2≤Nまで
while i**2<=N:
# iが素数でなければ
if IsPrime[i]==False:
# 次のiへ
i+=1
continue
# k=2,3,4,...
k=2
while i*k<=N:
# iの倍数は素数でない
IsPrime[i*k]=False
# 次のkへ
k+=1
# 次のkへ
i+=1
# 素数リスト
PList=[]
# i=2~N
for i in range(2,N+1):
# iが素数ならば
if IsPrime[i]==True:
# リストへ入れる
PList.append(i)
# リストを返す
return PList
# 入力の受け取り
N=int(input())
# 10^6以下の素数リストを作成
P=Eratosthenes(10**6)
# 答え
ans=0
# 素数リストの長さ
lenP=len(P)
# 最後の素数の番号(0インデックス)
k=lenP-1
# i=0~(lenP-1)
for i in range(lenP):
# p=i番目の素数(0インデックス)
# q=k番目の素数(0インデックス)
# p*q^3≤Nとなるまでkを減らしていく
while i<k and N<P[i]*P[k]**3:
k-=1
# k≤iとなったら
if k<=i:
# 答えの出力
print(ans)
# 途中終了
exit()
# i+1,i+2,...,k番目の素数までqとして使用できる
# ⇔(k-i)個
ans+=k-i
def Eratosthenes(N):
IsPrime=[True]*(N+1)
i=2
while i**2<=N:
if IsPrime[i]==False:
i+=1
continue
k=2
while i*k<=N:
IsPrime[i*k]=False
k+=1
i+=1
PList=[]
for i in range(2,N+1):
if IsPrime[i]==True:
PList.append(i)
return PList
# 入力の受け取り
N=int(input())
# 素数リストを作る
P=Eratosthenes(10**6)
# 素数リストの長さ
lenP=len(P)
# 二分探索
def Nibutan(i):
# 左
l=0
# 右
r=lenP-1
# 1<(右-左) ならば
while 1<(r-l):
# 中央=(左+右)//2
c=(l+r)//2
# P[i]=i番目の素数
# P[c]=c番目の素数
# 条件を満たすなら
if P[i]*P[c]**3<=N:
# 左=中央と更新
l=c
# 条件を満たさないなら
else:
# 右=中央と更新
r=c
# 左を返す
return l
# 答え
ans=0
# i=0~(素数リストの長さ-1)
for i in range(lenP):
# P[i]*P[k]^3≤Nとなるもののうち最大のk
k=Nibutan(i)
# i<kならば
if i<k:
# (k-i)個プラス
ans+=k-i
# そうでないなら
else:
# 探索終了
break
# 答えを出力
print(ans)