目指せ水色コーダー！！！！！！
ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)
AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。
こちらの記事の初中級者が解くべき過去問精選 100 問
をPythonで解いていきます！
@e869120さんに感謝！！！！！！
###過去記事リンク
全探索：全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
全探索：工夫して通り数を減らす全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】
全探索：ビット全探索
[【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】]
(https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f)
全探索：順列全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part4/22】
二分探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part5/22】
深さ優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】
幅優先探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part7/22】
#「Part6」〜深さ優先探索(DFS)編〜
以下の4問を解いていきます！
#####深さ優先探索
24 ALDS_11_B - 深さ優先探索 基本問題です。
25 AOJ 1160 - 島はいくつある？ グラフの連結成分数は、深さ優先探索で計算できます。
26 AtCoder Beginner Contest 138 D - Ki 木構造の問題の多くは、深さ優先探索を使います。
27 JOI 2009 予選 4 - 薄氷渡り 深さ優先探索は、木構造だけではありません、ということを教えてくれる問題です。再帰関数を使って解けます。
#DFSの前提知識
・以下の3点を前提として、記事を書いていきます！
①スタックとキューについて
まずはけんちょんさんの記事
スタックとキューを極める！ 〜 考え方と使い所を特集 〜
を読んで、スタックとキューについて雰囲気理解する！
②DFSとグラフについて
またまたけんちょんさんの記事
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【前編】
DFS (深さ優先探索) 超入門！ 〜 グラフ・アルゴリズムの世界への入口 〜【後編】
を読んで、DFSとグラフについて雰囲気理解する！
③あとは、PythonでのDFSの具体的な実装方法
として、
以下のサイトがわかりやすかったので、この2つのサイト
◆ふつうのグラフまたは木の場合
Pythonでアルゴリズム（深さ優先探索、dfs）
◆グリッドグラフの場合
Pythonで深さ優先探索(DFS)を実装してみる-ATC001
をじっくり読んでDFSとグラフについて深く理解する！
①②③の前提があれば、あとは実際に手を動かせば身につきます！！！
※補足1
DFSは再帰VerとスタックVerの2つの実装方法がありますが、
この記事ではスタックVerの実装に統一します！！！
(BFSに応用が効きやすい？+速度も早い？+スタックオーバーフローを起こさない？ため)
※補足2
今回(Part6)の記事から、入力を
input()→sys.stdin.readline().rstrip()
に変えています！
【Python】競プロテンプレ【AtCoder】
テンプレ用の記事も作ったので、よかったら使ってください〜
#24 ALDS_11_B - 深さ優先探索
典型的なグラフ問題！
graph = {i:collections.deque() for i in range(1,N+1)}
または、
graph = {i:[] for i in range(1,N+1)}
これがグラフのテンプレ！
DFSの実装初めてだったけど、
上のサイトの通り実装してみるとなんとか実装できた！
コードは長いけど、難易度はたいしたことない！！！
ポイントは、この2行！！！
seen[j] = 1
stack.append(j)
seen[g_NO] = 1
stack.append(g_NO)
〜覚え方〜
①家政婦は見た！（ドラマ）ので、
seenを0(False)→1(True)にする！
②家政婦は見たら、ストックに入れます！！！
（家政婦がゴミを見たので、ゴミ箱に入れるイメージ！！！）
このイメージが頭にあれば、実装の時に脳死でコードが書ける！
import collections,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n = I()
ukv = [LI() for _ in range(n)]
graph = {i:collections.deque() for i in range(1,n+1)} #1_indexed
for x in ukv:
u,k,*v = x
for y in v:
graph[u].append(y)
seen = [0]*(n+1) #1_indexed
stack = []
time = 0
seentime = [0]*(n+1) #1_indexed
donetime = [0]*(n+1) #1_indexed
def dfs(j):
global time
seen[j] = 1
stack.append(j)
time += 1
seentime[j] = time
while stack:
s = stack[-1]
if not graph[s]:
stack.pop()
time += 1
donetime[s] = time
continue
g_NO = graph[s].popleft()
if seen[g_NO]:
continue
seen[g_NO] = 1
stack.append(g_NO)
time += 1
seentime[g_NO] = time
for j in range(1,n+1):
if seen[j]:
continue
dfs(j)
for k,a,b in zip(range(1,n+1),seentime[1:],donetime[1:]):
print(k,a,b)
def dfs()なんて書く必要ないけど、DFSの記述とわかりやすいようにdefにしてみた！
また、グラフ問題は
「0」からではなく「1」から始まることがほとんどだと思うので
1_indexedでコード全体を統一！
globalも初めて使ってみたけどなるほど！って感じ！
あとコードを書いていて意識したことは、
continueをできるだけ使って、条件以下のコードを走らせないようにして可読性をあげました！
DFSは特にネストが深くなりがち！（＝複雑になりがち＝バグがうまれやすくなる！）
※過去記事参照
【リーダブルコード】内容を5つ抜粋！【競技プログラミング】
家政婦は見た！（2回目）
#25 AOJ 1160 - 島はいくつある？
典型的なグリッドグラフ問題！
ふつうのグラフの問題と考え方は同じ！
上のサイトを参考にしたが、案外スラスラかけた！
家政婦は見た！（3回目）
import collections,itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
while 1:
w,h = LI()
if w==h==0:
break
ans = 0
c = [LI() for _ in range(h)]
seen = [[0]*w for _ in range(h)]
stack = []
dhdw = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
def dfs(H,W):
seen[H][W] = 1
stack.append([H,W])
while stack:
sh,sw = stack.pop()
for dh,dw in dhdw:
nh,nw = sh+dh,sw+dw
if not(0<=nh<=h-1) or not(0<=nw<=w-1) or seen[nh][nw] or c[nh][nw]==0:
continue
seen[nh][nw] = 1
stack.append([nh,nw])
for H,W in itertools.product(range(h),range(w)):
if seen[H][W] or c[H][W]==0:
continue
ans += 1
dfs(H,W)
print(ans)
#26 AtCoder Beginner Contest 138 D - Ki
Difficulty:923
初見で解けませんでした！！！
計算量でつまずき、根の考え方でもつまずいた！
だけど、次からは似た問題きても解ける**「木」**がする！！！
ポイントはこの2点！
- 木は無向グラフとして考える
- 問題文よりこの木全体の根は頂点1
根より下にある頂点は全て、基準の根のポイントが追加されていく感じ〜
ACにならなかった人はこちらの記事も参考に！！！
AtCoder Beginner Contest 138 D - Ki のテストケースがコンテスト後に増えている件について (修正版)
家政婦は見た！（4回目）
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_indexed
graph = {i:collections.deque() for i in range(1,N+1)} #1_indexed
for a,b in ab:
graph[a].append(b)
graph[b].append(a)
for p,x in px:
ans[p] += x
seen = [0]*(N+1) #1_indexed
stack = []
def dfs():
seen[1] = 1
stack.append(1)
while stack:
s = stack.pop()
if not graph[s]:
continue
for j in range(len(graph[s])):
g_NO = graph[s].popleft()
if seen[g_NO]:
continue
seen[g_NO] = 1
stack.append(g_NO)
ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
ちなみに、
冒頭の補足2で記載した
今回(Part6)の記事から、入力を
input()→sys.stdin.readline().rstrip()
に変えています！
これの原因はこの問題ですw
TLEで苦戦していてところ、できる人のコード見てたら、
sys.stdin.readline()
使ってるなぁ・・・
一応使ってみるかと使ったところ、まさかのACになってびっくり！
調べてみると、input()が激遅であることが判明！！！
参考記事
Pythonの知っておくと良い細かい処理速度の違い8個
ほかにも計算量について、コードの改善余地はあるが、
(abやpxの受け取りのところとか)
ACになったからまあいいや〜
#27 JOI 2009 予選 4 - 薄氷渡り
こちらも初見で解けませんでした！！！
まさかの**家政婦は見た！(seen)**が使えない問題！！！
過去記事
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】
の部分和問題もDFSで解ける問題なのですが、
**家政婦は見た！(seen)**が使えない場合は、**家政婦は見た！(seen)**に変わるものを自分で考えないといけないので難易度高め！
- Part3の部分和問題：indexとsum
- 今回の問題：スタック時の位置、過去の履歴
難しい問題をたくさん解いて慣れていくしかなさそう！
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
m = I()
n = I()
area = [LI() for _ in range(n)]
ans = 0
dndm = [[1,0],[-1,0],[0,1],[0,-1]]
stack = [] #スタック時の位置、過去の履歴
def dfs(i,j):
global ans
stack.append([[i,j],set()])
while stack:
[sn,sm],history = stack.pop()
ans = max(ans,len(history))
for dn,dm in dndm:
nn,nm = sn+dn,sm+dm
if not(0<=nn<=n-1) or not(0<=nm<=m-1) or area[nn][nm]==0 or ((nn,nm) in history):
continue
stack.append([[nn,nm],history | {(nn,nm)}])
for i,j in itertools.product(range(n),range(m)):
if area[i][j]==1:
dfs(i,j)
print(ans)
※補足
history | {(nn,nm)}
の
|は和集合です！(ビット演算子のORでもある)
また、
&が積集合です！(ビット演算子のANDでもある)
^がどちらか一方の集合です！(ビット演算子のXORでもある)
※過去記事参照
【Python】ARC006A(集合(set)最強説)【AtCoder】
次回は、以下の6問を解いていきます！
#####幅優先探索
28 ALDS_11_C - 幅優先探索 基本問題です。
29 AtCoder Beginner Contest 007 C - 幅優先探索 重み無しグラフの最短経路問題は、幅優先探索で解けます。
30 JOI 2011 予選 5 - チーズ
31 JOI 2012 予選 5 - イルミネーション 少し実装が重いですが、頑張れば解けます。
32 AOJ 1166 - 迷図と命ず 実装が少し重いです。
33 AtCoder Beginner Contest 088 D - Grid Repainting これが解ければ、幅優先探索に慣れたと思って良いです。
Part6/22
おわり！