記事の対象読者　鉄則本を読んでいる人へ

みなさん、競技プログラミングに励んでいますか？

いま、競技プログラミングを上達させるための一冊といえば、競技プログラミングの鉄則ですよね！！　

しかし、初心者の皆さん、この本を使いこなせていますか？？

わたし自身、最初はこの本の理解に時間がかかりました。

そこで、

ちょっと苦手意識がある
得意とはいえない

と感じているみなさんに役立てるように、鉄則本の勉強メモを記事化します！！！！

競技プログラミングに苦手意識がある人でも理解しやすいように、この記事では、以下の観点にそって鉄則本の要点を紹介します。

問題が伝えたい考え方
実装上の注意
習熟したい基礎

もちろん、鉄則本を読んでいる人向けの内容です。

今回扱うテーマは、グラフです。

言語は、Python を使用します。

鉄則本の内容を染み込ませるために、ぜひこの記事を活用してみてください。

それでは、さっそく内容に移りましょう。

ほんとうの初心者さんはこちら

ちなみに、競技プログラミング初心者は、こちらの記事がおすすめです。
鉄則本の作者さんの記事です。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】

A61,B61 グラフの実装方法

この問題が伝えたい考え方

グラフの表現方法は隣接リストを採用する。
入力として与えられる辺をリストのリストにする。そのリストから、隣接リストを作成する。

実装上の注意点

隣接リストの要素数はN＋1個。これは、頂点番号とインデックスを揃えるため。

習熟したい基礎

リスト内包表記により、入力である辺をリストのリストにする。edges = [ list(map(int, input().split())) for i in range(M) ]
隣接リストの初期化。空リストを要素にもつリストをリスト内包表記で作成する。G = [ list() for i in range(N + 1) ]
リストのリストの要素へのfor文でのアクセス方法。for a, b in edges:
friend.index(mx) これはリスト friend の中で、値 mx が最初に現れるインデックス（位置）を探します。

A62 深さ優先探索

この問題が伝えたい考え方

グラフの連結判定には、深さ優先探索が使える

実装上の注意点

Pythonの場合、再起呼び出しの深さの上限を設定する必要がある。sys.setrecursionlimit(120000)

B62 移動経路の記録

この問題が伝えたい考え方

単純パスの求め方
深さ優先探索で頂点を訪れるたびに経路に追加する。ただし、それ以上先に行けな頂点は経路から削除する。

実装上の注意点

それ以上深く探索することのない頂点では、DFS関数は何もしない。よって、何もせず、一つ上の階層の処理に戻る。ここで、何もしないのではなく、それ以上深く探索できない頂点を経路から削除すればいい。

習熟したい基礎

sys.exit(0)は、Pythonプログラムを正常終了させるために使用されます。引数には終了ステータスコードを指定し、0は正常終了、0以外はエラー終了を意味します。
sys.exitはSystemExit例外を発生させるため、必要に応じて例外処理で捕捉することができます。
sys.exitを使うことで、プログラムの任意の場所で実行を停止させることができるため、特定の条件下での異常終了やエラー処理に役立ちます。

A63 幅優先探索

この問題が伝えたい考え方

重みなしグラフの最短距離探索には、幅優先探索が使える。
幅優先探索には、データ構造のキューを使う。

実装上の注意

問題の条件より、到達できない頂点への距離は-1とする。よって、初期値には、-1を設定しておくと便利。

習熟したい基礎

from collections import dequeにより、キューを使う。
Q = deque()キューの初期化。追加や削除は、リストの書き方と同じ。

B63

この問題が伝えたい考え方

二次元の迷路をグラフに見立てる。
マス（i, j）の頂点番号を、(i-1) * W(迷路の列数) + jによって隣接リストにマッピングする。
隣接リストで表現できれば、あとはただの幅優先探索の問題。

A64 ダイクストラ法

この問題が伝えたい考え方

重み付き無効グラフの最短経路問題には、ダイクストラ法が使える。
距離の暫定値を更新する（動的計画法の配る遷移形式に近い。iが確定しているとき、i+1やi+2の値を更新する考え方）

実装上の注意点

暫定値が最小の頂点を高速に求めるために、優先度付きキューが使える。
訪問済みの頂点を追跡し、すでに最短距離が確定した頂点を再び処理しないようにする。
暫定値の初期値には、大きな数値を設定する。本書の場合、INF = 10 ** 10などを設定。

習熟したい基礎

優先度つきキューの使い方。import heapqする。
キューへの追加。heapq.heappush(Q, (cur[1], 1))
キューからの削除と取得。pos = heapq.heappop(Q)[1]
重みつきグラフの隣接リスト表現↓　。タプルで、(頂点, その頂点への重み)で表現する。

for a, b, c in edges:
	G[a].append((b, c))
	G[b].append((a, c))

G = [[], [(2, 15), (4, 20)], [(1, 15), (3, 65), (5, 4)], [(2, 65), (6, 50)], [(1, 20), (5, 30)], [(2, 4), (4, 30), (6, 8)], [(3, 50), (5, 8)]]

B64

この問題が伝えたい考え方

具体的な最短経路は、動的計画法の復元と似たような考え方で求められる。

goal = N
path = [goal]
now = goal

while now != 1:
    for to, w in G[now]:
        if cur[to] + w == cur[now]:
            path.append(to)
            now = to
            break

print(*path[::-1])

習熟したい基礎

アンパック演算子 * は、リストやタプルの要素を個別の引数として展開します。例えば、リスト lst = [1, 2, 3] があるとき、print(*lst) は print(1, 2, 3) と同じ意味になります。

A66 Union-Find木

この問題が伝えたい考え方

Union-Find木は、グループ分けを効率的に管理することができるデータ構造。
グループとグループの統合、要素が同じグループにあるのかどうか、を高速に処理できる。
Union-Find木は、根付き木構造になっている。

実装上の注意点

計算量を減らすために、グループを結合するとき、頂点数の多いグループを上に持っていく。

A67 最小全域木

この問題が伝えたい考え方

最小全域木　すべての頂点が繋がっていてその長さが最小のもの。
最小全域木は、「短い辺から追加していく」という貪欲法によって求められる。
実装上は、クラスカル法と呼ばれていて、配列のソートとUnion-Findを用いて実装できる。

実装上の注意

Union-Findのクラスさえ用意してあれば、クラスカル法の実行部分は少ない。
辺の長さを小さい順にソートすることを忘れずに。

# 辺を長さの小さい順にソートする
edges.sort(key = lambda x: x[2])

# 最小全域木を求める
uf = unionfind(N)
answer = 0
for a, b, c in edges:
	if not uf.same(a, b):
		uf.unite(a, b)
		answer += c

習熟したい基礎

リストのsortメソッド。
key引数　sortメソッドの key引数は、並べ替えの基準となる値を返す関数を指定します。この関数はリストの各要素に適用され、その結果が並べ替えに使用されます。
lambda x: x[2]　lambda は匿名関数を作成するためのキーワードです。lambda x: x[2] は、引数 x を受け取り、x の第3要素（インデックス2の要素）を返す関数を定義しています。ここで、x はリスト edges の各要素を表しています。各要素がリストやタプル (a, b, c) であれば、x[2] は c になります。

おすすめ記事