LoginSignup
6
8

More than 3 years have passed since last update.

@rudorufu1981

【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part6/22】

Last updated at Posted at 2020-05-05

目指せ水色コーダー！！！！！！

ということで、
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】(@e869120さん)

AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

こちらの記事の初中級者が解くべき過去問精選 100 問
をPythonで解いていきます！
@e869120さんに感謝！！！！！！

過去記事リンク

全探索：全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part1/22】
全探索：工夫して通り数を減らす全列挙
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part2/22】
全探索：ビット全探索
【Python】初中級者が解くべき過去問精選 100 問を解いてみた【Part3/22】
全探索：順列全探索
【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)にする！
②家政婦は見たら、ストックに入れます！！！
（家政婦がゴミを見たので、ゴミ箱に入れるイメージ！！！）

このイメージが頭にあれば、実装の時に脳死でコードが書ける！

test.py
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回目）

test.py
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回目）

test.py
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
  • 今回の問題：スタック時の位置、過去の履歴

難しい問題をたくさん解いて慣れていくしかなさそう！

test.py
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
おわり！

次(Part7/22)へ

6
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
6
8