LoginSignup
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@tai-sei

競技プログラミング　基本知識(1)

Posted at

競技プログラミングに向けた、アルゴリズム学習日記

この記事は私がatcorderで必要だと感じた基本的な知識をまとめて共有する記事です！
それぞれのパートに例題も含めたので、atcorder初心者のかたも競プロの雰囲気を感じられるのではないかと思います！
是非ご拝読ください！

全探索

全探索とは、すべての可能性を片っ端から検証することです。今回は、深さ優先探索、幅優先探索という2種類の探索法を解説していきます！

再帰関数

再帰関数は、自身を呼び出す関数で、特にツリー構造や全探索に適しています。​Pythonでは、再帰の深さ制限があるため、深い再帰を行う場合は制限を緩和する必要があります。

import sys
sys.setrecursionlimit(10**7)

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

factorial(5)#120

このプログラムは、5の階乗を計算しています。処理自体はループでも書くことができますね。
再帰関数は、必ず関数が停止するように書く必要があります。nが0の場合の処理を指定しないと、プログラムが暴走してしまいます。

スタックを用いた再帰の模倣

再帰は内部的にスタック(後入れ先出し)を使用しています。​明示的にスタックを使って再帰を模倣することも可能です。

def factorial_iterative(n):
    stack = []
    result = 1
    while n > 0:
        stack.append(n)
        n -= 1
    while stack:
        result *= stack.pop()
    return result

例題

問題文：7, 5, 3 のみからなる数で、7, 5, 3 がすべて含まれるもののうち、N 以下のものの個数を求める。​

解法
再帰関数を用いて、7, 5, 3 を追加していく全探索を行います。​各ステップで、現在の数に7, 5, 3を追加し、N以下であれば再帰的に探索を続けます。​数に7, 5, 3がすべて含まれていればカウントします。

def dfs(n, use):
    if n > N:
        return 0
    res = 1 if use == 0b111 else 0
    for d, b in zip([7, 5, 3], [0b001, 0b010, 0b100]):
        res += dfs(n * 10 + d, use | b)
    return res

N = int(input())
print(dfs(0, 0))

スタックとキューの使い分け

スタック（LIFO）

スタックは「後入れ先出し」のデータ構造で、深さ優先探索（DFS）に適しています。

stack = []
stack.append(1)
stack.append(2)
print(stack.pop())  # 出力: 2

stack.pop():

これは、stack というリスト（スタックとして使われています）から、一番最後の要素を取り出す操作です。
取り出された要素は、stack から削除されます。
例えば、stack が [1, 2, 3] だった場合、stack.pop() を実行すると 3 が取り出され、stack は [1, 2] になります

キュー（FIFO）

キューは「先入れ先出し」のデータ構造で、幅優先探索（BFS）に適しています。

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
print(queue.popleft())  # 出力: 1

深さ優先探索（DFS）の詳細解説

以下のコードコードは深さ優先探索（DFS: Depth-First Search）の再帰的実装です。このアルゴリズムを詳しく解説します。

def dfs(graph, v, visited):
    visited[v] = True
    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

1. 関数の引数

  • graph: グラフを表現するデータ構造（隣接リストまたは隣接行列）
  • v: 現在探索中のノード（頂点）
  • visited: 各ノードが訪問済みかどうかを記録する配列またはディクショナリ

2. 処理の流れ

  1. 訪問マーキング: visited[v] = True で現在のノード v を訪問済みとしてマークします
  2. 隣接ノードの探索: for neighbor in graph[v] で現在のノード v に隣接するすべてのノードについて処理を行います
  3. 未訪問チェック: if not visited[neighbor] で隣接ノードがまだ訪問されていないかを確認します
  4. 再帰呼び出し: 未訪問の隣接ノードについて、dfs(graph, neighbor, visited) で再帰的にDFSを続行します

3. アルゴリズムの動作イメージ

例として、以下のようなグラフを考えます：

    A
   / \
  B   C
 / \   \
D   E---F

このグラフを隣接リストで表現すると：

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

DFSの実行過程（ノードAから開始）:

  1. ノードAを訪問: visited['A'] = True
  2. Aの隣接ノードBを探索:
    • Bを訪問: visited['B'] = True
    • Bの隣接ノードA: すでに訪問済みなのでスキップ
    • Bの隣接ノードDを探索:
      • Dを訪問: visited['D'] = True
      • Dの隣接ノードB: すでに訪問済みなのでスキップ
      • Dの処理完了、Bに戻る
    • Bの隣接ノードEを探索:
      • Eを訪問: visited['E'] = True
      • Eの隣接ノードB: すでに訪問済みなのでスキップ
      • Eの隣接ノードFを探索:
        • Fを訪問: visited['F'] = True
        • Fの隣接ノードC: まだ未訪問
        • Fの隣接ノードCを探索:
          • Cを訪問: visited['C'] = True
          • Cの隣接ノードA: すでに訪問済みなのでスキップ
          • Cの隣接ノードF: すでに訪問済みなのでスキップ
          • Cの処理完了、Fに戻る
        • Fの隣接ノードE: すでに訪問済みなのでスキップ
        • Fの処理完了、Eに戻る
      • Eの処理完了、Bに戻る
    • Bの処理完了、Aに戻る
  3. Aの隣接ノードC: すでに訪問済みなのでスキップ
  4. Aの処理完了、DFS終了

4. 実際の使用例

以下は完全な使用例です：

def dfs(graph, v, visited):
    visited[v] = True
    print(f"ノード {v} を訪問")
    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

# グラフの定義（隣接リスト形式）
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 訪問状態を記録する辞書を初期化
visited = {node: False for node in graph}

# DFSをノードAから開始
dfs(graph, 'A', visited)

5. 時間複雑度と空間複雑度

  • 時間複雑度: O(V + E)、Vはノード（頂点）数、Eはエッジ（辺）数
    • 各ノードは一度だけ訪問され、各エッジも一度だけ調べられる
  • 空間複雑度: O(V)
    • 再帰呼び出しのスタックとvisited配列のためのメモリ

6. 特徴と用途

  • 経路探索: 迷路や迷路生成、パス探索など
  • 連結成分の検出: グラフ内の連結している部分を見つける
  • トポロジカルソート: 有向非巡回グラフ（DAG）の順序付け
  • 強連結成分の検出: 有向グラフ内の強連結成分を見つける

7. 注意点と制限

  • スタックオーバーフロー: 再帰呼び出しが深すぎるとスタックオーバーフローが発生する可能性がある
  • バックトラック: DFSは一つの経路を最後まで探索するため、最短経路問題には適さない
  • 無限ループ: 閉路があるグラフでは訪問済みチェックが必須

8. 反復的な実装

再帰ではなくスタックを使った実装も可能です：

def dfs_iterative(graph, start):
    visited = {node: False for node in graph}
    stack = [start]
    
    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(f"ノード {v} を訪問")
            # 隣接ノードをスタックに追加（逆順で追加するとDFSの訪問順序が再帰版と近くなる）
            for neighbor in reversed(graph[v]):
                if not visited[neighbor]:
                    stack.append(neighbor)

競技プログラミングでは、DFSはグラフ探索の基本的なテクニックとして頻出します。木構造の探索や連結成分の検出、パス探索など、様々な問題に応用できる重要なアルゴリズムです。

例題

木構造が与えられ、各ノードに対して加算操作が行われる。各ノードの最終的な値を求める。

解法

DFSを用いて、親ノードの値を子ノードに伝播させていきます。​再帰的に各ノードを訪問し、親の値を加算していきます。

import sys
sys.setrecursionlimit(10**7)

def dfs(v, p):
    for u in tree[v]:
        if u != p:
            res[u] += res[v]
            dfs(u, v)

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)
    tree[b - 1].append(a - 1)

res = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    res[p - 1] += x

dfs(0, -1)
print(*res)

提供いただいたコードを解析し、BFSの詳細について説明します。以下にMarkdown形式で解説を行います。

幅優先探索（BFS）の詳細解説

以下のコードは幅優先探索（BFS: Breadth-First Search）のPython実装です。このアルゴリズムについて詳しく解説します。

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)
    distance = [0] * len(graph)
    queue = deque([start])
    visited[start] = True
    
    while queue:
        v = queue.popleft()
        for neighbor in graph[v]:
            if not visited[neighbor]:
                visited[neighbor] = True
                distance[neighbor] = distance[v] + 1
                queue.append(neighbor)
    
    return distance

1. 関数の引数

  • graph: グラフを表現するデータ構造（通常は隣接リスト）
  • start: 探索を開始するノード（頂点）の番号

2. 初期化部分

  • visited = [False] * len(graph): 各ノードの訪問状態を管理する配列
  • distance = [0] * len(graph): 開始ノードからの距離を記録する配列
  • queue = deque([start]): 探索対象のノードを管理するキュー
  • visited[start] = True: 開始ノードを訪問済みとしてマーク

3. 処理の流れ

  1. キュー操作: v = queue.popleft() でキューから先頭のノードを取り出す
  2. 隣接ノード探索: for neighbor in graph[v] で取り出したノードの隣接ノードを調べる
  3. 未訪問チェック: if not visited[neighbor] で未訪問の隣接ノードを特定
  4. 処理:
    • visited[neighbor] = True: 隣接ノードを訪問済みとしてマーク
    • distance[neighbor] = distance[v] + 1: 距離を更新（親ノードの距離+1）
    • queue.append(neighbor): 隣接ノードをキューに追加（後で処理するため）
  5. 返り値: 開始ノードからの距離を記録した配列 distance を返す

4. アルゴリズムの動作イメージ

例として、以下のようなグラフを考えます：

    0
   / \
  1   2
 / \   \
3   4---5

このグラフを隣接リストで表現すると：

graph = [
    [1, 2],    # ノード0の隣接ノード
    [0, 3, 4], # ノード1の隣接ノード
    [0, 5],    # ノード2の隣接ノード
    [1],       # ノード3の隣接ノード
    [1, 5],    # ノード4の隣接ノード
    [2, 4]     # ノード5の隣接ノード
]

BFSの実行過程（ノード0から開始）:

  1. 初期状態:

    • queue = [0]
    • visited = [True, False, False, False, False, False]
    • distance = [0, 0, 0, 0, 0, 0]

  2. ノード0の処理:

    • キューから0を取り出す → queue = []
    • 隣接ノード1, 2を調べる:
      • 1は未訪問 → visited[1] = True, distance[1] = 1, queue = [1]
      • 2は未訪問 → visited[2] = True, distance[2] = 1, queue = [1, 2]

  3. ノード1の処理:

    • キューから1を取り出す → queue = [2]
    • 隣接ノード0, 3, 4を調べる:
      • 0は訪問済み → スキップ
      • 3は未訪問 → visited[3] = True, distance[3] = 2, queue = [2, 3]
      • 4は未訪問 → visited[4] = True, distance[4] = 2, queue = [2, 3, 4]

  4. ノード2の処理:

    • キューから2を取り出す → queue = [3, 4]
    • 隣接ノード0, 5を調べる:
      • 0は訪問済み → スキップ
      • 5は未訪問 → visited[5] = True, distance[5] = 2, queue = [3, 4, 5]

  5. 以下同様に続き、すべてのノードを処理

  6. 最終的なdistance配列: [0, 1, 1, 2, 2, 2]
    (ノード0からの距離を表す)

5. 実際の使用例

以下は完全な使用例です：

from collections import deque

def bfs(graph, start):
    visited = [False] * len(graph)
    distance = [0] * len(graph)
    queue = deque([start])
    visited[start] = True
    
    while queue:
        v = queue.popleft()
        print(f"ノード {v} を処理（距離: {distance[v]}）")
        for neighbor in graph[v]:
            if not visited[neighbor]:
                visited[neighbor] = True
                distance[neighbor] = distance[v] + 1
                queue.append(neighbor)
    
    return distance

# グラフの定義（隣接リスト形式）
graph = [
    [1, 2],    # ノード0の隣接ノード
    [0, 3, 4], # ノード1の隣接ノード
    [0, 5],    # ノード2の隣接ノード
    [1],       # ノード3の隣接ノード
    [1, 5],    # ノード4の隣接ノード
    [2, 4]     # ノード5の隣接ノード
]

# BFSをノード0から開始
distances = bfs(graph, 0)
print("各ノードへの距離:", distances)

6. 時間複雑度と空間複雑度

  • 時間複雑度: O(V + E)、Vはノード（頂点）数、Eはエッジ（辺）数
    • 各ノードとエッジは一度だけ処理される
  • 空間複雑度: O(V)
    • visited配列、distance配列、キューのためのメモリ

7. 特徴と用途

  • 最短経路: 無向グラフで各辺の重みが等しい場合の最短経路問題
  • 連結成分の検出: グラフ内の連結部分を見つける
  • レベル順探索: 木構造を層ごとに探索
  • 2点間の最短距離: 迷路など格子状の問題での最短経路

8. DFSとの比較

  • BFSは幅優先で、同じ距離のノードをすべて処理してから次の距離に進む
  • DFSは深さ優先で、一つの経路を最後まで探索してから別の経路に移る
  • BFSは最短経路問題に適している
  • DFSは深い探索や全探索、バックトラッキングに適している

9. 競技プログラミングでの応用例

  • グリッド上の最短経路問題
  • 迷路の最短経路
  • 文字列の編集距離（単語変換問題）
  • 2点間の最短ステップ数
  • 特定条件を満たす最小操作回数

競技プログラミングでは、BFSはDFSと並んで基本的なグラフ探索アルゴリズムとして重要です。特に最短経路を求める問題や、層ごとに探索する必要がある場合に有用なテクニックです。

例題

N×Mの迷路があります。'#'は壁、'.'は通路、'S'はスタート地点、'G'はゴール地点を表します。上下左右の隣接するマスに移動できるとき、スタートからゴールまでの最短経路の長さ（何マス移動するか）を求めてください。
サンプル入力:

5 6
......
.S####
......
####G.
......

サンプル出力:

9

解法
この問題は典型的なBFS問題です。迷路をグリッドとして扱い、以下のステップで解きます：

  • スタート地点を見つける
  • BFSでスタートから各マスへの最短距離を計算
  • ゴール地点の距離を返す
from collections import deque

def solve(maze, H, W):
    # スタート地点とゴール地点を見つける
    for i in range(H):
        for j in range(W):
            if maze[i][j] == 'S':
                start = (i, j)
            elif maze[i][j] == 'G':
                goal = (i, j)
    
    # 距離を記録する2次元配列（-1は未訪問）
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    dist[start[0]][start[1]] = 0
    
    # BFSのキュー
    queue = deque([start])
    
    # 上下左右の移動
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    # BFS開始
    while queue:
        x, y = queue.popleft()
        
        # 現在の距離
        current_dist = dist[x][y]
        
        # 上下左右を探索
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            
            # 迷路の範囲内か確認
            if 0 <= nx < H and 0 <= ny < W:
                # 未訪問かつ壁でない場合
                if dist[nx][ny] == -1 and maze[nx][ny] != '#':
                    dist[nx][ny] = current_dist + 1
                    queue.append((nx, ny))
    
    # ゴール地点の距離を返す
    return dist[goal[0]][goal[1]]

# 入力処理
H, W = map(int, input().split())
maze = [input() for _ in range(H)]

# 解答
print(solve(maze, H, W))

詳細解説：

1. データの初期化

dist[i][j] は座標(i, j)へのスタートからの最短距離を表します
初期値は-1（未訪問）で、スタート地点は0に設定します
キューにスタート地点を入れて探索を開始します

2. BFSのプロセス

例えば、サンプル入力の迷路を処理する際のステップを追ってみましょう：

......   距離:  -1 -1 -1 -1 -1 -1
.S####         -1  0 -1 -1 -1 -1
......         -1 -1 -1 -1 -1 -1
####G.         -1 -1 -1 -1 -1 -1
......         -1 -1 -1 -1 -1 -1

1. スタート(1, 1)を処理:

上(0, 1)、下(2, 1)、左(1, 0)を探索（右は壁）
dist[0][1] = 1, dist[2][1] = 1, dist[1][0] = 1
キュー = [(0, 1), (2, 1), (1, 0)]

2.(0, 1)を処理:

上は範囲外、下は訪問済み、左(0, 0)と右(0, 2)を探索
dist[0][0] = 2, dist[0][2] = 2
キュー = [(2, 1), (1, 0), (0, 0), (0, 2)]

3. 以下同様に進み、BFSの特性により、最初にゴールに到達したときの距離が最短距離になります

3. アルゴリズムの要点

  • 層ごとの探索: BFSは距離が同じノードをすべて処理してから、距離が+1のノードを処理します
  • 最短性の保証: グリッド上の移動コストが均一（各移動=1）なので、BFSは最短経路を保証します
  • 訪問管理: すでに訪問したマスは再び訪問しないため、無限ループを防ぎます

4. その他のBFS応用例

  • 複数のスタート地点：例えば「水たまりが広がる」問題など、複数のスタート地点をキューに入れて同時にBFSを行う
  • 状態空間の探索：グリッドだけでなく、状態空間（例：パズルの状態）もBFSで探索できる
  • 重み付きグラフ：すべての辺の重みが同じ場合、BFSで最短経路を見つけられる

このように、幅優先探索（BFS）は迷路や格子状の問題での最短経路計算に非常に有効なアルゴリズムです。「同じ距離のノードをすべて処理してから次の距離に進む」という特性により、最短経路を確実に求めることができます。

1
2
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
1
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?