【AtCoder 初心者】ACL Beginner の参加記録 ~感想と解法~【python】

AtCoder
この記事は約4分で読めます。

ABC179に引き続き,連続での参加となります.

スポンサーリンク

A問題:A – Repeat ACL

何も不安がることはない.

K=int(input())

print("ACL"*K)

B問題:Integer Preference

a~bとc~dの区間に注目する.

数字が被っていない場合(以下の2パターン)はNo,それ以外はYesという風に考える.

ソースコードは以下の通り.

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())
  
a,b,c,d=input2()

if d<a or b<c:
	print("No")
else:
	print("Yes")

C問題:Connect Cities

鬼門のC問題.

N個の都市間を全て行き来できる(到達可能)ように道路をつなぎ,その数を答えよという問題.

まず以下の入力を考える.

5 2
1 4
2 3

このケースでは「都市1-都市4」と「都市2-都市3」が道路で繋がっており,「都市5」は独立している状態.この状態から全ての都市を行き来するためには,以下のように道路をつなげば良い.

上図のように,「都市1-都市2」と「都市2-都市5」間を道路でつなぐと,全ての都市に行き来できるようになる.

このように,図で書くと分かるのだが,「部分グラフの数-1」がこの問題の解となる.

そこで部分グラフの数を求めるのに使うのが「Union-Find」というアルゴリズムである.

この問題をみた途端,「Union-Findで一発じゃね?」って考えられたら,あなたの勝ちです.

ソースコードは以下の通り.

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n

	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)

		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x
		# print(self.parents)
n,m=input2()
AB=[input_array() for _ in range(m)]


uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1
print(ans-1)

感想(懺悔コーナー)

D問題も見た目簡単そうだなーと思って挑んだのですが,爆死しました.今回はどうやら水色レベルだったらしい...

茶色と緑色はどこにいったのだろうか...(勉強します.)

関連記事

参考図書

アルゴリズムに関する実践的な知識を身に付けたい人向け(オススメ)

競技プログラミングで出てくるアルゴリズム全般を勉強したい人向け

Pythonで競技プログラミングを解きたい人向け

おーよしの紹介
院卒Webエンジニアマン

「プログラミング」や「開発技術」,「大学院の苦労話」について情報発信してます.これからのIT時代を生き抜くため,自分のスキルを磨き続けます.将来は起業できたらいいなという思いがあります.

oyoshiをフォローする
スポンサーリンク
AtCoder python アルゴリズム プログラミング
スポンサーリンク
にほんブログ村に参加中(^~^)
PVアクセスランキング にほんブログ村
おーよしぶろぐ

コメント

タイトルとURLをコピーしました