この記事は 『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
【サンプル一覧】
ABC228 A：https://qiita.com/sano192/private/f8f09ea769f2414a5733
ABC249 B：https://qiita.com/sano192/private/daf74d7c31bc698d33ce
ABC226 C：https://qiita.com/sano192/private/3aa26373ca6cfcb3ef0f
ABC246 D：https://qiita.com/sano192/private/a22aadde99945bfb01a8
「ものすごく丁寧でわかりやすいABC解説」シリーズをベースに【キーワード】【どう考える？】【別解】を追加し、【解説】と【実装のコツ】を分けることでよりわかりやすく、具体例や図もより豊富に全ての問題の解説を書き直しました！
さらにQiitaでは公開していないARC129～139の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！
【キーワード】
BFS(幅優先探索)
【どう考える？】
操作を逆順にして考えるというテクニックがある。本問の場合は技Nから遡ってどの技が必要かを考える。例えば技⑤を習得するのに技④が必要なら、更に技④を習得するのに必要な技を確認して……という要領で必要な技を確認できる。
これをグラフの関係として考え、BFSで頂点Nから到達可能な頂点を全て確認すれば終わり。
【解説】
各技を習得するのに必要な技をグラフで表し、頂点Nから到達可能な頂点を確認して必要な時間を計算する。到達可能な頂点の確認にはBFS(幅優先探索)を使う。
～例～
N：5
T1 K1 ：3 0
T2 K2 ：1 0
T3 K3 A(3,1)：6 1 2
T4 K4 A(4,1) A(4,2)：7 2 1 2
T5 K5 A(5,1)：5 1 4
まず技の関係をグラフにする。習得が必要な技に向かって矢印を引く。
技③を習得するのに技②の習得が必要
技④を習得するのに技①,②の習得が必要
技⑤を習得するのに技④の習得が必要
最終的には技N=技⑤を習得するわけだから、グラフで頂点⑤から到達可能な頂点の技は全て習得する必要がある。
頂点Nから到達可能な頂点を確認するためにBFS(幅優先探索)を使う。
「BFS(幅優先探索)」
Breadth First Searchの略。
グラフや木構造を探索するためのアルゴリズムの一つで、探索を開始する頂点から近い順に探索する方法。
手順は以下。
(1)キューを用意し、Nを入れる。
(2)「キュー」の左端から頂点番号を取り出し、「習得必要」にする
(3)取り出した頂点番号から到達可能な頂点を確認し、「習得必要」になっていなければ「キュー」に追加する
(4)(2)~(3)をキューが空になるまで繰り返す
※キューはリストのようなもの。詳細は【実装のコツ】<deque>を参照。
(1)キューを用意し、Nを入れる。
「キュー」へN=⑤を入れる。
キュー：⑤
(2)「キュー」の左端から頂点番号を取り出し、「習得必要」にする
キュー：⑤
「キュー」の左端から⑤を取り出す。取り出した頂点は「キュー」からなくなる。
⑤は「習得必要」にする。
習得必要：⑤
(3)取り出した頂点番号から到達可能な頂点を確認し、「習得必要」になっていなければ「キュー」に追加する
頂点⑤から到達可能なのは頂点④のみ。頂点④は「習得必要」に入っていないので「キュー」に追加する。
キュー：④
(4)(2)~(3)をキューが空になるまで繰り返す
まだ「キュー」は空になっていないので続行。
(2)「キュー」の左端から頂点番号を取り出し、「習得必要」にする
キュー：④
「キュー」の左端から④を取り出し、「習得必要」にする。
習得必要：④ ⑤
(3)取り出した頂点番号から到達可能な頂点を確認し、「習得必要」になっていなければ「キュー」に追加する
頂点④から到達可能な頂点は①,②。それぞれをキューに追加する。
キュー：① ②
(4)(2)~(3)をキューが空になるまで繰り返す
まだ「キュー」は空になっていないので続行。
(2)「キュー」の左端から頂点番号を取り出し、「習得必要」にする
キュー：① ②
「キュー」の左端から①を取り出し、「習得必要」にする。
習得必要：① ④ ⑤
(3)取り出した頂点番号から到達可能な頂点を確認し、「習得必要」になっていなければ「キュー」に追加する
頂点①から到達可能な頂点はないのでなにもしない。
キュー：②
(4)(2)~(3)をキューが空になるまで繰り返す
まだ「キュー」は空になっていないので続行。
(2)「キュー」の左端から頂点番号を取り出し、「習得必要」にする
キュー：②
「キュー」の左端から②を取り出し、「習得必要」にする。
習得必要：① ② ④ ⑤
(3)取り出した頂点番号から到達可能な頂点を確認し、「習得必要」になっていなければ「キュー」に追加する
頂点①から到達可能な頂点はないのでなにもしない。
キュー：(空)
(4)(2)~(3)をキューが空になるまで繰り返す
ここで「キュー」が空になったのでBFSの処理は終了。
あとは「習得必要」になっている技の習得時間を全て足す。
技①+技②+技④+技⑤
=3+1+7+5
=16
答えは「16」となる。
【実装のコツ】
<1インデックスで受け取り>
Tをそのまま受け取るとT1=T[0],T2=A[1]と番号がずれて少々面倒。
受け取りの際に0番目をT[0]=0など、なにか適当なものを埋めることで番号をずらすのがよい。
<複数要素の受け取り>
T,K,Aは一行で入力される。
一旦リストで受け取り、0番目の要素がT、1番目の要素がK、2~(K+1)番目の要素がAと割り振りを行えば良い。
<進める頂点の記録>
頂点iから頂点A(i,1),A(i,2),A(i,3),...へ進めると記録しなければならない。
まず二次元配列(connect)を用意する。
connect=[[] for i in range(N+1)]
ここに進める頂点を記録していく。
for x in range(2,K+2):
connect[i].append(TKA[x])
例えば頂点⑤から頂点①,②へ進めるという場合は
connect[5]=[1,2]となる
<deque>
dequeはリストのようなものだが、左端から要素を取り出す操作がO(1)でできる。
※リストを使ってしまうとこの操作がO(N)かかるのでTLEする。
dequeはライブラリcollectionsからインポートして使う。
「使い方」
・インポート：from collections import deque
・作成：変数名=deque()
・先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
・末尾(右端)に要素追加【O(1)】：変数名.append(要素)
・先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
・末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
「使用例」
# インポート：from collections import deque
from collections import deque
# 作成：変数名=deque()
que=deque()
# 先頭(左端)に要素追加【O(1)】：変数名.appendleft(要素)
que.appendleft(1)
# 末尾(右端)に要素追加【O(1)】：変数名.append(要素)
que.append(3)
# 先頭(左端)から要素を取り出して削除【O(1)】：変数名.popleft()
x=que.popleft()
# 末尾(右端)から要素を取り出して削除【O(1)】：変数名.pop()
y=que.pop
<BFS>
BFSはBreadth First Search(幅優先探索)の意味。グラフの頂点を順に探索するアルゴリズムの一つ。
今回は到達可能な頂点の確認のために使う。
手順は以下。
(1)各頂点から進める頂点のリスト(connect)を作る
(2)「習得必要」技のリスト(learn)を作る。最初は全てFalseにしておき、習得必要な場合はTrueにする。例えば技⑤が習得必要ならlearn[5]=Trueとなる。
(3)キューを用意し、Nを入れる
(4)キューの左端から要素を取り出し、「習得必要」にする
(5)取り出した頂点番号から到達可能な頂点を確認する
・「習得必要」になっていなければ
キューに追加する
(6)(4)～(5)をキューが空になるまで繰り返す
(7)learnがTrueになっている要素の時間を合計して出力する
BFSについては私が作った動画があるので、そちらも是非参考にしてほしい。
<進める頂点の確認>
connectに行ける都市の情報を格納している。
キューから取り出した頂点(now)から進める頂点(to)を順に処理する場合は以下のように書く。
for to in connect[now]:
以下のように書いても同じ意味になる。
for i in len(connect[now]):
to=connect[now][i]
【提出】
# 入力の受け取り
N=int(input())
# (1)各頂点から進める頂点のリスト(connect)を作る
connect=[[] for i in range(N+1)]
# Tの記録(0番目を埋めておく)
T=[0]
# i=1~N
for i in range(1,N+1):
# リストで受け取り
TKA=list(map(int,input().split()))
# 0番目の要素がT
T.append(TKA[0])
# 1番目の要素がK
K=TKA[1]
# x=2~(K+1)
for x in range(2,K+2):
# i→TKA[x]へ進める
connect[i].append(TKA[x])
# (2)「習得必要」技のリスト(learn)を作る
# 最初は全てFalseにしておき、習得必要な場合はTrueにする。
# 例えば技⑤が習得必要ならlearn[5]=Trueとなる。
learn=[False]*(N+1)
# (3)キューを用意し、Nを入れる
# キューを用意
from collections import deque
que=deque()
# キューにNを追加
que.append(N)
# (6)(4)～(5)をキューが空になるまで繰り返す
# ⇔キューの長さが0でなければ
while 0**\<len(que):**
# (4)キューの左端から要素を取り出し、「習得必要」にする
now=que.popleft()
# Nは習得必要⇔learn[N]=True
learn[now]=True
# (5)取り出した頂点番号から到達可能な頂点を確認する
# to=nowから進める頂点
for to in connect[now]:
# 「習得必要」になっていなければ
# ⇔learn[to]がFalseならば
if learn[to]==False:
# キューに追加する
que.append(to)
# 答え
ans=0
# (7)learnがTrueになっている要素の時間を合計して出力する
# 1~Nまで
for i in range(1,N+1):
# 習得必要なら
if learn[i]==True:
# 答えにT[i]を追加
ans+=T[i]
# 答えを出力
print(ans)