#745286 (PyPy3) No.1868 Teleporting Cyanmond

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
# 実装上の工夫：
# 非再帰（パフォーマンス（メモリ、時間ともに）上微妙にいい、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))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX