結果
| 問題 |
No.1868 Teleporting Cyanmond
|
| コンテスト | |
| ユーザー |
 flora
|
| 提出日時 | 2022-03-11 21:27:42 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 11,987 bytes |
| コンパイル時間 | 140 ms |
| コンパイル使用メモリ | 82,444 KB |
| 実行使用メモリ | 848,908 KB |
| 最終ジャッジ日時 | 2024-09-16 01:30:51 |
| 合計ジャッジ時間 | 3,793 ms |
|
ジャッジサーバーID （参考情報） |
judge6 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | MLE * 1 -- * 24 |
ソースコード
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])