ACL Beginner ContestをPythonで解く-Shinoryo's Weblog

こんにちは, Shinoryoです.

今回はACL Beginner Contestを, Pythonで解いてみた結果を書き連ねていこうと思います.

A - Keyboard

$K$ 回「ACL」を出力します.

view raw atcoder-aclb-a.py hosted with ❤ by GitHub

整数範囲が重なる条件は, $B \geq C$ かつ $A \leq D$ になります.

view raw atcoder-aclb-b.py hosted with ❤ by GitHub

幅優先探索(breadth first search; BFS)と呼ばれる方法を用いて, 双方向道路で行き来することができる都市群が何個あるかを計算します.

幅優先探索はグラフ理論等で用いられるアルゴリズムです. ある根ノードで始まり隣接した全てのノードを探索し, そのそれぞれに対して同様のことを繰り返すことによって探索対象ノードを網羅します.

幅優先探索に関しては, 「AtCoder Beginner Contest 177をPythonで解く」(https://shinoryo-weblog.blogspot.com/2021/02/atcoder-beginner-contest-177.html)を参照してください.

この幅優先探索によって, 都市群が $G$ 個作られたとします. 最終的に, 都市同士は間接的にでもつながっていれば問題ないので, 求める数は $G - 1$ になります.

	# collectionsモジュールのdeque型を使用
	from collections import deque

	# 入力
	N, M = [int(x) for x in input().split()]

	# 都市連結情報リストの作成
	# 都市Aと都市Bがつながっていたら, A行目のリストにBを加える
	# リストのインデックスは0から始まるため, N+1行の2次元配列
	# (0行目の存在は無視する)
	g = [[] for _ in range(N+1)]
	for i in range(M):
	A, B = [int(x) for x in input().split()]
	g[A].append(B)
	g[B].append(A)

	# どの都市群に所属しているかが判明している人のリスト
	visited = [False]*(N+1)

	# 都市群の総数を記録
	group_number = 0

	# 各都市に対してループ
	for i in range(1,N+1):
	# どの都市群に所属しているかが判明している場合は調べなくてよい
	if visited[i]:
	continue

	# 都市群の総数に+1
	group_number += 1
	# 都市を調べたことにする
	visited[i] = True
	# deque型の変数を作成(まずはiとつながっている都市を調べるため, iを格納)
	queue = deque([i])

	# 幅優先探索の実行
	# queueの各要素についてつながっている都市を調べる
	while queue:
	k = queue.popleft()
	for j in g[k]:
	# iとつながっている新しい都市jに関して,
	# ・visited[j]をTrueにし,
	# ・queueにjを追加する
	if visited[j]:
	continue
	visited[j] = True
	queue.append(j)

	# 間接的につながっていてもいいので、
	# 求めるのはgroup_number - 1でよい
	print(group_number - 1)

view raw atcoder-aclb-c.py hosted with ❤ by GitHub

D以降は私の能力不足故に省略いたします.