記事の対象読者 鉄則本を読んでいる人へ
みなさん、競技プログラミングに励んでいますか？
いま、競技プログラミングを上達させるための一冊といえば、競技プログラミングの鉄則ですよね！！
しかし、初心者の皆さん、この本を使いこなせていますか？？
わたし自身、最初はこの本の理解に時間がかかりました。
そこで、
- ちょっと苦手意識がある
- 得意とはいえない
と感じているみなさんに役立てるように、鉄則本の勉強メモを記事化します！！！！
競技プログラミングに苦手意識がある人でも理解しやすいように、この記事では、以下の観点にそって鉄則本の要点を紹介します。
- 問題が伝えたい考え方
- 実装上の注意
- 習熟したい基礎
もちろん、鉄則本を読んでいる人向けの内容です。
今回扱うテーマは、グラフです。
言語は、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 になります。