#744795 (PyPy3) No.1868 Teleporting Cyanmond

提出ソース
結果

問題	No.1868 Teleporting Cyanmond
ユーザー	flora
提出日時	2022-03-11 21:26:00
言語	PyPy3 (7.3.15)
結果	MLE
実行時間	-
コード長	11,987 bytes
コンパイル時間	677 ms
コンパイル使用メモリ	82,176 KB
実行使用メモリ	856,960 KB
最終ジャッジ日時	2024-09-16 01:26:16
合計ジャッジ時間	4,130 ms
ジャッジサーバーID （参考情報）	judge3 / judge6
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	45 ms 55,680 KB
testcase_01	AC	45 ms 56,320 KB
testcase_02	AC	44 ms 55,552 KB
testcase_03	MLE	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code


import math
from collections import deque
import heapq
import sys
sys.setrecursionlimit(10**6)

# 便利函数のクラスです。クラスメソッドのみをもちます。


class ConvinientFunctions:

	@classmethod
	def round_four(cls, y, x, H, W):
		if y - 1 >= 0:
			yield (y - 1, x)
		if y + 1 < H:
			yield (y + 1, x)
		if x - 1 >= 0:
			yield (y, x - 1)
		if x + 1 < W:
			yield (y, x + 1)

	@classmethod
	def round_eight(cls, y, x, H, W):
		if y - 1 >= 0:
			yield (y - 1, x)
		if y + 1 < H:
			yield (y + 1, x)
		if x - 1 >= 0:
			yield (y, x - 1)
		if x + 1 < W:
			yield (y, x + 1)
		if y - 1 >= 0 and x - 1 >= 0:
			yield (y - 1, x - 1)
		if y - 1 >= 0 and x + 1 < W:
			yield (y - 1, x + 1)
		if y + 1 < H and x + 1 < W:
			yield (y + 1, x + 1)
		if y + 1 < H and x - 1 >= 0:
			yield (y + 1, x - 1)

	@classmethod
	def onedim_round_four(cls, n, H, W):
		# nはy*W+xです。
		# 上下
		if n - W >= 0:
			yield n - W
		if n + W <= (H - 1) * W + W - 1:
			yield n + W
		# 左
		if n % W != 0:
			yield n - 1
		# 右
		if n % W != W - 1:
			yield n + 1

	# Nを素因数分解するメソッドです。onebyoneをTrueにすると、[2,2,2,3,3...]のように同じ素因数も並べて出力します
	@classmethod
	def pfactorization(cls, N, onebyone=False):
		if N < 2:
			raise ValueError("forbbiden input")
		primelist = []
		if onebyone:
			for i in range(2, int(math.sqrt(N)) + 1):
				while N % i == 0:
					N = N // i
					primelist.append(i)
			if N != 1:
				primelist.append(N)
			return primelist
		else:
			for i in range(2, int(math.sqrt(N)) + 1):
				e = 0
				while N % i == 0:
					e += 1
					N = int(N // i)
				if e != 0:
					primelist.append([i, e])
			if N != 1:
				primelist.append([N, 1])
			return primelist

	# 拡張ユークリッドの互除法で逆元を求めています。p=modは素数でなくてもよいです。ただしaとmodはお互いに素である必要はあります。
	@classmethod
	def calc_inverse_element(cls, a, mod):
		def inverseelement(a, mod):
			if a == 1:
				return (1, 0)
			x, y = inverseelement(mod % a, a)
			return (y - x * (mod // a), x)
		x, y = inverseelement(a, mod)
		if x < 0:
			return x + mod
		else:
			return x

	@classmethod
	def my_factorial(cls, n, mod):
		# n!%modを高速に求める函数。ケタが大きいとかなり差がでます。必ずこれを使うこと。
		sol = 1
		for i in range(2, n + 1):
			sol = (sol * i) % mod
		return sol

	@classmethod
	# 組み合わせを求める函数。myfactと逆元を組み合わせて高速化されています。
	def my_combinations(cls, r, n, mod):
		return (cls.my_factorial(r, mod) * cls.calc_inverse_element((cls.my_factorial(n, mod) * cls.my_factorial(r - n, mod)) % mod, mod)) % mod


class UnionFind:
	def __init__(self, n):
		self.n = n
		self.parents = list(range(n))
		self.size = [1] * n

	# ある要素iのrootを返却します
	def find(self, i):
		while self.parents[i] != i:
			self.parents[i] = self.parents[self.parents[i]]
			i = self.parents[i]
		return i

	# iを含む木とjを含む木を結合します
	def union(self, i, j):
		if self.find(i) == self.find(j):
			# もとから連結なら何もしません。
			pass
		elif self.size[self.find(i)] < self.size[self.find(j)]:
			# parentsを買えるとfindで取得されるものが変わりますから、先にsizeを書き換えて、そのあとにparentsを変えないといけないことに注意してください。
			self.size[self.find(j)] = self.size[self.find(i)
												] + self.size[self.find(j)]
			self.parents[self.find(i)] = self.find(j)
		else:
			self.size[self.find(i)] = self.size[self.find(j)
												] + self.size[self.find(i)]
			self.parents[self.find(j)] = self.find(i)

	# i,jが同じグループにあるかどうかを判定します
	def is_same(self, i, j):
		if self.find(i) == self.find(j):
			return True
		else:
			return False

	# iが属する木のサイズを返却します
	def get_size(self, i):
		# iが属する部分木のサイズを取得します。
		return self.size[self.find(i)]


	#group[i]はiがどのグループに所属するかを持ちます。そういうリストを作るメソッドです。
	#O(n*alpha())かかります
	def create_group(self):
		group=self.n*[None]
		for i in range(self.n):
			group[i]=self.find(i)
		return group

	#rootのsetをかえします。このsetの長さはグループの数になります
	def get_roots(self):
		return set(self.create_group())


	#グループの数のdictを返します。rootをkeyにしてgroup[root]にはそのrootに所属する要素がsetではいっています
	def create_group_dict(self):
		group_dict={}
		for root in self.get_roots():
			group_dict[root]=set()

		for i in range(self.n):
			group_dict[self.find(i)].add(i)

		return group_dict



# グラフ構造を持ちます
class Graph:
	# Nが頂点の数です
	def __init__(self, N, dir: bool = False):
		self.N = N
		# 隣接リスト
		self.edges = [set() for _ in range(N)]
		# directedは有向グラフならTrue、無効グラフならFalseをいれます
		self.directed = dir
		# self.Eは辺の数です。最初は0で、createEdgeで辺を作るごとに加算します
		self.E = 0

	# 頂点間にedgeを作るメソッドです。
	def create_edge(self, u, v, dist=1):
		self.E += 1
		self.edges[u].add((dist, v))
		# 無効グラフなら逆も入れる
		if not self.directed:
			self.edges[v].add((dist, u))

	# startから各点までの距離distが与えられたとき、startからendまでの最短経路を計算するメソッドです（蟻本参照）
	# (start,...,end)という感じの形式でリターンします。
	# 採点経路復元は頂点O(N)か辺の数O(E)で復元できますから、短くなる方で勝手に復元するようにします(まだしてない)
	def recover_route(self, dist, start, end) -> deque:
		if start == end:
			# 同一点のときその点だけを返します。
			return deque([end])
		if dist[start] != 0:
			raise ValueError("distとstartに整合性がありません。")
		if dist[end] == -1:
			raise ValueError("endは到達不可能な点です")
		# 結果出力用のdequeです。endだけ入れておきます
		result = deque([end])
		# 逆順に更新していく必要があるので、有向グラフの場合には逆向きのedgeを作る必要があります。
		if self.directed:
			reverseEdge = [set() for _ in range(self.N)]
			# 有向グラフなら逆順のリストを作る
			for i in range(self.N):
				for e in self.edges[i]:
					reverseEdge[e[1]].add((e[0], i))
		else:
			# 無向グラフ
			reverseEdge = self.edges
		# O(E)で復元できます。startからひとつずつたどっていけばいいです。d[start]=d[i]-cost[start][i]となるような点があれば、そのiがstartの次の点です。これを繰り返します。
		next = end
		# endにつくまでループします
		while next != start:
			# nextから一歩で行ける点の中から次のnextをさがします
			for d, i in reverseEdge[next]:
				if dist[next] == dist[i] + d:
					# この等式がなりたつときe[1]は次のnextです。
					next = i
					result.appendleft(i)
					break
		return result

	# O(V+E)なので基本的に使えるときは最速です。
	# 幅優先探索で距離を計算するメソッドです。startpから各点への距離を計算します。
	# 到達不可能な点には-1が入ります
	# もちろん幅優先探索なので重みなしのときしか使えません。
	def calc_dist_by_BFS(self, start):
		seen = self.N * [False]
		dist = self.N * [-1]
		# 初期化
		queue = deque([start])
		seen[start] = True
		dist[start] = 0
		# 幅優先探索
		while len(queue) > 0:
			now = queue.pop()
			for d, nextp in self.edges[now]:
				if d != 1:
					# dは重みですが、重みが全部1のときのみ幅優先探索で距離を求められます
					raise ValueError("重みが1出ない場合幅優先探索はできません")
				if not seen[nextp]:
					queue.appendleft(nextp)
					seen[nextp] = True
					dist[nextp] = dist[now] + 1
		return dist

	# O(E*log(N))
	# ダイクストラ。重みありなら最速です。ただし負の辺があるときは使えません。
	def calc_dist_by_Dijkstra(self, start):
		dist = [-1] * self.N
		# ヒープキュー
		hq = []
		# 確定済みorNot
		fixed = [False] * self.N
		# 初期化
		dist[start] = 0
		fixed[start] = True
		for d in self.edges[start]:
			heapq.heappush(hq, d)
		while len(hq) > 0:
			nowd, nowi = heapq.heappop(hq)
			# 確定済みの点なら何もしない
			if fixed[nowi]:
				continue
			# nowpを確定させる
			dist[nowi] = nowd
			fixed[nowi] = True
			for d, i in self.edges[nowi]:
				heapq.heappush(hq, (d + dist[nowi], i))
		return dist

	# O(N^3)
	# ワーシャルフロイド
	# 負の閉路がある場合は文字列で"NEGATIVE CYCLE"を返します
	# ダイクストラよりも遅いが、負の辺があっても負の閉路がない限り対応できるというメリットがある。またダイクストラと違い始点を定めずにいっきに全部の点の組み合わせの最短距離がでるところもメリットではある（全部の組み合わせの最短距離もダイクストラのほうがはやいが）
	# なのでこのメソッドもstartは不要である。
	def calc_dist_by_WarshallFloyd(self):
		# distWF[i][j]はiとjの間の最短距離です。初期化は同一点は0で他はinf
		distWF = [[0 if i == j else float('inf') for i in range(
			self.N)] for j in range(self.N)]
		# 次に直接隣接している辺についてdistWFに情報をいれます
		for i in range(self.N):
			for d, j in self.edges[i]:
				distWF[i][j] = d
		for k in range(self.N):
			for i in range(self.N):
				for j in range(self.N):
					distWF[i][j] = min(
						distWF[i][j], distWF[i][k] + distWF[k][j])
		# 対角成分に負があったら負の閉路があります
		if sum([distWF[i][i] for i in range(self.N)]) < 0:
			return "NEGATIVE CYCLE"
		else:
			return distWF

	# トポロジカルソートするメソッドです。閉路がなくてかつ有向のグラフ（DAG）であればトポロジカルソートが存在します。必要十分です。
	# O(N+E)です
	def find_topologicalorder(self):
		# まず無向グラフならだめです。
		if not self.directed:
			raise ValueError("無向グラフにはトポロジカルオーダーは存在しません")
		# 結果用のdeque
		result = deque([])
		# 探索済みorNot
		seen = [False] * self.N

		# 再帰処理で見つけます。nの次の点を探索しに行くメソッドです。
		def rec(n):
			# globalじゃなくてnonlocalで書かないとだめよ
			nonlocal result
			nonlocal seen
			# nを探索済みにする
			seen[n] = True
			# nから一歩で行ける未探索の点を探索しにいく
			for d, nextp in self.edges[n]:
				if not seen[nextp]:
					rec(nextp)
					# 帰りがけにresultに入れる
					result.appendleft(nextp)
		# 初期値で実行
		for i in range(self.N):
			if not seen[i]:
				rec(i)
				result.appendleft(i)

		# 結果を返す
		return result


#################################################################
#　　　　　　　　　　 ∧＿∧
#　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
#　　　　 （ ´_ゝ`）　/　 ⌒i
#　　　　／　　　＼　 　  |　|
#　　　 /　　 /￣￣￣￣/　　|
#　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
#　 　　　＼/＿＿＿＿/　（u　⊃
#################################################################
N=int(input())
R=list(map(lambda x:int(x)-1,input().split()))
#有向グラフにして幅優先で距離を求める

G=Graph(N,dir=True)
for i in range(N-1):
	for j in range(i+1,R[i]+1):
		#iからjにedgeをつくる
		G.create_edge(i,j)

#幅優先
dist=G.calc_dist_by_BFS(0)
print(dist[-1])
yukicoder

結果

テストケース

ソースコード
