結果
| 問題 | No.1868 Teleporting Cyanmond |
| ユーザー |
 flora
|
| 提出日時 | 2022-03-11 22:32:16 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 216 ms / 2,000 ms |
| コード長 | 7,799 bytes |
| コンパイル時間 | 623 ms |
| コンパイル使用メモリ | 82,432 KB |
| 実行使用メモリ | 96,256 KB |
| 最終ジャッジ日時 | 2024-09-16 02:54:44 |
| 合計ジャッジ時間 | 5,572 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
# 実装上の工夫：
# 非再帰（パフォーマンス（メモリ、時間ともに）上微妙にいい、stackで書いたものとかではない）
# nodeの数を2のべきにしない（微妙にメモリ節約。あと無駄なものを持たなくていいので微妙に気持ちがいい）
# またnodeの数を2のべきにしなくていいと、identityの指定が不要になり、うれしい（ただしidentityの指定を不要にするとqueryの実装はちょっとだけ複雑になる）。
# 交換法則は仮定しない（ただし結合法則は仮定される、例えば引き算や割り算は結合法則が満たされないためだめ、行列の積とかはいける）
# 1-indexed。0-indexedでも実装できますし最初はそうしましたが、1-indexedだと親子のindexを得るのを全部bit演算でできるのではやくなります。比べてみところ以外と無視できないほど変わったので1-indexedにしました。遅い方を採用する意味はまったくないので
# よく使うoperatorと単位元のリスト。
"""
最小値
operator=min, identity=float('inf')
最大値
operator=max, identity = -float('inf')
区間和
operator=lambda x, y: x + y,identity = 0
区間積
operator=lambda x, y: x * y, identity = 1
最大公約数
operator=math.gcd, identity = 0
複数の要素をもたせたいときの区間和。ベクトルの和にする。このときはupdate(k,x)のxにも同じ次元のリストを入れます。
operator=lambda A, B: [a+b for a,b in zip(A,B)]
"""
# セグメント木のクラス。構築O(N),update O(log(N)),query O(log(N))
class SegmentTree:
# O(N)
# 初期化です。デフォルトはRMQにしてあります。適切なoperatorを指定してください。
def __init__(self, A, operator=min):
"""
A:いま扱う配列
operator:いま考える二項間演算子。交換法則は仮定しない
identity:operatorに対応する単位元
"""
# ちなみに1-indexでnode iの親:i//2,左の子:2*i,右の子:2*i+1です。
# ただしbit演算のほうが速いので、親:i>>1,左の子:i<<1,右の子i<<1|1と書くことにする。
# セグメント木は完全二分木ですから、リストで木の要素を管理することができます。
# 要素数
self.N = len(A)
# operator
self.operator = operator
# 木を成すサイズ2N-1の配列を作る。このときidentityで初期化する。ちなみに2*NよりもN+Nのほうがかすかにはやいです。
self.tree = [None] * (self.N + self.N)
# 初期化は葉、すなわちtreeの後ろからN個の部分にAの値を配置する。
for i, a in enumerate(A, self.N):
self.tree[i] = a
# たつの子にoperatorを作用したものを親にするという操作を繰り返す。ここでindexの大きい方からやっていけば葉から上にたどることができる。
for i in range(self.N - 1, 0, -1):
# [1,N-1]の逆順ループ。親の値をふたつの子のoperatorから決めます。ここで左右という順番でいれないとだめなことには注意ね。
self.tree[i] = self.operator(
self.tree[i << 1], self.tree[i << 1 | 1])
# O(log(N))
# Aのk番目の値A[k]をxに変更します。
def update(self, k, x):
# A[k]に対応するのはtree[k+self.N]ですので、そこから初めてrootに到達するまで親に向かいます
k += self.N
# 更新
self.tree[k] = x
# rootはk=1ですので正である間ループすればOKです
while k > 1:
# 親のindex。
k >>= 1
# 親の値を書き直す
self.tree[k] = self.operator(
self.tree[k << 1], self.tree[k << 1 | 1])
# O(log(N))
# 半開区間[left,right)において、operatorで指定された演算の値を返します。
# ただしleft,rightにNoneを入力すると、例えばleft=Noneにするといまありうる一番左を指定します
def query(self, left, right):
if left is None:
left = 0
if right is None:
right = self.N
# left,rightに対応するtreeのindex
left += self.N
right += self.N
# 左右の値
vl = None
vr = None
# 非再帰の実装ではleaf側からrootに向かっていくのがポイントです。[2]の図がわかりやすいです。
# [left,right)の外側から値を確定させていくイメージ。どんどん内側によせていき、leftとrightが重なったら終わり
while left < right:
if left & 1:
# leftが奇数なら、その区間を確定させる
if vl is None:
# 何もなければその値自体を入れる
vl = self.tree[left]
else:
# あればもとの値と演算
vl = self.operator(vl, self.tree[left])
# 次は右の親に移動するのでLを足しておく
left += 1
if right & 1:
# rightが奇数なら、-1してから確定させる
right -= 1
if vr is None:
vr = self.tree[right]
else:
# 順番には注意ね
vr = self.operator(self.tree[right], vr)
# 親を見る
left >>= 1
right >>= 1
# 最後にvlとvrの演算を返す。ただしどちらもNoneなら、区間が空集合になっているのでNoneを返す。片側がNoneならNoneじゃないほうを返すことにする。
if vl is None and vr is None:
return None
elif vl is None:
return vr
elif vr is None:
return vl
else:
# ここでも演算の順番に注意
return self.operator(vl, vr)
# O(log(N))
# Aのk番目の値A[k]にxを加算します。すなわちA[k]+=xと同じ操作です。
# 実装はupdateとほぼ同じ。
def add(self, k, x):
k += self.N
# 加算
self.tree[k] += x
while k > 1:
k >>= 1
self.tree[k] = self.operator(
self.tree[k << 1], self.tree[k << 1 | 1])
# O(1)
# A[k]と同じ。もとのAのk番目の値を取得します。
def get(self, k):
return self.tree[k + self.N]
# O(1)
# もとのAはself.treeのself.tree[self.N: 2*self.N]の部分に埋め込まれています。
# その範囲を半開区間で返します
def original_range(self):
return self.N, 2 * self.N
N=int(input())
R=list(map(lambda x:int(x)-1,input().split()))
#グラフの問題的に求めたいが、edgeが多いのでそのまま探索すると時間がかかりすぎる。
#後ろから順番にNへの最短距離をもとめていく。DAGであることをイメージして効率的に探索できる
#iからN-1の距離をdist[i]とする
#後ろから調べて、dist[i]は[i+1,R[i]]の最小値を取ればいい。これをセグ木でやる。
#初期値はN-1だけが0ほかはinf
distseg=SegmentTree([float('inf')]*(N-1)+[0],operator=min)
for i in reversed(range(N-1)):
#iからN-1の最小値を計算して
#これはすなわち[i+1,R[i]]の最小値を計算すればOK
mindist=distseg.query(i+1,R[i]+1)
#mindist+1をそこの距離として更新する
distseg.update(i,mindist+1)
#最後まで求めて0の値が答えです
print(distseg.get(0))