トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228) A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。
その他のABC解説、動画などは以下です。
トヨタシステムズ様について
求人情報は以下のページにあるので、興味がある方はご覧ください。
動画
A - On and Off
まずS<Tの場合と、T<Sの場合に分けて考えましょう。
・S<T
S≤X<Tならば「Yes」
そうでないならば「No」
を出力します。
T<S
X<TまたはS≤Xならば「Yes」
そうでないならば「No」
を出力します。
これらの条件をifを使って書き、条件分岐すればOKです。
「Yes」「No」は文字列なので出力の際、"Yes","No"とダブルクオーテーションをつけてください。
入力の受け取り、出力がわからない方は以下の記事を参考にしてください。
【提出】
# 入力の受け取り
S,T,X=map(int,input().split())
# S<Tならば
if S<T:
# S<=X<Tなら
if S<=X<T:
# 「Yes」を出力
print("Yes")
# そうでなければ
else:
# 「No」を出力
print("No")
# そうでなければ(T<Sならば)
else:
# X<TまたはS<=Xならば
if X<T or S<=X:
# 「Yes」を出力
print("Yes")
# そうでなければ
else:
# 「No」を出力
print("No")
B - Takahashi's Secret
次に誰が秘密を聞くか、順番に確認しながら、すでに秘密を知っている人を管理します。
秘密を知っている人を管理するリストをknowとし、x番目の友達が知っていればknow[x]=True、まだ聞いていなければknow[x]=FalseとすればOKです。
次に秘密を聞く人がすでに秘密を知っていれば確認を終了し、「秘密を聞いた人数」⇔「know[x]=Trueとなっている人数」をカウントします。
【提出】
# 入力の受け取り
N,X=map(int,input().split())
A=[0]+list(map(int,input().split()))
# 秘密を知る友達
# 知っていたらTrue、知らなければFalse
know=[False]*(N+1)
# 次に秘密を聞く友達
next_friend=X
# 次に秘密を聞く友達がまだ秘密を知らないなら
while know[next_friend]==False:
# 秘密を聞く
know[next_friend]=True
# 次に秘密を聞く友達を更新
next_friend=A[next_friend]
# 答え
ans=0
# i=!~Nまで
for i in range(1,N+1):
# 秘密をしっていれば
if know[i]==True:
# 答えにカウント
ans+=1
# 答えを出力
print(ans)
C - Final Day
K位以内に入るために必要な最低点数を考えましょう。
4日目のテストで自分以外の生徒全員が0点を取った場合、K番以内に入るための点数が一番低くなります。
つまり各生徒3日間の合計点を大きい順にソートしたときのK番目の点数が、K位以内に入るための最低点数となります。
あとは各生徒について、4日目のテストで300点を取ったとして最低点数を上回れるか？を確認すればOKです。
【提出】
# 入力の受け取り
N,K=map(int,input().split())
# 3日目までの合計得点を格納する
point=[]
# N回
for i in range(N):
# 点数を受け取り
Pi1,Pi2,Pi3=map(int,input().split())
# 合計点を格納
point.append(Pi1+Pi2+Pi3)
# 得点を大きい順でソート
point_sorted=sorted(point,reverse=True)
# K位以内に入るための最低得点
# 受け取りが0インデックスなので[K-1]となることに注意
Lowest_Point=point_sorted[K-1]
# i=1~(N-1)まで
for i in range(N):
# 最終日に満点を取った場合(+300)、最低得点を上回れば
if Lowest_Point<=point[i]+300:
# 「Yes」を出力
print("Yes")
# そうでなければ(満点を取っても最低得点より小さい)
else:
# 「No」を出力
print("No")
D - Linear Probing
問題文の指示そのままに操作を行うと「hの値を1増やすことを繰り返す」のところでTLEします。
t=1のクエリで、xi≤h かつ A[h%N]≠-1 となっている最小のhを高速で探す必要があります。
例えばいくつかのクエリを処理して以下のような状況になっているとしましょう。
「Fen」はどこが更新されたかを確認するためのリストです。(後に説明しますがFenwick-TreeのFenです)
Fen[p]=1⇔A[p]がまだ更新されていない⇔A[p]=-1
Fen[p]=0⇔A[p]が更新されている⇔A[p]≠-1
を表しています。
このタイミングで
t：1
x：4
のクエリが来たとしましょう。
1 h=4とする
2 A[h]=4なのでhの値を1増やす。
3 A[h]=5なのでhの値を1増やす。
...
という処理にすると間に合いません。そこでFenを見ます。
要するに「x=4≤hを満たすhのうち、Fen[h％N]=1となっている最小のh」がわかれば、A[h]=xと更新すれば良いわけです。
この場合だと
Fen[4]=0
Fen[5]=0
Fen[6]=0
Fen[7]=1
なのでh=7で、A[7]=4とすればよいことがわかります。
ではこの「x≤hを満たすhのうち、Fen[h%N]=1となっている最小のh」をどのように高速で探すか考えます。
これには
・区間和(Fenwick-Tree)
・二分探索
を使います。
・区間和(Fenwick-Tree)
例えばFen[4~9]の区間和が1以上だったらその区間に少なくとも一つは「1」があるはずです。
厳密に言うと
「1≤Fen[4~9]の区間和」⇔「4≤p≤9についてFen[p]=1となるpが少なくとも一つ存在する」
ということです。
逆にFen[4~9]の区間和が0だったらその区間に「1」は一つもありません。
このように区間和を使うとどの区間に「1」があるのかがわかります。
区間和はFenwick-Treeを使えば高速で更新、計算ができます。
Fenwick-Treeは数列の要素への加算、区間和計算を高速で行えるデータ構造です。
・要素の加算：O(log(N))
・区間和計算：O(log(N))
FenwickTreeについては以下の記事でとてもわかり易くまとめている方がいらっしゃるので興味があれば読んでください。
ただし実装については理解できなくても、以下のclassをコピペして使えれば問題ありません。
灰色～茶色コーダーの方はFenwick-Treeの考え方を「ふ～んなるほどね～」くらいで理解しておけば十分です。
# Fenwick_Tree
class Fenwick_Tree:
# 初期化(要素数n)
def __init__(self,n):
self._n=n
self.data=[0]*n
# p番目の要素にxを追加
def add(self,p,x):
p+=1
while p<=self._n:
self.data[p-1] +=x
p+=p&-p
# [0,r)の区間和を計算
def _sum(self,r):
s=0
while 0<r:
s+=self.data[r-1]
r-=r&-r
return s
# [l,r]の区間和を計算
def sum(self,l,r):
r+=1
return self._sum(r)-self._sum(l)
# p番目の要素を出力
def select(self,p):
return self.sum(p,p)
【機能】
・初期化(初期値は全て0)【O(N)】：変数名=Fenwick_Tree(要素の長さ)
・加算【O(logN)】：変数名.add(インデックス番号,加算する数)
・区間和計算【O(logN)】：変数名.sum(左インデックス番号,右インデックス番号)
・値の参照【O(logN)】：変数名.select(インデックス番号)
【使用例】
# 初期化(初期値は全て0)【O(N)】：変数名=Fenwick_Tree(要素の長さ)
Fenwick=Fenwick_Tree(100)
# 加算【O(logN)】：変数名.add(インデックス番号,加算する数)
Fenwick.add(10,5)
Fenwick.add(20,10)
Fenwick.add(30,20)
# 区間和計算【O(logN)】：変数名.sum(左インデックス番号,右インデックス番号)
x=Fenwick.sum(10,25)
# 値の参照【O(logN)】：変数名.select(インデックス番号)
print(Fenwick.select(10))
これで区間の中に「1」があるかどうか確認できることはわかりました。
・二分探索
次に二分探索を使い、区間を絞っていきます。
クエリ
t：1
x：4
であれば、まず
左端：4
右端：1048575(2^20-1)
とします。
左端から中間地点である(4+1048575)/2=524289までに「1」があるか確認します。即ち、
区間Fen[4~524289]に「1」があるか=区間和Fen[4~524289]が1以上か
を確認します。
もし、この区間に「1」がある=「区間和が1以上」だった場合は
左端：4
右端：524289(=中間地点)
と更新します。
※逆に「1」がない=「区間和が0」だった場合は左端：524289 右端：1048575(2^20-1) となります。
次も同じように左端から中間地点である(4+524289)/2=262146までに「1」あるかを確認します。即ち、
区間Fen[4~262146]に「1」があるか=区間和が1以上か
を確認します。
もし、この区間に「1」がある=「区間和が1以上」だった場合は
左端：4
右端：262146
と更新します。
これを繰り返していけば最終的に
左端：6
右端：7
となります。
あとは右端と左端のFenの値を順に確認します。
Fen[6]=1か？→Fen[6]=0
Fen[7]=1か？→Fen[7]=1
ゆえに「x≤hを満たすhのうち、Fen[h%N]=1となっている最小のh」は「h=7」であることがわかります。
少々厄介なのはx~(2^20-1)=1048575のうちに「1」が一つもない場合です。
要するにFen[x]～Fen[N-1]まで全て「0」の場合です。
この場合、h=1048576,1048577,1048578,...,1048576+(x-1)のmod N、すなわちh=0,1,2,...,x-1のうちからFen[h]=1となるhを探すことになります。
この場合は
左端：0
右端：x-1
として同様に二分探索をしていきます。
hが見つかったら
A[h]=x と更新
Fen[h]=0 と更新(-1を加算)
という処理を行います。
pythonでは間に合わないのでpypyで提出します。
【提出】
# pypyで提出
# Fenwick_Tree
class Fenwick_Tree:
# 初期化(要素数n)
def __init__(self,n):
self._n=n
self.data=[0]*n
# p番目の要素にxを追加
def add(self,p,x):
p+=1
while p<=self._n:
self.data[p-1] +=x
p+=p&-p
# [0,r)の区間和を計算
def _sum(self,r):
s=0
while 0<r:
s+=self.data[r-1]
r-=r&-r
return s
# [l,r]の区間和を計算
def sum(self,l,r):
r+=1
return self._sum(r)-self._sum(l)
# p番目の要素を出力
def select(self,p):
return self.sum(p,p)
# 入力の受け取り
Q=int(input())
# Nの定義
N=2**20
# Aを作る
A=[-1]*N
# FenwickTreeを作る
Fen=Fenwick_Tree(N)
# Fen[p]=1ならば更新されていない(A[p]=-1)
# Fen[p]=0ならば更新されている(A[p]≠-1)
# 最初は全て1にする
for i in range(N):
Fen.add(i, 1)
# 二分探索
def Nibutan(x):
# 左端=x
left=x
# 右端=N-1
right=N-1
# 1<右端-左端 の間
while 1<right-left:
# 真ん中
center=(left+right)//2
# 区間Fen[x~真ん中]に「1」があれば=区間和が1以上であれば
if 1<=Fen.sum(x,center):
# 右端を更新
right=center
# そうでなければ
# 区間Fen[x~真ん中]に「1」がなければ=区間和が0であれば
else:
# 左端を更新
left=center
# Fen[左端]が1だったら
if Fen.select(left)==1:
# 左端を返す
return left
# Fen[右端]が1だったら
elif Fen.select(right)==1:
# 右端を返す
return right
# Fen[x]～Fen[N-1]まで全て「0」の場合
# 左端=0
left=0
# 右端=x-1
right=x-1
# 1<右端-左端 の間
while 1<right-left:
# 真ん中
center=(left+right)//2
# 区間Fen[0~真ん中]に「1」があれば=区間和が1以上であれば
if 1<=Fen.sum(0,center):
# 右端を更新
right=center
# そうでなければ
# 区間Fen[x~真ん中]に「1」がなければ=区間和が0であれば
else:
# 左端を更新
left=center
# Fen[左端]が1だったら
if Fen.select(left)==1:
# 左端を返す
return left
# Fen[右端]が1だったら
elif Fen.select(right)==1:
# 右端を返す
return right
# Q回
for i in range(Q):
# 入力を受け取る
t,x=map(int,input().split())
# t=1の場合
if t==1:
# 「x≤hを満たすhのうち、Fen[h%N]=1となっている最小のh」
h=Nibutan(x%N)
# A[h]を更新
A[h]=x
# 更新された(A[h]≠-1となった)からFen[h]=1→0にする
Fen.add(h,-1)
# t=2の場合
else:
# 出力
print(A[x%N])
【広告】
『AtCoder 凡人が『緑』になるための精選50問詳細解説』
AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
1～24問目まではサンプルとして無料公開しています
『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』
ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。
サンプルを5問分公開しています
Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。
値段：300円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
『Excelでリバーシを作ろう!! マクロ、VBAを1から学ぶ』
Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！ 丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)
サンプルとして「準備」～「三目並べ」を無料公開しています。
【kindle】
【booth(pdf】