本記事は拙著『AtCoder 最速で緑になる 基礎・典型50問詳細解説』のコピペ用コード集ですです。
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP
【booth(pdf)】
https://booth.pm/ja/items/4102300
冒頭5問をサンプルとして無料公開しています。
https://qiita.com/sano192/items/6361ed72106cb6dd5843
1 入力と出力 ABC205 A Dif:6
提出
# 入力の受け取り
A,B=map(int, input().split())
# A×(1/100)×Bを出力
print(A*(1/100)*B)
2 条件分岐1 ABC219 A Dif:6
提出
# 入力の受け取り
X=int(input())
# 初級の場合
if 0<=X<40:
# 40-Xを出力
print(40-X)
# 中級の場合
elif 40<=X<70:
# 70-Xを出力
print(70-X)
# 上級の場合
elif 70<=X<90:
# 90-Xを出力
print(90-X)
# エキスパートの場合
else:
# "expert"を出力
print("expert")
3 関数 ABC234 A Dif:7
提出
# 入力の受け取り
t=int(input())
# 関数の定義
# 引数；x 返り値：x^2+2x+3
def f(x):
return x**2+2*x+3
# 答えの計算
ans=f(f(f(t)+t)+f(f(t)))
# 答えの出力
print(ans)
4 for文 ABC204 B Dif:9
提出
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# 答え
ans=0
# i=0~N-1まで
for i in range(N):
# A[i]が10より大きければ
if 10<A[i]:
# A[i]-10をansにプラスする
ans+=A[i]-10
# 答えの出力
print(ans)
別解
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# 答えの格納用変数
ans=0
# xへAの値を順に入れる
for x in A:
# 0と(x-10)の大きい方を足す
ans+=max(0,x-10)
# 答えの出力
print(ans)
5 文字列操作 ABC232 A Dif:9
提出
# 入力の受け取り
S=input()
# Sの0文字目と2文字目を整数へ変換
S0=int(S[0])
S2=int(S[2])
# 掛け算して出力
print(S0*S2)
6 文字コード変換 ABC218 B Dif:14
提出
# 入力の受け取り
P=list(map(int, input().split()))
# 答えを格納する変数
ans=""
# i=0~25
for i in range(26):
# 文字コード「P[i]+96」の文字をansの末尾へ追加
ans+=chr(P[i]+96)
# 答えを出力
print(ans)
別解
# 入力の受け取り
P=list(map(int, input().split()))
def convert(x):
if x==1:return "a"
if x==2:return "b"
if x==3:return "c"
if x==4:return "d"
if x==5:return "e"
if x==6:return "f"
if x==7:return "g"
if x==8:return "h"
if x==9:return "i"
if x==10:return "j"
if x==11:return "k"
if x==12:return "l"
if x==13:return "m"
if x==14:return "n"
if x==15:return "o"
if x==16:return "p"
if x==17:return "q"
if x==18:return "r"
if x==19:return "s"
if x==20:return "t"
if x==21:return "u"
if x==22:return "v"
if x==23:return "w"
if x==24:return "x"
if x==25:return "y"
if x==26:return "z"
ans=""
# i=0~25
for i in range(26):
# P[i]を変換してansの末尾へ追加
ans+=convert(P[i])
# 答えを出力
print(ans)
7 リスト操作 ABC241 A Dif:15
提出
# 入力の受け取り
a=list(map(int,input().split()))
# 最初に画面に表示されているのは「0」
k=0
# ボタンを押す
k=a[k]
# ボタンを押す
k=a[k]
# ボタンを押す
k=a[k]
# 答えを出力
print(k)
8 set ABC240 B Dif:19
提出
# 入力の受け取り
N=int(input())
a=list(map(int,input().split()))
# リスト→セットへ変換
aSet=set(a)
# 長さを出力
print(len(aSet))
9 図形 ABC246 A Dif:28
提出
# 入力の受け取り
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)
10 二次元配列、ソート1 ABC201 B Dif:32
提出
# 入力の受け取り
N=int(input())
# 山の高さ、名前を格納するリスト
Mountains=[]
# N回
for i in range(N):
# 入力の受け取り
S,T=map(str, input().split())
# Tを整数へ変換
T=int(T)
# T,Sの順に格納
Mountains.append([T,S])
# 大きい順に並び替え
Mountains.sort(reverse=True)
# 1番目のリストの、1番目の要素を出力
print(Mountains[1][1])
11 二重ループ ABC234 B Dif:46
提出
# 入力の受け取り
N=int(input())
# 座標の格納用
x=[]
y=[]
# i=0~(N-1)
for i in range(N):
# 入力の受け取り
xi,yi=map(int,input().split())
# 座標の格納
x.append(xi)
y.append(yi)
# mathのインポート
import math
# 答え
ans=0
# i=0~(N-1)
for i in range(N):
# j=(i+1)~(N-1)
for j in range(i+1,N):
# 距離の計算
length=math.sqrt((x[i]-x[j])**2+(y[i]-y[j])**2)
# そこまでの値より大きければ更新
ans=max(ans,length)
# 答えの出力
print(ans)
12 条件分岐2 ABC205 C Dif:63
提出
# 入力の受け取り
A,B,C=map(int, input().split())
# C：偶数
if C%2==0:
# A：0以上(+)
if 0<=A:
# B：0以上(+)
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# B：0未満(-)
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# A：0未満(-)
if A<0:
# B：0以上(+)
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# B：0未満(-)
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# C：奇数
if C%2==1:
# A：0以上(+)
if 0<=A:
# B：0以上(+)
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# B：0未満(-)
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「>」を出力
print(">")
# |A|=|B|
if abs(A)==abs(B):
# 「>」を出力
print(">")
# |A|>|B|
if abs(A)>abs(B):
# 「>」を出力
print(">")
# A：0未満(-)
if A<0:
# B：0以上(+)
if 0<=B:
# |A|<|B|
if abs(A)<abs(B):
# 「<」を出力
print("<")
# |A|=|B|
if abs(A)==abs(B):
# 「<」を出力
print("<")
# |A|>|B|
if abs(A)>abs(B):
# 「<」を出力
print("<")
# B：0未満(-)
if B<0:
# |A|<|B|
if abs(A)<abs(B):
# 「>」を出力
print(">")
# |A|=|B|
if abs(A)==abs(B):
# 「=」を出力
print("=")
# |A|>|B|
if abs(A)>abs(B):
# 「<」を出力
print("<")
別解
A,B,C=map(int, input().split())
if C%2==0:
if abs(A)<abs(B):print("<")
elif abs(A)==abs(B):print("=")
else:print(">")
else:
if 0<=A:
if 0<=B:
if abs(A)<abs(B):print("<")
elif abs(A)==abs(B):print("=")
else:print(">")
else:print(">")
else:
if 0<=B:print("<")
else:
if abs(A)<abs(B):print(">")
elif abs(A)==abs(B):print("=")
else:print("<")
13 周期性 ABC220 C Dif:119
提出
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
X=int(input())
# Aの合計
Asum=sum(A)
# 必要なAの数：X//(Aの合計)
quo=X//Asum
# 項数(k)：(Aの個数)×(Aの要素数)
k=N*quo
# 合計(Bsum)：(Aの個数)×(Aの合計)
Bsum=Asum*quo
# Xを超えるまでAの要素を順に足していく
# i=0~(N-1)まで
for i in range(N):
# 合計に+A[i]
Bsum+=A[i]
# 項数に+1
k+=1
# X<合計になったら
if X<Bsum:
# 答えを出力
print(k)
# 終了
exit()
14 逆順操作 ABC216 C Dif:145
提出
# 入力の受け取り
N=int(input())
# 答え(最初は空)
ans=""
# Nが0より大きい間
while 0<N:
# Nが偶数なら
if N%2==0:
# ansの左端にBを追加
ans="B"+ans
# 2で割る
N//=2
# それ以外(Nが奇数なら)
else:
# ansの左端にAを追加
ans="A"+ans
# 1を引く
N-=1
# 答えを出力
print(ans)
15 貪欲法 ABC229 C Dif:165
提出
# 入力の受け取り
N,W=map(int,input().split())
# チーズの情報
Cheese=[]
# N回
for i in range(N):
# 入力の受け取り
A,B=map(int,input().split())
# 情報の格納
Cheese.append([A,B])
# 美味しさの大きい順にソート
Cheese.sort(reverse=True)
# 答え
ans=0
# i=0～(N-1)まで
for i in range(N):
# i種類目のチーズの美味しさ
Delicious=Cheese[i][0]
# i種類目のチーズの重さ
Weight=Cheese[i][1]
# 重さ≤Wなら
if Weight<=W:
# 全部載せる
ans+=Delicious*Weight
# 載せられる残りの重さ
W-=Weight
# そうでないなら(W<重さなら)
else:
# W[g]分載せる
ans+=Delicious*W
# これ以上載せられないからforを抜ける
break
# 答えの出力
print(ans)
16 インタラクティブ ABC244 C Dif:165
提出
# 入力の受け取り
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
17 連想配列1 ABC206 C Dif:171
提出
# 入力の受け取り
N=int(input())
A=list(map(int, input().split()))
# defaultdictのインポート
from collections import defaultdict
# 要素の出現回数を数える連想配列countを用意
count=defaultdict(int)
# Aのそれぞれの要素(a)について
for i in range(N):
# 出現回数を+1
count[A[i]]+=1
# 全組み合わせ=NC2=N*(N-1)//2
ans=N*(N-1)//2
# countの値(x)それぞれについて
for x in count.values():
# Ai=Ajとなる組の数x*(x-1)//2を引く
ans-=x*(x-1)//2
# 答えの出力
print(ans)
18 itertools ABC215 C Dif:178
提出
# 入力の受け取り(Kも文字列として)
S,K=map(str,input().split())
# Kを整数に変換
K=int(K)
# 作れる文字を格納するセット(リストだと重複するものも入ってしまうためセットを使う)
Sset=set()
# itertoolsをインポート
import itertools
# p=(0,1,2),(0,2,1),(1,0,2),(1,2,0),...
for p in itertools.permutations(range(len(S))):
# 作った文字列を記録する変数
Stmp=""
# pを使って文字を作成
# 例：p=(2,0,1)ならStmp=Sの2文字目+Sの0文字目+Sの1文字目
for i in p:
Stmp+=S[i]
# できた文字をSsetに格納(setへの追加はappendではなくaddであることに注意)
Sset.add(Stmp)
# ソートするためにリストへ変換
Slist=list(Sset)
# 辞書順にソート
Slist.sort()
# K-1番目の要素を出力
print(Slist[K-1])
19 二分探索1 ABC231 C Dif:194
提出
# 入力の受け取り
N,Q=map(int,input().split())
A=list(map(int,input().split()))
# Aをソート
A.sort()
# 二分探索
# 引数：x 返り値：「身長がx以上の中で最も小さい人は何番目か」
def Nibutan(x):
# 左端
l=0
# 右端
r=N-1
# 1<右端-左端の間
while 1<r-l:
# 中央
c=(l+r)//2
# A[c]<xならば(条件を満たさない場合)
if A[c]<x:
# 左端を中央へ更新
l=c
# そうでなければ(x≤A[c] 条件を満たす場合)
else:
# 右端を中央へ更新
r=c
# 右端を返す
return r
# Q回
for i in range(Q):
# 入力の受け取り
x=int(input())
# xがAの中で最小の要素以下である場合
if x<=A[0]:
# N人
print(N)
# xがAの中で最大の要素より大きい場合
elif A[N-1]<x:
print(0)
# それ以外
else:
# 答えの出力
print(N-Nibutan(x))
別解
# 入力の受け取り
N,Q=map(int,input().split())
A=list(map(int,input().split()))
# Aをソート
A.sort()
# クエリの記録
query=[]
# Q回
for i in range(Q):
# 入力の受け取り
x=int(input())
# [x,i番目のクエリ]と記録
query.append([x,i])
# クエリをxの小さい順にソート
query.sort()
# 答えの格納用リスト
Ans=[0]*Q
# インデックス：初期値は0
k=0
# 各クエリについて
for x,i in query:
# A[k]<xである限り
while k<N and A[k]<x:
# kを先に進める
k+=1
# A[k]はx以上
# i番目のクエリの答えを記録
Ans[i]=N-k
# 答えの出力
for a in Ans:print(a)
20 ソート2 ABC209 C Dif:285
提出
# 入力の受け取り
N=int(input())
C=list(map(int, input().split()))
# mod=10^9+7と定義
mod=10**9+7
# Cをソート
C.sort()
# 答えを格納する変数
ans=1
# i=0~(N-1)まで
for i in range(N):
# もしC[i]-i=0ならば
if C[i]-i==0:
# 0を出力
print(0)
# 終了
exit()
# ansにC[i]-iをかける
ans*=C[i]-i
# 余りを取る
ans%=mod
# 答えを出力
print(ans)
21 シミュレーション1 ABC214 C Dif:319
提出
# 入力の受け取り
N=int(input())
S=list(map(int, input().split()))
T=list(map(int, input().split()))
# i番目のすぬけ君が初めて宝石をもらう時間
# 初期値は大きい数
time=[10**15]*N
# 1週目
for i in range(N):
# 次のすぬけ君の番号。i=N-1のとき、次のすぬけ君の番号=Nではなく=0とするためNで割った余りを取る
next=(i+1)%N
# 高橋君からもらうのが早いか、隣のすぬけ君からもらうのが早いか
time[next]=min(T[next],time[i]+S[i])
# 2周目
for i in range(N):
next=(i+1)%N
# 1周目で計算した時間が早いか、隣のすぬけ君からもらうのが早いか
time[next]=min(time[next],time[i]+S[i])
# 答えの出力
for i in range(N):
print(time[i])
22 bit全探索 ABC221 C Dif:379
提出
# 入力の受け取り(文字列)
N=input()
# 答え 初期値は0
ans=0
# bitnum=(000000),(000001),(000010),(000011),...,(111111)まで
for bitnum in range(1<<len(N)):
# グループA,Bを用意
A=[]
B=[]
# shift=0~(Nの桁数-1)まで
for shift in range(len(N)):
# bitnumのshift桁目が「0」か「1」か確認
# 右にshift分シフト演算して「1」とアンド演算
# 0ならば
if bitnum>>shift & 1==0:
# グループAへ追加
A.append(N[shift])
# 1ならば
else:
# グループBへ追加
B.append(N[shift])
# グループAまたはグループBが空なら
if A==[] or B==[]:
# 次のbitnum
continue
# 大きい順に並び替え
A.sort(reverse=True)
B.sort(reverse=True)
# A,Bを結合
A_join="".join(A)
B_join="".join(B)
# 整数にして掛け算
tmp_ans=int(A_join)*int(B_join)
# ansよりtmp_ansが大きかったらansを更新
ans=max(ans,tmp_ans)
# 答えの出力
print(ans)
23 区間の処理 ABC207 C Dif:397
提出
# 入力の受け取り
N=int(input())
# 区間の格納リスト
section=[]
# N回
for i in range(N):
# 入力の受け取り
t,l,r=map(int, input().split())
# t=1の場合
if t==1:
# 区間[l,r]を追加
section.append([l,r])
# t=2の場合
elif t==2:
# 区間[l,r-0.1]を追加
section.append([l,r-0.1])
# t=3の場合
elif t==3:
# 区間[l+0.1,r]を追加
section.append([l+0.1,r])
# t=4の場合
elif t==4:
# 区間[l+0.1,r-0.1]を追加
section.append([l+0.1,r-0.1])
# 答えの格納用変数
ans=0
# i=0~(N-1)まで
for i in range(N):
# j=(i+1)~(N-1)まで
for j in range(i+1,N):
# 区間iの左端
il=section[i][0]
# 区間iの右端
ir=section[i][1]
# 区間jの左端
jl=section[j][0]
# 区間jの右端
jr=section[j][1]
# (区間iの左端)≤(区間jの左端)≤(区間iの右端)
if il<=jl<=ir:
# 答えにカウント
ans+=1
# (区間iの左端)≤(区間jの右端)≤(区間iの右端)
elif il<=jr<=ir:
# 答えにカウント
ans+=1
# (区間jの左端)≤(区間iの左端)≤(区間jの右端)
elif jl<=il<=jr:
# 答えにカウント
ans+=1
# (区間jの左端)≤(区間iの右端)≤(区間jの右端)
elif jl<=ir<=jr:
# 答えにカウント
ans+=1
# 答えの出力
print(ans)
別解
# 入力の受け取り
N=int(input())
# 区間の格納リスト
section=[]
# N回
for i in range(N):
# 入力の受け取り
t,l,r=map(int, input().split())
# t=1の場合
if t==1:section.append([l,r])
# t=2の場合
elif t==2:section.append([l,r-0.1])
# t=3の場合
elif t==3:section.append([l+0.1,r])
# t=4の場合
else:section.append([l+0.1,r-0.1])
# 答えの格納用変数
ans=0
# i=0~(N-1)まで
for i in range(N):
# j=(i+1)~(N-1)まで
for j in range(i+1,N):
# 区間i,jの右端,左端
il,ir=section[i]
jl,jr=section[j]
# max(区間iの左端,区間jの左端)≤min(区間iの右端,区間jの右端)ならば
# 答えにカウント
if max(il,jl)<=min(ir,jr):ans+=1
# 答えの出力
print(ans)
24 座標圧縮 ABC213 C Dif:481
提出
# 入力の受け取り
H,W,N=map(int, input().split())
# カードの[行番号,列番号]を受け取るリスト
cards=[]
# 行番号だけ受け取るリスト
Gyou=[]
# 列番号だけ受け取るリスト
Retu=[]
# N回
for i in range(N):
# 入力の受け取り
A,B=map(int, input().split())
# カードの[行番号,列番号]を受け取り
cards.append([A,B])
# 行番号を受け取り
Gyou.append(A)
# 列番号を受け取り
Retu.append(B)
# 重複の削除(setにする)
Gyou=set(Gyou)
# リストに直す(setはソートできない)
Gyou=list(Gyou)
# ソートする
Gyou.sort()
# 変換先を記録する連想配列
GyouConvert=dict()
# 重複削除後の行の個数分
for i in range(len(Gyou)):
# もとの行番号→インデックス番号+1と変換できるように記録(小さい方から何番目にあるか？)
GyouConvert[Gyou[i]]=i+1
#列も同じことをする
Retu=set(Retu)
Retu=list(Retu)
Retu.sort()
RetuConvert=dict()
for i in range(len(Retu)):
RetuConvert[Retu[i]]=i+1
# それぞれのカードについて行、列番号を変換して出力
for Gyou,Retu in cards:
# 行番号の変換
AnsGyou=GyouConvert[Gyou]
# 列番号の変換
AnsRetu=RetuConvert[Retu]
# 答えを出力する
print(AnsGyou,AnsRetu)
25 heap ABC234 D Dif:503
提出
# 入力の受け取り
N,K=map(int,input().split())
P=list(map(int,input().split()))
# heapqのインポート
import heapq
# (1)heap queueを用意する
que=[]
# (2)P1~PKをheap queueへ入れる
for i in range(K):
heapq.heappush(que,P[i])
# (3)heap queueの最小値を出力する
print(que[0])
# i=K~(N-1)
for i in range(K,N):
# (4)heap queueから最小値を取り出す
x=heapq.heappop(que)
# (5)(heap queueの最小値)とPiのうち大きい方をheap queueへ戻す
heapq.heappush(que,max(x,P[i]))
# (6)(heap queueの最小値)を出力する
print(que[0])
# (7)次のiへ((4)へ戻る)
26 deque ABC237 D Dif:544
提出
# 入力の受け取り
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)
27 DP1 ABC211 C Dif:559
提出
# 入力の受け取り
S=input()
# 文字数=N
N=len(S)
# Sの0文字目を?にする
S="?"+S
# T=?chokudai(?は0文字目)
T="?chokudai"
# 余りの定義
mod=10**9+7
# (1)表を作る
dp=[[0]*9 for i in range(N+1)]
# (2)すぐにわかるところを埋める
# i=0~N
for i in range(N+1):
# k=0
dp[i][0]=1
# (3)表の小さい方から答えにたどり着くまで埋める
# Sのi文字目までを使う
for i in range(1,N+1):
# chokudaiのk文字目までを作る
for k in range(1,9):
# 1≤i≤N,1≤k≤8,Sのi文字目=chokudaiのk文字目の場合
if S[i]==T[k]:
# dp[i-1][k]：Sの(i-1)文字目までを使ってchokudaiのk文字目を作る場合(Sのi文字目を使わない)
# dp[i-1][k-1]：Sの(i-1)文字目までを使ってchokudaiの(k-1)文字目を作る場合(Sのi文字目を使う)
dp[i][k]=dp[i-1][k]+dp[i-1][k-1]
# 1≤i≤N,1≤k≤8,Sのi文字目≠chokudaiのk文字目の場合
else:
# dp[i-1][k-1]：Sの(i-1)文字目までを使ってchokudaiの(k-1)文字目を作る場合(Sのi文字目を使う)
dp[i][k]=dp[i-1][k]
# 余りを取る
dp[i][k]%=mod
# SのN文字目までを使ってchokudaiの8文字目までを作る方法の数
print(dp[N][8])
28 全探索2 ABC233 C Dif:604
提出
# 入力の受け取り
N,X=list(map(int,input().split()))
# L,aの格納リスト
L=[]
a=[]
# N回
for i in range(N):
# 一旦リストで受け取り
tmp=list(map(int,input().split()))
# リストの0番目=L
L.append(tmp[0])
# リストの1番目~=a
a.append(tmp[1:])
# 全ての掛け算パターンの結果
Pro=[1]
# i=0~(N-1)
for i in range(N):
# 一時的に結果を格納するリスト
tmpPro=[]
# i番目の袋のa全てについて
for ai in a[i]:
# ここまでの全ての掛け算パターンの結果
for p in Pro:
# 掛け算して格納
tmpPro.append(ai*p)
# ProをtmpProで更新
Pro=tmpPro
# 結果がXとなったパターンを数える
ans=Pro.count(X)
# 答えを出力
print(ans)
29 BFS1 ABC204 C Dif:629
提出
# 入力の受け取り
N,M=map(int, input().split())
# 道路の情報を格納するリスト
connect=[[] for i in range(N+1)]
# M回受け取り
for i in range(M):
# 入力の受け取り
A,B=map(int, input().split())
# connect[A]にBを追加
# 都市1から都市2,3,4にいけるならconnect[1]=2,3,4
connect[A].append(B)
# dequeをインポート
from collections import deque
# BFS
# 引数：スタート都市→返り値：スタート都市から行ける都市の数
def BFS(start):
# 行ける都市を数える変数
# スタート都市→スタート都市には必ず行けるから1
count=1
# 訪問済み都市のリスト
# 訪問済みならTrue、未訪問ならFalse
visited=[False]*(N+1)
# スタート都市は訪問済みにする
visited[start]=True
# キューを用意
que=deque()
# キューへスタート都市を追加
que.append(start)
# キューが空になるまで
while 0<len(que):
# 今いる都市
now=que.popleft()
# 今いる都市から行ける都市を順にtoへ
for to in connect[now]:
# もしtoが未訪問なら
if visited[to]==False:
# countにプラス1
count+=1
# toを訪問済みにする
visited[to]=True
# キューへtoを追加
que.append(to)
# 行ける都市の数を返す
return count
# 答えを格納する変数
ans=0
# x=1~N
for x in range(1,N+1):
# xをスタート地点としたときに行ける都市の数を順に足し算
ans+=BFS(x)
# 答えの出力
print(ans)
30 規則性利用 ABC238 C Dif:637
提出
# 余りを定義
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)
31 全探索3 ABC227 C Dif:692
提出
# pypyで提出
# 入力の受け取り
N=int(input())
# 答えのカウント
ans=0
# 初期値
A=1
# A≤(Nの三乗根)⇔A^3≤Nの間
while A**3<=N:
# 初期値
B=A
# B≤√(N/A)⇔A*B^2≤Nの間
while A*B**2<=N:
# ありうるCの個数=(N/AB)の切り捨て-B+1
ans+=int(N/(A*B))-B+1
# 次のBへ
B+=1
# 次のAへ
A+=1
# 答えの出力
print(ans)
32 DFS1 ABC213 D Dif:710
提出
# 再帰回数上限。再帰関数を書くときは必ず最初に書くこと
import sys
sys.setrecursionlimit(10**6)
# 入力受け取り
N=int(input())
# 辺の情報格納
connect=[[] for i in range(N+1)]
# 辺の情報受け取り
for i in range(N-1):
A,B=map(int, input().split())
connect[A].append(B)
connect[B].append(A)
# connect[1]=[2,3,4]ならば1と2,3,4がつながっている、というように確認できる
# 小さい順に回るからソート
for i in range(N+1):
connect[i].sort()
# 答えの格納リスト
ans=[]
# DFS(今いる都市,前にいた都市)
def DFS(now,pre):
# 今いる都市を答えに入れる
ans.append(now)
# to=今いる都市から行ける都市
for to in connect[now]:
# もしtoが前にいた都市と違うなら
if to!=pre:
# 更に先へ探索する
DFS(to,now)
# 戻ってきたら答えへ格納
ans.append(now)
# 最初の都市=1,前にいた都市=-1(前にいた都市がないので存在しない番号)としてスタート
DFS(1,-1)
# 答えの出力
print(*ans)
33 連想配列2 ABC218 D Dif:715
提出
# 入力を受け取り
N=int(input())
# 座標の格納用リスト
points=[]
# defaultdictを用意 初期値は0
from collections import defaultdict
# (x,y)が存在したらp[(x,y)]=1
p=defaultdict(int)
# M行受け取り
for i in range(N):
# x,yを受け取り
x,y=map(int, input().split())
# 座標をpointsへ格納
points.append([x,y])
# p[(x,y)]=1を記録
p[(x,y)]=1
# 答えを格納する変数
ans=0
# p1=0~(N-1)
for p1 in range(N):
# p2=(p1+1)~(N-1)
for p2 in range(p1+1,N):
# p1のx座標,y座標
p1_x,p1_y=points[p1]
# p1のx座標,y座標
p2_x,p2_y=points[p2]
# x座標またはy座標が同じ場合は
if p1_x==p2_x or p1_y==p2_y:
# 次の点へ
continue
# 座標(p1_x,p2_y)と座標(p2_x,p1_y)の点が存在すれば
if p[(p1_x,p2_y)]==1 and p[(p2_x,p1_y)]==1:
# 答えにプラス1
ans+=1
# 二重に数えているので2で割る
ans//=2
# 答えを出力
print(ans)
34 UnionFind1 ATC B
提出
class UnionFind:
def __init__(self,n):
self.n=n
self.parent_size=[-1]*n
def leader(self,a):
if self.parent_size[a]<0: return a
self.parent_size[a]=self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self,a,b):
x,y=self.leader(a),self.leader(b)
if x == y: return
if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y]=x
def same(self,a,b):
return self.leader(a) == self.leader(b)
def size(self,a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result=[[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
# 入力の受け取り
N,Q=map(int,input().split())
# UnionFindを用意
UF=UnionFind(N+1)
# Q回
for i in range(Q):
# 入力の受け取り
P,A,B=map(int,input().split())
# P=0の場合
if P==0:
# A,Bを連結
UF.merge(A,B)
# P=1の場合
else:
# A,Bが連結なら
if UF.same(A,B):
# 「Yes」を出力
print("Yes")
# 連結でないなら
else:
# 「No」を出力
print("No")
35 UnionFind2 ABC231 D Dif:726
提出
class UnionFind:
def __init__(self,n):
self.n=n
self.parent_size=[-1]*n
def leader(self,a):
if self.parent_size[a]<0: return a
self.parent_size[a]=self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self,a,b):
x,y=self.leader(a),self.leader(b)
if x == y: return
if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y]=x
def same(self,a,b):
return self.leader(a) == self.leader(b)
def size(self,a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result=[[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
# 入力の受け取り
N,M=map(int,input().split())
# UnionFind 初期化
UF=UnionFind(N+1)
# 辺の本数をカウント
count=[0]*(N+1)
# M回
for i in range(M):
# 入力の受け取り
A,B=map(int,input().split())
# 辺の本数をカウント
count[A]+=1
count[B]+=1
# 辺の本数が3本以上なら
if 3<=count[A] or 3<=count[B]:
# 「No」を出力
print("No")
# 終了
exit()
# A,Bが連結の場合
if UF.same(A,B)==True:
# 「No」を出力
print("No")
# 終了
exit()
# そうでなければ(連結出ない場合)
else:
# A,Bに辺を張る(連結する)
UF.merge(A,B)
# 「Yes」を出力
print("Yes")
別解
# 再帰回数上限。再帰関数を使うときは必ず最初に書くこと
import sys
sys.setrecursionlimit(10**6)
# 入力の受け取り
N,M=map(int,input().split())
# つながっている頂点の記録
Connect=[[] for i in range(N+1)]
# M回
for i in range(M):
# 入力の受け取り
A,B=map(int,input().split())
# A→B、B→Aへ行ける
Connect[A].append(B)
Connect[B].append(A)
# 辺の本数が3本以上なら
if 3<=len(Connect[A]) or 3<=len(Connect[B]):
# 「No」を出力
print("No")
# 終了
exit()
# まだ訪問済みでない頂点
visited=[False]*(N+1)
# DFS(今いる頂点、直前にいた頂点)
def DFS(Now,Pre):
# 今いる頂点を訪問済みにする
visited[Now]=True
# to=Nowから行ける頂点
for to in Connect[Now]:
# 直前にいた頂点でなければ
if to!=Pre:
# 訪問済みでなければ
if visited[to]==False:
# 次のDFSを開始
DFS(to,Now)
# 訪問済みであれば
# ⇔ループになった
else:
# 「No」を出力
print("No")
# 終了
exit()
# i=1~N
for i in range(1,N+1):
# 訪問済みでなければ
if visited[i]==False:
# DFSを開始
# (直前にいた頂点はないので0にしておく)
DFS(i,0)
# 「Yes」を出力
print("Yes")
36 尺取法1、区間和 ABC229 D Dif:745
提出
# 入力の受け取り
S=input()
K=int(input())
S="?"+S
# Sの長さ
N=len(S)
# 「.」の累積個数
Count=[0]*N
# i=1~(N-1)
for i in range(1,N):
# S[i]=「X」ならば
if S[i]=="X":
# 一つ左と同じ
Count[i]=Count[i-1]
# そうでないなら(S[i]=「.」)
else:
# 一つ左+1
Count[i]=Count[i-1]+1
# 答え
ans=0
# 右
r=1
# l=1~(N-1)
for l in range(1,N):
# r<Nの間
while r<N:
# [左,右]にある「.」の数=Count[r]-Count[l-1]
Period=Count[r]-Count[l-1]
# [左,右]にある「.」の数≤Kならば
# ⇔[左,右]にある「.」を全て「X」に変えられるなら
if Period<=K:
# 右を移動
r+=1
# そうでないなら([左,右]にある「.」を全て「X」に変えられないなら)
else:
# whileを抜ける
break
# [左,右-1]の長さを計算し、今までの答えより大きければ更新
ans=max(ans,r-l)
# 答えの出力
print(ans)
37 BFS2 ABC211 D Dif:755
提出
# 入力の受け取り
N,M=map(int, input().split())
# 道路の情報を格納する変数
connect=[[] for i in range(N+1)]
# 道路の情報を受け取って格納
for i in range(M):
A,B=map(int, input().split())
connect[A].append(B)
connect[B].append(A)
# 余りの定義
mod=10**9+7
# まだ到達していない都市の移動時間(infinity：無限大)
# 大きめの数にする
inf=10**15
# (1)各都市の最短移動時間を記録するリストtimeを作る(初期値は大きな数)
time=[inf]*(N+1)
# 都市①の最短移動時間は「0」
time[1]=0
# (2)各都市にたどり着くまでの経路数を記録するリストcountを作る
count=[0]*(N+1)
# 都市①に行く経路数は「1」
count[1]=1
# (3)キューを用意
from collections import deque
que=deque()
# キューに都市①を入れる
que.append(1)
# (6)(4)~(5)をキューが空になるまで繰り返す
while 0<len(que):
# (4)キューの左端から要素(都市の番号)を取り出す(今いる街)
now=que.popleft()
# (5)今いる都市から行ける都市を確認する
# nowから行ける都市を順にtoへ格納
for to in connect[now]:
# もし行ける都市の移動時間がinfならば(まだ更新されていない)
if time[to]==inf:
# (5-1)「経路数」=「今いる都市の経路数」
count[to]=count[now]
# (5-2)「最短移動時間」=「今いる都市の最短移動時間+1」
time[to]=time[now]+1
# (5-3)キューに追加
que.append(to)
# そうでないなら(移動時間が更新済み)
else:
# 「最短移動時間」=「今いる都市の最短移動時間+1」(最短経路)ならば
if time[to]==time[now]+1:
# (5-4)「経路数」+=「今いる都市の経路数」
count[to]+=count[now]
# 余りを取る
count[to]%=mod
# (7)答えを出力する
# Nが未到達であれば(「最短移動時間」が更新されていなければ)
if time[N]==inf:
# たどり着けないため「0」を出力
print(0)
# そうでないならば
else:
# count[N]を出力
print(count[N])
38 シミュレーション2 ABC243 D Dif:758
提出
# 入力の受け取り
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)
39 DP2 ABC248 C Dif:787
提出
# 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)
40 二分探索2 ABC248 D Dif:793
提出
# 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)
41 尺取法2、エラトステネスの篩 ABC250 D Dif:797
提出
# エラトステネスの篩
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)
42 FenwickTree ACL B
提出
class FenwickTree:
def __init__(self,N):
self.N=N
self.F=[0]*N
def add(self,i,x):
i+=1
while i<=self.N:
self.F[i-1]+=x
i+=i&-i
def sum_r(self,r):
s=0
while 0<r:
s+=self.F[r-1]
r-=r&-r
return s
def sum(self,l,r):
return self.sum_r(r+1)-self.sum_r(l)
def select(self,i):
return self.sum(i,i)
# 入力の受け取り
N,Q=map(int,input().split())
a=list(map(int,input().split()))
# 長さ(N+1)のFenwickTreeを用意
# 初期値は全て0
FT=FenwickTree(N+1)
# i=0~(N-1)
for i in range(N):
# i番目にa[i]を足す
FT.add(i, a[i])
# Q回
for i in range(Q):
# 入力の受け取り
q,a,b=map(int,input().split())
# q=0の場合
if q==0:
# a番目にbを足す(p番目にxを足す)
FT.add(a, b)
# q=1の場合
else:
# a~(b-1)番目の区間和を出力(l~(r-1)番目の区間和を出力)
print(FT.sum(a, b-1))
43 想定解multiset ABC217 D Dif:802
提出
# 提出はpypyで行う
# Fenwick_Tree
class Fenwick_Tree:
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)
# 入力の受け取り
L,Q=map(int, input().split())
# クエリの記録用リスト
query=[]
# カットする場所を予め記録するリスト
cut=[]
# Q回
for i in range(Q):
# 入力の受け取り
c,x=map(int, input().split())
# クエリを記録
query.append([c,x])
# c=1ならば
if c==1:
# cutに場所を記録
cut.append(x)
# cutに「0」を追加
cut.append(0)
# cutに「L」を追加
cut.append(L)
# cutをソート
cut.sort()
# cutの長さをNとする
N=len(cut)
# x(カットする場所)→インデックス番号への変換
cut_index=dict()
# 変換表の作成
for i in range(N):
cut_index[cut[i]]=i
# FenwickTreeの作成
Fenwick=Fenwick_Tree(N)
# 左端(0)に「1」を立てる(1を足す)
Fenwick.add(0,1)
# 右端(Lのインデックス番号)に「1」を立てる(1を足す)
Fenwick.add(N-1,1)
# xがどのインデックス番号の間にあるか確認する二分探索
# 引数：x→返り値：cut[l]<x<cut[r]を満たす最大のl、最小のr
def Nibutan_x(x):
# 左(left)=0
l=0
# 右(right)=N-1
r=N-1
# 1<(右-左)の間
while 1<r-l:
# 中央(center)=(l+r)//2
c=(l+r)//2
# cut[c]<xなら
if cut[c]<x:
# 左=c
l=c
# x<cut[c]なら
else:
# 右端=c
r=c
# 左、右を返す
return l,r
# xより左で1が立っている場所のうち、一番近いものを二分探索
# 引数：x→返り値：Fenwickの区間和[k~x]が1以上となるもののうち、最大のk
def Nibutan_l(x):
# 左(left)=0
l=0
# 右(right)=x
r=x
# 1<(右-左)の間
while 1<r-l:
# 中央(center)=(l+r)//2
c=(l+r)//2
# 区間和[c~x]が1以上
# ⇔区間c~xに「1」が1つ以上立っている
if 1<=Fenwick.sum(c,x):
# 左=中央
l=c
# 区間和[c~x]が1未満(=0)
# ⇔区間c~xに「1」が立っていない
else:
# 右=中央
r=c
# 区間和[r~x]が1ならば
if Fenwick.sum(r,x)==1:
# rを返す
return r
# そうでなければ
else:
# lを返す
return l
# xより右で1が立っている場所のうち、一番近いものを二分探索
# 引数：x→返り値：Fenwickの区間和[x~k]が1以上となるもののうち、最小のk
def Nibutan_r(x):
# 左(left)=x
l=x
# 右(right)=N-1
r=N-1
# 1<(右-左)の間
while 1<r-l:
# 中央(center)=(l+r)//2
c=(l+r)//2
# 区間和[x~c]が1以上
# ⇔区間x~cに「1」が1つ以上立っている
if 1<=Fenwick.sum(x,c):
# 右=中央
r=c
# 区間和[x~c]が1未満(=0)
# ⇔区間x~cに「1」が立っていない
else:
# 左=中央
l=c
# 区間和[x~l]が1ならば
if Fenwick.sum(x,l)==1:
# lを返す
return l
# そうでなければ
else:
# rを返す
return r
# クエリを読み込み
for c,x in query:
# c=1の場合
if c==1:
# cut_index[i]の部分に「1」を立てる(+1する)
Fenwick.add(cut_index[x],1)
# c=2の場合
else:
# xがどのインデックス番号の間にあるか確認する二分探索
l_x,r_x=Nibutan_x(x)
# xより左で「1」が立っている場所のうち、一番近い場所のインデックス番号を二分探索
l_index=Nibutan_l(l_x)
# xより右で「1」が立っている場所のうち、一番近い場所のインデックス番号を二分探索
r_index=Nibutan_r(r_x)
# 右の値-左の値
print(cut[r_index]-cut[l_index])
別解
import bisect
from array import array
# 入力の受け取り
L,Q=map(int,input().split())
# カット位置を記録するarray
# array(型コード,値)
cut=array("i",[0,L])
# Q回
for i in range(Q):
# 入力の受け取り
c,x=map(int,input().split())
# c=1の場合
if c==1:
# xをx以上で最小の要素の次に挿入
bisect.insort(cut,x)
# それ以外(c=2の場合)
else:
# x以上で最小の要素のインデックス番号を取得
index=bisect.bisect(cut,x)
# 長さを出力
print(cut[index]-cut[index-1])
44 DP3 ABC204 D Dif:832
提出
# pypyで提出
# 入力の受け取り
N=int(input())
# Tは先頭に[0]を追加して受け取り
T=[0]+list(map(int, input().split()))
# Tの合計
T_sum=sum(T)
# (1)表を作る
# 『i番目までの数を組み合わせてKを作れるか』
# 例：『3番目までの数を組み合わせて「7」を作れる』→ dp[3][7]=True
dp=[[False]*(T_sum+1) for i in range(N+1)]
# (2)すぐにわかるところを埋める
# 『0番目までの数を組み合わせて「0」を作れる
dp[0][0]=True
# (3)表の小さい方から答えにたどり着くまで埋める
# i=1~N
for i in range(1,N+1):
# K=0~T_sum Kを作れるか確認
for K in range(T_sum+1):
# 『(i-1)番目までの数を組み合わせてKを作れる』(→dp[i-1][K]=True)ならば
if dp[i-1][K]==True:
# 『i番目までの数を組み合わせてKを作れる』(→dp[i][K]=True)
dp[i][K]=True
# 0<=K-T[i] かつ『(i-1)番目までの数を組み合わせてK-T[i]を作れる』ならば(dp[i-1][K-T[i]]=True)
if 0<=K-T[i] and dp[i-1][K-T[i]]==True:
# 『i番目までの数を組み合わせてKを作れる』(→dp[i][K]=True)
dp[i][K]=True
# 答えを格納する変数(初期値はバカでかい数)
ans=10**15
# (4)答えを出力する
# K=0~T_sum
for K in range(T_sum+1):
# 『N番目までの数を組み合わせてKを作れる』ならば
if dp[N][K]==True:
# max(K,T_sum-K)が料理をすべて作るのにかかる時間=答えの候補
# それまでのansより小さければ更新
ans=min(ans,max(K,T_sum-K))
# 答えの出力
print(ans)
45 区間スケジューリング ABC230 D Dif:963
提出
# 入力の受け取り
N,D=map(int,input().split())
# 区間の情報
Section=[]
# N回
for i in range(N):
# 入力の受け取り
L,R=map(int,input().split())
# 情報を格納
Section.append([L,R])
# 右端の列番号を基準にソート
Section.sort(key=lambda x:x[1])
# 最初の壁の右端にパンチを打つ
X=Section[0][1]
# 答え
ans=1
# i=1~(N-1)
for i in range(1,N):
# i番目の壁の左端、右端
Li,Ri=Section[i][0],Section[i][1]
# 最後のパンチでi番目の壁を壊せていなければ
# ⇔最後にパンチした位置+(D-1)<左端
if X+D-1<Li:
# 右端にパンチを打つ
X=Ri
# 回数をカウント
ans+=1
# 答えの出力
print(ans)
46 UnionFind3 ABC218 E Dif:1004
提出
# UnionFind
class UnionFind:
def __init__(self,n):
self.n=n
self.parent_size=[-1]*n
def leader(self,a):
if self.parent_size[a]<0: return a
self.parent_size[a]=self.leader(self.parent_size[a])
return self.parent_size[a]
def merge(self,a,b):
x,y=self.leader(a),self.leader(b)
if x == y: return
if abs(self.parent_size[x])<abs(self.parent_size[y]):x,y=y,x
self.parent_size[x] += self.parent_size[y]
self.parent_size[y]=x
def same(self,a,b):
return self.leader(a) == self.leader(b)
def size(self,a):
return abs(self.parent_size[self.leader(a)])
def groups(self):
result=[[] for _ in range(self.n)]
for i in range(self.n):
result[self.leader(i)].append(i)
return [r for r in result if r != []]
# 入力の受け取り
N,M=map(int, input().split())
# 辺の情報格納用リスト
edge=[]
# M行受け取り
for i in range(M):
A,B,C=map(int, input().split())
# 後のソートのためC先頭で格納
edge.append([C,A,B])
# (1)辺をCの小さい順に並び替える
edge.sort()
# 報酬
ans=0
# (2)すべての辺を取り除き、報酬と罰金の合計を計算する
for i in range(M):
ans+=edge[i][0]
# UnionFindを初期化(頂点数(N+1)個(0~N))
UF=UnionFind(N+1)
# edgeの各要素について
for C,A,B in edge:
# (3)Cが小さい方から辺を確認していく
# ・Cが0以下なら
if C<=0:
# 頂点Ai,Biを連結し、罰金|C|を報酬にプラスする(Cがマイナスの辺は取り除く理由がない)
# 連結
UF.merge(A,B)
# 罰金=|C|をプラス
ans+=abs(C)
# そうでないならば(cが0より大きいなら)
else:
# ・頂点Ai,Biが非連結なら
if UF.same(A,B)==False:
# 頂点Ai,Biを連結し、報酬からCを引く
# 報酬からCを引く
ans-=C
# A,Bを連結
UF.merge(A,B)
# 答えを出力
print(ans)
47 DFS2 ABC239 E Dif:1084
提出
# 入力の受け取り
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])
48 DP4 ABC219 D Dif:1085
提出
# pypyで提出
# 入力の受け取り
N=int(input())
X,Y=map(int, input().split())
# バカでかい数を作っておく(infinity)
inf=10**15
# (1)表を作る
# dp[i][x][y]：「i種類目までの弁当を使い、x個のたこ焼きとy個のたい焼きを手に入れるために必要な弁当の最小個数」
# 初期値はinf
dp=[[[inf]*(Y+1) for i in range(X+1)] for j in range(N+1)]
# (2)すぐにわかるところを埋める
# 「0種類目までの弁当を使い、0個のたこ焼きと0個のたい焼きを手に入れる最小個数」=0
dp[0][0][0]=0
# (3)表の小さい方から答えにたどり着くまで埋める
# i=1~N
for i in range(1,N+1):
# 入力の受け取り
A,B=map(int, input().split())
# たこ焼きの数：x=0~X
for x in range(X+1):
# たい焼きの数：y=0~Y
for y in range(Y+1):
# 「買わない場合」(すでに埋まっている数のほうが小さい場合は更新しない)
dp[i][x][y]=min(dp[i][x][y],dp[i-1][x][y])
# 「買う場合」(すでに埋まっている数のほうが小さい場合は更新しない)
# たこ焼きの数がX以上→Xへ変換
x_plus=min(x+A,X)
# たい焼きの数がY以上→Yへ変換
y_plus=min(y+B,Y)
dp[i][x_plus][y_plus]=min(dp[i][x_plus][y_plus],dp[i-1][x][y]+1)
# 答え：「N種類目までの弁当を使い、X個のたこ焼きとY個のたい焼きを手に入れるために必要な弁当の最小個数」
ans=dp[N][X][Y]
# (4)答えを出力する
# もし答えがinfだったら(X個以上のたこ焼き、Y個以上のたい焼きを手に入れられない場合)
if ans==inf:
# -1を出力
print(-1)
# そうでないならば
else:
# 答えを出力
print(ans)
49 二分探索3 ABC246 D Dif:1148
提出
# 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)
50 ワーシャルフロイド法 ABC208 D Dif:1190
提出
# pypyで提出
# 入力の受け取り
N,M=map(int, input().split())
# 到達不可能時間(大きすぎるとTLEするので注意)
inf=10**15
# 時間表
time=[[inf]*(N+1) for i in range(N+1)]
# i=1~Nまで
for i in range(1,N+1):
# 都市①→都市①,都市②→都市②、...を時間0へ
time[i][i]=0
# M回
for i in range(M):
# 入力の受け取り
A,B,C=map(int, input().split())
# 時間表の更新
time[A][B]=C
# 答えを格納する変数
ans=0
# k=1~N
for k in range(1,N+1):
# 新しい時間表
new_time=[[0]*(N+1) for i in range(N+1)]
# スタート都市：1~N
for start in range(1,N+1):
# ゴール都市：1~N
for goal in range(1,N+1):
# 新しい時間表を更新
# 「(K-1)以下の都市を通って良いパターン」と「都市kを経由するパターン」の小さい方
new_time[start][goal]=min(time[start][goal],time[start][k]+time[k][goal])
# スタート都市：1~N
for start in range(1,N+1):
# ゴール都市：1~N
for goal in range(1,N+1):
# 新しい時間表でスタート→ゴールが到達不能でなければ
if new_time[start][goal]!=inf:
# 新しい時間を答えにプラス
ans+=new_time[start][goal]
# 古い時間表を新しい時間表へ更新
time=new_time
# 答えの出力
print(ans)
クラス解説：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)