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

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

https://atcoder.jp/contests/abc236/tasks/abc236_a

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

https://atcoder.jp/contests/abc236/tasks/abc236_b

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

https://atcoder.jp/contests/abc236/tasks/abc236_c

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

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

https://atcoder.jp/contests/abc236/tasks/abc236_d

```python:
# 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

https://atcoder.jp/contests/abc237/tasks/abc237_a

```python:
#入力の受け取り
N=int(input())
 
# -2^31以上2^31未満ならば
if(-2)**31<=N<2**31:
    # 「Yes」 を出力
    print("Yes")
#そうでないならば
else:
    # 「No を出力」
    print("No")
```

# ABC237 B

https://atcoder.jp/contests/abc237/tasks/abc237_b

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

https://atcoder.jp/contests/abc237/tasks/abc237_c

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

https://atcoder.jp/contests/abc237/tasks/abc237_d

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

https://atcoder.jp/contests/abc238/tasks/abc238_a

```python:
# 入力の受け取り
n=int(input())
 
# 2≤n≤4の場合
if 2<=n<=4:
    # 「No」を出力
    print("No")
# それ以外の場合
else:
    # 「Yes」を出力
    print("Yes")
```

# ABC238 B

https://atcoder.jp/contests/abc238/tasks/abc238_b

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

https://atcoder.jp/contests/abc238/tasks/abc238_c

```python:
# 余りを定義
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

https://atcoder.jp/contests/abc238/tasks/abc238_d

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

https://atcoder.jp/contests/abc239/tasks/abc239_a

```python:
# 入力の受け取り
H=int(input())
 
# ルートの計算のためsqrtをインポート
import math
 
# 答えの出力
print(math.sqrt(H*(12800000+H)))
```

# ABC239 B

https://atcoder.jp/contests/abc239/tasks/abc239_b

```python:
# 入力の受け取り
X=int(input())
 
# Xを10で割った商を出力
print(X//10)
```

# ABC239 C

https://atcoder.jp/contests/abc239/tasks/abc239_c

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

```python:
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

https://atcoder.jp/contests/abc239/tasks/abc239_d

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

```python:
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

https://atcoder.jp/contests/abc239/tasks/abc239_e

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

https://atcoder.jp/contests/abc240/tasks/abc240_a

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

https://atcoder.jp/contests/abc240/tasks/abc240_b

```python:
# 入力の受け取り
N=int(input())
a=list(map(int,input().split()))
 
# リスト→セットへ変換
aSet=set(a)
 
# 長さを出力
print(len(aSet))
```

# ABC240 C

https://atcoder.jp/contests/abc240/tasks/abc240_c

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

https://atcoder.jp/contests/abc240/tasks/abc240_d

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

https://atcoder.jp/contests/abc240/tasks/abc240_e

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

https://atcoder.jp/contests/abc241/tasks/abc241_a

```python:
# 入力の受け取り
a=list(map(int,input().split()))
 
# 最初に画面に表示されているのは「0」
k=0
 
# ボタンを押す
k=a[k]
 
# ボタンを押す
k=a[k]
 
# ボタンを押す
k=a[k]
 
# 答えを出力
print(k)
```

# ABC241 B

https://atcoder.jp/contests/abc241/tasks/abc241_b

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

https://atcoder.jp/contests/abc241/tasks/abc241_c

```python:
# 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")
```

```python:
# 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

https://atcoder.jp/contests/abc241/tasks/abc241_d

```python:
# 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

https://atcoder.jp/contests/abc242/tasks/abc242_a

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

https://atcoder.jp/contests/abc242/tasks/abc242_b

```python:
# 入力の受け取り
S=input()
 
# (1)Sを1文字ずつリストに格納する
S=list(S)
 
# (2)Sをソートする
S.sort()
 
# (3)リストを結合する
S="".join(S)
 
# 答えの出力
print(S)
```

# ABC242 C

https://atcoder.jp/contests/abc242/tasks/abc242_c

```python:
# 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

https://atcoder.jp/contests/abc243/tasks/abc243_a

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

https://atcoder.jp/contests/abc243/tasks/abc243_b

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

https://atcoder.jp/contests/abc243/tasks/abc243_c

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

https://atcoder.jp/contests/abc243/tasks/abc243_d

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

https://atcoder.jp/contests/abc244/tasks/abc244_a

```python:
# 入力の受け取り
N=int(input())
S=input()
 
# Sの（N-1)文字目を出力
print(S[N-1])
```

```python:
# 入力の受け取り
N=int(input())
S=input()
 
# Sの右から1文字目を出力
print(S[-1])
```

# ABC244 B

https://atcoder.jp/contests/abc244/tasks/abc244_b

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

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

https://atcoder.jp/contests/abc244/tasks/abc244_c

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

https://atcoder.jp/contests/abc244/tasks/abc244_d

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

https://atcoder.jp/contests/abc244/tasks/abc244_e

```python:
# 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

https://atcoder.jp/contests/abc245/tasks/abc245_a

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

https://atcoder.jp/contests/abc245/tasks/abc245_b

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

https://atcoder.jp/contests/abc245/tasks/abc245_c

```python:
# 入力の受け取り(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

https://atcoder.jp/contests/abc245/tasks/abc245_d

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

https://atcoder.jp/contests/abc246/tasks/abc246_a

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

https://atcoder.jp/contests/abc246/tasks/abc246_b

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

https://atcoder.jp/contests/abc246/tasks/abc246_c

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

https://atcoder.jp/contests/abc246/tasks/abc246_d

```python:
# 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

https://atcoder.jp/contests/abc247/tasks/abc247_a

```python:
# 入力の受け取り
S=input()
 
# 「0」+「Sの0文字目」+「Sの1文字目」+「Sの2文字目」
S="0"+S[0]+S[1]+S[2]
 
# 答えを出力
print(S)
```

# ABC247 B

https://atcoder.jp/contests/abc247/tasks/abc247_b

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

https://atcoder.jp/contests/abc247/tasks/abc247_c

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

https://atcoder.jp/contests/abc247/tasks/abc247_d

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

https://atcoder.jp/contests/abc248/tasks/abc248_a

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

```python:
# 入力の受け取り
S=input()
 
# i=0~9
for i in range(10):
    # i(を文字列にしたもの)がSに含まれないならば
    if str(i) not in S:
        # iを出力
        print(i)
```

# ABC248 B

https://atcoder.jp/contests/abc248/tasks/abc248_b

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

https://atcoder.jp/contests/abc248/tasks/abc248_c

```python:
# 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

https://atcoder.jp/contests/abc248/tasks/abc248_d

```python:
# 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)
```

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

https://atcoder.jp/contests/abc249/tasks/abc249_a

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

https://atcoder.jp/contests/abc249/tasks/abc249_b

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

```

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

https://atcoder.jp/contests/abc249/tasks/abc249_c

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

https://atcoder.jp/contests/abc249/tasks/abc249_d

```python:
# 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

https://atcoder.jp/contests/abc250/tasks/abc250_a

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

https://atcoder.jp/contests/abc250/tasks/abc250_b

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

https://atcoder.jp/contests/abc250/tasks/abc250_c

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

https://atcoder.jp/contests/abc250/tasks/abc250_d

```python:
# エラトステネスの篩
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
```

```python:
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)
```