の続きです。

ALDS_11_C - 幅優先探索

practice.py

from collections import deque

n = int(input())
connected = [[] for _ in range(n+1)]
for _ in range(n):
    u,k,*V = map(int,input().split())
    connected[u] = V
visited = [-1]*(n+1)
q = deque()
q.append(1)
visited[1] = 0
while q:
    now = q.popleft()
    for to in connected[now]:
        if visited[to] != -1:
            continue
        q.append(to)
        visited[to] =  visited[now]+1
for i, ans in enumerate(visited[1:]):
    print(i+1, ans)

この問題はすごい勉強になる問題です。まずはBFSを使うのにほぼ必須と言ってもいいdequeをcollectionsからインポートしておきましょう。そのあとはdfsと同じように情報を受け取っていきましょう。connectedのところを+1でやっているのは全てにわざわざ-1をしていくのがめんどくさいし混乱するから。そのあとは既に訪ねた場所かどうかを調べるのと始めておとづれた時間を格納していくためのvisited変数を作ってあげましょう。そしてdequeにbfsを開始するために必要な1を入れてあげてからbfsを始めていきます。dfsと同様にまず1と繋がっている場所を調べて、もしおとづれたことが無いのならdequeにその場所を追加して、visitedにも現在の時間+1をぶち込んであげましょう。そしてqの中に何も無くなったら結果を出力してあげればACです。
dequeについて

07 幅優先探索

practice.py

from collections import deque

R,C = map(int, input().split())
sy,sx = map(int, input().split())
sy-=1
sx-=1
gy,gx = map(int, input().split())
gy-=1
gx-=1
field = [list(input()) for _ in range(R)]
visited = [[-1]*C for _ in range(R)]
q = deque()
q.append((sy,sx))
visited[sy][sx] = 0
while q:
    cy,cx = q.popleft()
    if field[cy+1][cx]=="." and visited[cy+1][cx]==-1:
        visited[cy+1][cx]=visited[cy][cx]+1
        q.append((cy+1,cx))
    if field[cy-1][cx]=="." and visited[cy-1][cx]==-1:
        visited[cy-1][cx]=visited[cy][cx]+1
        q.append((cy-1,cx))
    if field[cy][cx+1]=="." and visited[cy][cx+1]==-1:
        visited[cy][cx+1]=visited[cy][cx]+1
        q.append((cy,cx+1))
    if field[cy][cx-1]=="." and visited[cy][cx-1]==-1:
        visited[cy][cx-1]=visited[cy][cx]+1
        q.append((cy,cx-1))
print(visited[gy][gx])

この問題はTLEにならないように頑張る問題です。まずは情報を受け取っていきましょう。今回はインデックス番号主体で操作をしていきたいのであらかじめ、sy,sx,gy,gxの値から1を引いておきましょう。そして到達できる時間を格納するためのvisited変数を作っておきましょう。そしてbfsを始めるための準備を始めます。今回は二重配列を含む問題なのでdequeにもy座標とx座標の値を入れといてあげましょう。そしてスタート地点の値は0にしておきましょう。そのあとは上下左右の値を調べて"."であるかつまだ行ったことのない場所ならvisitedの値を変更してdequeにその場所の座標を追加しましょう。ここでtuple型を使っているのはそっちの方が計算速度が早くなるからです。そして最後にゴールの座標の値を出力してあげればACです。

JOI 2011 予選 5 - チーズ

practice.py

from collections import deque

def bfs(sy,sx,target,H,W,field):
    visited = [[-1]*W for _ in range(H)]
    movement = [(0,1),(0,-1),(1,0),(-1,0)]
    q = deque()
    q.append((sy,sx))
    visited[sy][sx] = 0
    while q:
        cy,cx = q.popleft()
        for dy,dx in movement:
            y = cy+dy
            x = cx+dx
            if y < 0 or H <= y or x < 0 or W <= x:
                continue
            if field[y][x] == "X":
                continue
            if visited[y][x] != -1:
                continue
            if field[y][x] == target:
                visited[y][x] = visited[cy][cx]+1
                return visited[y][x]
            visited[y][x] = visited[cy][cx]+1
            q.append((y,x))


H,W,N = map(int, input().split())
field = [list(input()) for _ in range(H)]
cheese = [(0,0) for _ in range(10)]
sy,sx = 0,0
for i in range(H):
    for j in range(W):
        if field[i][j] == "." or field[i][j] == "X":
            continue
        elif field[i][j] == "S":
            sy,sx = i,j
        else:
            field[i][j] = int(field[i][j])
            cheese[field[i][j]] = (i,j)
target = 1
time = 0
while target <= N:
    time += bfs(sy,sx,target,H,W,field)
    sy,sx = cheese[target]
    target += 1
print(time)

この問題はbfsをチーズの数だけ繰り返していく感じの問題です。イメージとしてはスタート地点のチーズから1のチーズまでのbfs、1のチーズから2のチーズまでのbfs...みたいな感じ。まずは情報を受け取ってfieldの情報を扱いやすいようにチーズの番号をint型に変換してあげましょう。そしてcheeseの場所を保管しておくcheese変数も作っちゃいましょう。最初に食べたいチーズの番号は1なので、target変数の初期値として、その後に最後に食べるチーズにたどり着くまでの時間を格納するための変数timeを作ってあげましょう。そして最後のチーズにたどりつくためのwhile文を作ってあげましょう。楽しいbfs始まるよーーー!bfsにはスタート地点の座標とtargetのチーズの番号、そしてfieldの情報に、擬似fieldを作りだすためにHとWの値を渡してあげましょう。そこからは基本的に他のbfsと同じような処理をしていきます。まずはおとづれたかどうかを調べるためのvisited変数を作るそしてdequeに初期値の座標を落とし込んであげる。そしてbfsをwhile文で始めてあげる。まずは例外として動いた後の座標がfieldの範囲を飛び出してしまうものと侵入不可能なもの、そして既におとづれているものをcontinueで取り除いてあげます。もしチーズの座標に辿り着けたのなら、visitedの値を他と同じように更新してあげて、それをreturnで返してあげましょう。それ以外のケースではvisitedの値を更新して、qに追加してあげるだけです。そして最後に全てのチーズを食べ切るまでの時間を格納したtime変数の値を出力してACです。

JOI 2012 予選 5 - イルミネーション

practice.py

from collections import deque

def judge(sy,sx,field,W,H,even,odd):
    cnt = 0
    if sy%2==0:
        move = even
    else:
        move = odd
    for dy,dx in move:
        y = sy+dy
        x = sx+dx
        if y < 0 or y > H+1 or x < 0 or x > W+1:
            continue
        if field[y][x] == 1:
            cnt += 1
    return cnt


W,H = map(int, input().split())
field = []
field.append([0]*(W+2))
for _ in range(H):
    field_line = list(map(int, input().split()))
    field_line = [0]+field_line+[0]
    field.append(field_line)
field.append([0]*(W+2))
visited = [[-1]*(W+2) for _ in range(H+2)]
even = [(-1, -1), (-1, 0), (0, 1), (1, 0), (1, -1), (0, -1)]
odd = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (0, -1)]
ans = 0
q = deque()
q.append((0,0))
cnt = judge(0,0,field,W,H,even,odd)
visited[0][0] = cnt
ans += cnt
while q:
    sy,sx = q.popleft()
    if sy%2==0:
        move = even
    else:
        move = odd
    for dy,dx in move:
        y = sy+dy
        x = sx+dx
        if y < 0 or y > H+1 or x < 0 or x > W+1:
            continue
        if field[y][x] == 1:
            continue
        if visited[y][x] != -1:
            continue
        q.append((y,x))
        cnt = judge(y,x,field,W,H,even,odd)
        visited[y][x] = cnt
        ans += cnt
print(ans)

この問題の考え方は主に隣接する建物数から答えを導き出すです(BFSでは主に建物ないところを探索していく)。なので、受け取るマップの情報を0で囲ってあげる必要があります。次に重要な部分は動きが奇数の時と偶数の時で異なるとういうことです。前までの問題ではmovementに一つのパターンを入れるだけでよかったですが、今回は2つの異なるパターンを入れないといけません。動きをぶち込んだら準備はおわりです。そしてqに0,0を入れておきます。そしてcntに最初の座標に隣接する建物の数を入れときます。BFSの中では前の問題と同じように現在地の座標をpopleftで取り出して、syの座標からどっちの動きを適応するかを判定して、for文を回していきます。ここではマップからはみ出してしまうケースと座標に建物があるケース、既に調べてあるケースを除いておきます。この処理を終わるまで繰り返して、最後にansの値を出力してあげればACです。

AOJ 1166 - 迷図と命ず

practice.py

from collections import deque

ans = []
while True:
    W,H = map(int,input().split())
    if W == 0:
        break
    verticle = []
    horizon = [[0]*W]
    for i in range(H*2-1):
        lis = list(map(int, input().split()))
        if i % 2==0:
            verticle.append([0]+lis)
        else:
            horizon.append(lis)
    visited = [[0]*W for _ in range(H)]
    moves = [(1,0),(-1,0),(0,1),(0,-1)]
    q = deque()
    q.append((0,0))
    visited[0][0] = 1
    while q:
        sy,sx = q.popleft()
        for dy,dx in moves:
            y = sy+dy
            x = sx+dx
            if dy == 1 and dx == 0:
                if y < 0 or H-1 < y or x < 0 or W-1 < x:
                    continue
                if visited[y][x] != 0:
                    continue
                if horizon[y][x] == 1:
                    continue
                visited[y][x] = visited[sy][sx]+1
                q.append((y,x))
            elif dy == -1 and dx == 0:
                if y < 0 or H-1 < y or x < 0 or W-1 < x:
                    continue
                if visited[y][x] != 0:
                    continue
                if horizon[sy][x] == 1:
                    continue
                visited[y][x] = visited[sy][sx]+1
                q.append((y,x))
            elif dy == 0 and dx == 1:
                if y < 0 or H-1 < y or x < 0 or W-1 < x:
                    continue
                if visited[y][x] != 0:
                    continue
                if verticle[y][x] == 1:
                    continue
                visited[y][x] = visited[sy][sx]+1
                q.append((y,x))
            else:
                if y < 0 or H-1 < y or x < 0 or W-1 < x:
                    continue
                if visited[y][x] != 0:
                    continue
                if verticle[y][sx] == 1:
                    continue
                visited[y][x] = visited[sy][sx]+1
                q.append((y,x))
    ans.append(visited[H-1][W-1])
for a in ans:
    print(a)

この問題は、visitedの中の値を少しづつ埋めていって、最後の出口の値を出力していく問題です。　まずは他の問題と同じようにdequeをインポートします。そして一塊の入力ごとに結果を出力していったらうまくいっているかが確認しづらいので、ansリストを作って一度結果をこのリストにぶち込んでからfor文を回して出力していきます。最初に必要な情報を受け取っていってから、マップの入力を処理しやすいように整えていきます。そして、動ける範囲は左右上下なので、moveを作っていきます。他のbfs問題と同じようにdequeを作って初期位置をdequeに追加してあげて、ついでに初期ちちのvisitedの値も変えてあげましょう。while文の中では他のbfsと同じようにpopleft()からmoveリストの値を元に、位置を動かしていきます。今回はどこに線があるかが重要な問題なので、dyとdxを元に処理を変化させていきます。全てに共通しているものはマップからはみ出していないかどうか、すでにおとづれた場所ではないかです。まずは上に行くときは自分か1ではだめなので、horizon[sy][x]にしています。そして下に行くときは行き先が1ではダメなので、horizon[y][x]を処理に使い。右に動くときは行き先をチェック、左に動くときは自分の現在地をチェックみたいな感じです。そして何事もなかったらdequeに動かした後の位置を追加しvisitedの値を前の動かす前の位置を元に更新していきます。そして、ansファイルに出口に行くまでにかかる値を追加して、最後にfor文で出力していきます。

ABC088 D - Grid Repainting

practice.py

from collections import deque

H,W = map(int, input().split())
field = [list(input()) for _ in range(H)]
cnt = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            cnt += 1
visited = [[-1]*W for _ in range(H)]
moves = [(1,0),(-1,0),(0,1),(0,-1)]
q = deque()
q.append((0,0))
visited[0][0] = 1
while q:
    sy,sx = q.popleft()
    for dy,dx in moves:
        y = sy+dy
        x = sx+dx
        if y < 0 or H-1 < y or x < 0 or W-1 < x:
            continue
        if visited[y][x] != -1:
            continue
        if field[y][x] == '#':
            continue
        visited[y][x] = visited[sy][sx]+1
        q.append((y,x))
if visited[H-1][W-1] == -1:
    print(-1)
    exit()
ans = H*W-cnt-visited[H-1][W-1]
print(ans)

この問題は一見難しそうに見えますが意外と単純です。基本的な動作としては全てのfieldの要素の数(HW)からスタートからゴールに辿り着くまでの最短時間と、最初から#になっている要素の数を引いて出力するだけです。まずは他のbfsと同じで情報を取得します。取得し終わったら一定の位置に辿り着けるまでの時間を記録するためのvisitedリストと、whileの中での動作を簡単にするためのmovesリストを作ってあげましょう。そしてdequeを作り出して、初期値をぶち込みます。そしていよいよbfsを開始していきます。正直中でやっていることは上の問題07 幅優先探索とほぼ同じなのでそっちの解説を参照してください、if y < 0 or H-1 < y or x < 0 or W-1 < xはフィールドの範囲から出ていないかをチェックするためのものです(indexエラー防止用)。そして上に書いた処理をする前にゴールに辿り着けないケースでは-1を出力しなければいないので、if文で捕まえてあげましょう。もしつかまらかったときは上のHWから初期の#の数とゴールまでの最短距離の数を引いてあげて出力してあげましょう。

ALDS_10_A - フィボナッチ数

practice.py

n = int(input())
fibo = [0]*(n+1)
fibo[0] = 1
fibo[1] = 1
for i in range(2,n+1):
    fibo[i] = fibo[i-1]+fibo[i-2]
print(fibo[n])

この問題はDPの基本の考え方の前回までの値から現在の値を求めるというのがよく学べる良い問題でした。fiboのところを[0]*(n+1)にしているのはfiboが0からスタートしていくからです。

DPL_1_B - 0,1ナップザック問題

practice.py

N,W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
    val,wei = map(int, input().split())
    for w in range(W+1):
        if w-wei < 0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w], dp[i-1][w-wei]+val)
print(dp[N][W])

この問題は超有名なDP問題ナップザック問題ですね。イメージとしてはi個までのアイテムをwの範囲で買うときの最大効率の答えを一つずつ地道に埋めていって、次のループでその情報を使って、新しいアイテムが入った後の最大効率を求めいく感じの問題です、なんかタイムリープ系の話みたいでかっこいいね。for文の中ではまず、重さが超えてしまった時の処理を追加してあげます、単純になんの変化も加えずに上の情報をそのままぶち込んでいってあげるだけです。それ以外の場合では、加える場合と加えない場合を比べて大きい方をDPにぶち込んであげます。そして、最後に最後のリストの重さの限界値の値を出力してあげればACできます。

DPL_1_C - ナップザック問題

practice.py

N,W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
    val,wei = map(int, input().split())
    for w in range(1,W+1):
        if w-wei<0:
            dp[i][w] = dp[i-1][w]
        else:
            dp[i][w] = max(dp[i-1][w],dp[i][w-wei]+val)
print(dp[N][W])

この問題の前回と同じところは同じアイテムを何回でも選べるところです。なので、基本的な処理は前回と同じです。重複を許すために帰るとこは9行目のmaxの後ろのところの前回ではdp[i-1]だったところをdp[i]にするだけで重複を許したバージョンを作ることができます。

DPL_1_A - コイン問題

practice.py

INF = 1 << 60
N,M = map(int, input().split())
dp = [[INF]*(N+1) for _ in range(M+1)]
dp[0][0] = 0
clist = [0]+list(map(int, input().split()))
for i in range(1,M+1):
    for j in range(N+1):
        if j-clist[i] < 0:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j],dp[i][j-clist[i]]+1,dp[i-1][j-clist[i]]+1)
print(dp[M][N])

この問題は最小を求めるタイプのdpなので、前回までのように初期値を0にしてはいけません。最初は全てのdpをINFという果てしなくデカイ数字をぶち込んだ変数をベースにして作り出して動作を始めていきましょう。そして、dp[0][0]の値をだけを0に変えて実際にdpを始めてあげましょう。clistの最初に0を足している理由はdpのfor文は基本的に1から始まるので、clistからコインの値を出していくときにいちいち1を引いていくのがめんどくさいからです。今回は3つのパターンからminを求めていきます。普通に前回までの最小値がそのまま最小値になるパターンと、前回の[jからコインの価値を引いた数]の最小値に1を足すだけのパターンと、現在のdpの[jからコインの価値を引いた数]の最小値に1を足すだけの3パターンです。これを延々とやっていって最後にdp[M][N]の値を出力すればACできます。

ALDS_10_C - 最長共通部分列

practice.py

#上と同じようにやっていったらTLEになった、誰かTLEにならない方法教えてください。二周目では解き切る！