ABC226 C Dif:539 『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説』サンプル

この記事は **『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の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！

https://qiita.com/sano192/items/54accd04df62242b70f0

https://atcoder.jp/contests/abc226/tasks/abc226_c

**【キーワード】**
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

まず技の関係をグラフにする。習得が必要な技に向かって矢印を引く。
技③を習得するのに技②の習得が必要
技④を習得するのに技①,②の習得が必要
技⑤を習得するのに技④の習得が必要

![ABC226_C_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/700383/f77a4231-7392-e49f-fb15-df8a5e03ca74.png)

最終的には技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)を用意する。

```python:
connect=[[] for i in range(N+1)]
```

ここに進める頂点を記録していく。

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

「使用例」

```python:
# インポート：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については私が作った動画があるので、そちらも是非参考にしてほしい。

<iframe width="560" height="315" src="https://www.youtube.com/embed/WyJvs9hL9Yc" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

**\<進める頂点の確認>**
connectに行ける都市の情報を格納している。
キューから取り出した頂点(now)から進める頂点(to)を順に処理する場合は以下のように書く。

```python:
for to in connect[now]:
```

以下のように書いても同じ意味になる。

```python:
for i in len(connect[now]):
    to=connect[now][i]
```

**【提出】**

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