#1137159 (PyPy3) No.3393 Move on Highway

• 問題: No.3393 Move on Highway
• ユーザー: navel_tos
• 提出日時: 2025-11-29 12:55:15
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 1,440 ms / 3,000 ms
• コード長: 15,125 bytes
• コンパイル時間: 231 ms
• コンパイル使用メモリ: 82,344 KB
• 実行使用メモリ: 131,192 KB
• 最終ジャッジ日時: 2025-11-29 12:55:49
• 合計ジャッジ時間: 31,305 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 33

ソースコード

#yukicoder570

'''
#A-D 省略

#E
#入力受取 Aをソート
N, M, K = map(int, input().split())
A = sorted(int(Ai) for Ai in input().split())
MOD = 998244353

#sub[i]: ドミノiとの大きさの差がK以下の[Lt, Rt)
sub: list[tuple[int, int]] = [(0, 0)] * N
for i in range(N):
    for Lt in range(i - 1, -2, -1):
        if Lt == -1 or abs(A[Lt] - A[i]) > K:
            break
    Lt += 1
    for Rt in range(i + 1, N + 1, +1):
        if Rt == N or abs(A[Rt] - A[i]) > K:
            break
    sub[i] = (Lt, Rt)

#累積和DP
DP: list[int] = [1] * N
C: list[int] = [0] * (N + 1)
for _ in range(M - 1):
    for i in range(N):
        C[i + 1] = (C[i] + DP[i]) % MOD
    for i, (Lt, Rt) in enumerate(sub):
        DP[i] = C[Rt] - C[Lt]
ans: int = sum(DP) % MOD
if ans < 0:
    ans += MOD
print(ans)


#F
#Rolling Hash
#Reference: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
from random import randrange as _RollingHash_randrange
_RollingHash_base = _RollingHash_randrange(~ (- 1 << 61))
class RollingHash:
    \'''
    Rolling Hash for codon, PyPy3
    法2 ** 61 - 1の下、文字列のハッシュを計算します。

    base: 基数 指定がない場合、[0, 2 ** 61 - 1)から乱択
    \'''
    base: int
    _builded: bool
    _B: list[int]
    _H: list[int]
    __slots__ = ('base', '_builded', '_B', '_H')
    def __init__(self, base: int = -1) -> None:
        self.base: int = base if 0 <= base < 0x1FFFFFFFFFFFFFFF else _RollingHash_base
        self._B: list[int] = [1]
    #内部関数
    def _mul(self, x: int, y: int) -> int:
        div_x, mod_x = x >> 31, x & 0x7FFFFFFF
        div_y, mod_y = y >> 31, y & 0x7FFFFFFF
        m: int = div_x * mod_y + div_y * mod_x
        ans: int = 2 * div_x * div_y + (m >> 30) + ((m & 0x3FFFFFFF) << 31) + mod_x * mod_y
        if ans < 0x1FFFFFFFFFFFFFFF:
            return ans
        div_ans, mod_ans = ans >> 61, ans & 0x1FFFFFFFFFFFFFFF
        ans2: int = div_ans + mod_ans
        return ans2 if ans2 < 0x1FFFFFFFFFFFFFFF else ans2 - 0x1FFFFFFFFFFFFFFF
    def _build_B(self, x: int) -> None:
        if x >= len(self._B):
            if (x + 1) / len(self._B) < 1.1:
                for _ in range(x + 1 - len(self._B)):
                    self._B.append(self._mul(self._B[-1], self.base))
            else:
                new_B: list[int] = [1] * (x + 1)
                for i, Bi in enumerate(self._B):
                    new_B[i] = Bi
                for i in range(len(self._B), x + 1):
                    new_B[i] = self._mul(new_B[i - 1], self.base)
                self._B = new_B
    def _RH(self, A, k: int) -> list[int]:
        ans: list[int] = [0] * (len(A) - k + 1)
        cnt: int = 0
        pow_base: int = 1
        for i in range(k):
            Ai: int = ord(A[i]) if isinstance(A[i], str) else A[i]
            cnt: int = self._mul(cnt, self.base) + Ai
            if cnt >= 0x1FFFFFFFFFFFFFFF:
                cnt -= 0x1FFFFFFFFFFFFFFF
            pow_base: int = self._mul(pow_base, self.base)
        ans[0] = cnt
        for Li in range(len(A) - k):
            A_back: int = ord(A[Li    ]) if isinstance(A[Li    ], str) else A[Li    ]
            A_now:  int = ord(A[Li + k]) if isinstance(A[Li + k], str) else A[Li + k]
            cnt: int = self._mul(cnt, self.base) + A_now - self._mul(A_back, pow_base)
            if cnt >= 0x1FFFFFFFFFFFFFFF:
                cnt -= 0x1FFFFFFFFFFFFFFF
            if cnt < 0:
                cnt += 0x1FFFFFFFFFFFFFFF
            ans[Li + 1] = cnt
        return ans
    def _build_array(self, A) -> None:
        self._builded: bool = True
        self._H: list[int] = [0] * (len(A) + 1)
        self._build_B(len(A))
        for i, Ai in enumerate(A):
            Bi: int = ord(Ai) if isinstance(Ai, str) else Ai
            self._H[i + 1] = self._mul(self._H[i], self.base) + Bi
            if self._H[i + 1] >= 0x1FFFFFFFFFFFFFFF:
                self._H[i + 1] -= 0x1FFFFFFFFFFFFFFF

    #基本機能
    def hash(self, A) -> int:
        '現在の基数を用い、Aのハッシュ値を計算します。'
        ans: int = 0
        for Ai in A:
            Bi: int = ord(Ai) if isinstance(Ai, str) else Ai
            ans: int = self._mul(ans, self.base) + Bi
            if ans >= 0x1FFFFFFFFFFFFFFF:
                ans -= 0x1FFFFFFFFFFFFFFF
        return ans
    def rolling_hash(self, A, k: int) -> list[int]:
        '0 <= i < len(A) - k + 1 において、A[i: i + k]のハッシュ値を計算します。'
        assert 0 <= k <= len(A)
        return self._RH(A, k)
    def build(self, A) -> None:
        'Aのハッシュの前計算を行います。'
        self._build_array(A)
    def fold(self, Lt: int, Rt: int) -> int:
        'build(A)によるAの前計算の下、A[Lt: Rt]のハッシュをO(1)で取得します。'
        assert self._builded == True
        assert 0 <= Lt and Rt < len(self._H)
        if Lt >= Rt:
            return 0
        ans: int = self._H[Rt] - self._mul(self._H[Lt], self._B[Rt - Lt])
        return ans if ans >= 0 else ans + 0x1FFFFFFFFFFFFFFF


#入力受取
N = int(input())
A = [int(Ai) for Ai in input().split()]

#D[i]: A[i + 1] - A[i]
D: list[int] = [A[i + 1] - A[i] for i in range(N - 1)]
n: int = len(D)


#Dの回文の個数を数える  manacherでO(N) RHでO(NlogN)
#RHの制約上、入力は[0, 2**61 - 1)に収めないといけないのでDを補正
def count_palindrome_RH(D):
    ans: int = 0
    base: int = 100
    RH = RollingHash(base)
    revRH = RollingHash(base)
    for i in range(n):
        D[i] %= ~(-1 << 61)
        if D[i] < 0:
            D[i] += ~(-1 << 61)  #for codon
    RH.build(D)
    revRH.build(D[::-1])
    #1. D[i]を中心とする奇数長の回文
    for i in range(n):
        #回文半径をd文字(d >= 1)としたとき、D[i: i + d] == rev(D[i + 1 - d: i + 1]) を判定
        #D[Lt: Rt] → revD[n - Rt: n - Lt] に注意
        ok: int = 1
        ng: int = min(n - i + 1, i + 2)
        while abs(ok - ng) > 1:
            mid: int = (ok + ng) >> 1
            if RH.fold(i, i + mid) == revRH.fold(n - (i + 1), n - (i + 1 - mid)):
                ok = mid
            else:
                ng = mid
        ans += ok

    #2. D[i]とD[i + 1]の間を中心とする偶数長の回文
    for i in range(n - 1):
        #回文半径をd文字(d >= 0)としたとき、D[i + 1: i + 1 + d] == rev(D[i + 1 - d: i + 1]) を判定
        ok: int = 0
        ng: int = min(n - i, i + 2)
        while abs(ok - ng) > 1:
            mid: int = (ok + ng) >> 1
            if RH.fold(i + 1, i + 1 + mid) == revRH.fold(n - (i + 1), n - (i + 1 - mid)):
                ok = mid
            else:
                ng = mid
        ans += ok
    return ans


#TLEしたのでmanacher
#Reference: https://tjkendev.github.io/procon-library/python/string/manacher.html
def manacher(S) -> list[int]:
    \'''
    S: str | list[str] | list[int] として、Sの最長回文を求めます。
    A[i << 1]: S[i]を中心とする奇数長の最大回文
    A[i << 1 | 1]: S[i + 1: i + 1]を中心とする偶数長の最大回文

    制約: S[i]はstr または 非負整数
    \'''
    C: list[int] = [-1] * (2 * len(S) - 1)
    for i, s in enumerate(S):
        Si: int = ord(s) if isinstance(s, str) else int(s)
        C[i << 1] = Si
    N: int = len(C)
    A: list[int] = [0] * N
    i = j = 0
    while i < N:
        while j <= i < N - j and C[i - j] == C[i + j]:
            j += 1
        A[i] = j
        k: int = 1
        while j - A[i - k] > k <= i < N - k:
            A[i + k] = A[i - k]
            k += 1
        i += k
        j -= k
    for i in range(N):
        if i & 1 == A[i] & 1:
            A[i] -= 1
    return A


#ans: int = N + count_palindrome_RH(D)
ans: int = N + sum(-(-Ai >> 1) for Ai in manacher(D))
print(ans)
'''

#G
#dijkstra SegTree for PyPy3 (codonはint限定)
class dijkstra_SegTree:
    N: int
    inf: int
    _node: list[int]
    _node_id: list[int]
    _fstar: list[int]
    _size: int
    _head: int
    _tail: int
    _free: int
    __slots__ = ('N', 'inf', '_node', '_node_id', '_fstar',
                 '_size', '_head', '_tail', '_free')
    def __init__(self, N: int, dist_inf: int = 9 * 10 ** 18) -> None:
        assert 0 <= N
        self.N: int = N
        logN: int = 0 if N <= 1 else len(bin(N - 1)) - 2  #max(0, N - 1).bit_length()
        self.inf: int = dist_inf
        self._node: list[int] = [self.inf for _ in range((1 << logN) + N + 1 + N)]
        self._node_id: list[int] = [-1 << 32 | i for i in range(1, N + 1)]
        self._fstar: list[int] = [0] * ((1 << logN) + N)
        self._size: int = 1
        self._head = self._tail = self._free = 0
    #内部関数
    def _clear_node(self) -> None:
        for i in range(len(self._node)):
            self._node[i] = self.inf
        for i in range(len(self._node_id)):
            self._node_id[i] = -1 << 32 | (i + 1)
        for i in range(len(self._fstar)):
            self._fstar[i] = 0
        self._size: int = 1
        self._head = self._tail = self._free = 0
    def _lazy_update(self) -> int:  #待機キューを遅延更新 距離最小の頂点を報告 なければ-1
        self._fstar[0], tail = self._head, self._tail
        head = self._head = self._tail = 0  #head・tailをローカル束縛してから初期化
        while head != tail:
            self._fstar[head], head = 0, self._fstar[head]
            if head != 1:
                d: int = self._node[head]
                p: int = head >> 1
                if d < self._node[p]:
                    self._node[p] = d
                    if self._fstar[p] == 0:
                        self._fstar[tail] = self._fstar[p] = p
                        tail = p
        self._fstar[head] = 0  #assert all(self._fstar[i] == 0 for i in range(len(self._fstar)))
        cur: int = 1
        d: int = self._node[1]
        if d == self.inf:
            return -1
        while cur < self._size:
            cur <<= 1
            if self._node[cur] > d:
                cur |= 1
        return self._node_id[cur ^ self._size] & 0xFFFFFFFF

    #特殊メソッド・特殊関数
    def __len__(self) -> int:  #頂点数
        return self.N
    def __repr__(self) -> str:  #現在の各頂点の最小重み
        return f'{self.__class__.__name__}({self._node[-1: ~ self.N: -1]})'
    def __iter__(self):  #-> generator[int]
        'for now in self: で、 待機キューが空になるまでself.pop()を実行します。'
        now: int = self.pop()
        while now != -1:
            yield now
            now: int = self.pop()
    def clear(self) -> None:
        '配列を代入で初期化します。メモリ消費量を削減したい際にご利用ください。'
        self._clear_node()

    #基本機能
    def chmin(self, now: int, value: int) -> None:
        'dist(now) > value の時だけ、dist(now) ← value と更新し、待機キューにpushします。'
        if now < 0:
            now += self.N
        assert 0 <= now < self.N
        if value >= self._node[~ now]:
            return
        cur: int = self._node_id[now] >> 32
        if cur == -1:
            if self._free == self._size:
                for i in range(self._size, self._size << 1):
                    self._node[i + self._size] = self._node[i]
                    self._node[i] = self.inf
                for i in range(self._size + (-(- self._size >> 1)) - 1, 0, -1):
                    self._node[i] = min(self._node[i << 1], self._node[i << 1 | 1])
                for i in range(self._size):
                    self._node_id[self._node_id[i] & 0xFFFFFFFF] += self._size << 32
                for i in range(self._size, self._size << 1):
                    if self._fstar[i] != 0:
                        self._fstar[i + self._size] = self._fstar[i] + self._size
                        self._fstar[i] = 0
                if self._head != 0:
                    self._head += self._size
                    self._tail += self._size
                self._size <<= 1
            t: int = self._free
            cur: int = t | self._size
            self._node_id[now] = cur << 32 | (self._node_id[now] & 0xFFFFFFFF)
            self._free: int = self._node_id[t] & 0xFFFFFFFF
            self._node_id[t] = self._node_id[t] >> 32 << 32 | now
        self._node[~ now] = self._node[cur] = value
        if self._fstar[cur] == 0:
            if self._head == 0:
                self._head = self._tail = cur
            self._fstar[cur], self._head = self._head, cur
    def pop(self) -> int:
        '待機キュー内の重み最小の頂点をどれか1つ取り出します。存在しない場合、-1とします。'
        now: int = self._lazy_update()
        if now == -1:
            return -1
        cur: int = self._node_id[now] >> 32
        w = self._node[cur] = self.inf
        self._node_id[now] = -1 << 32 | (self._node_id[now] & 0xFFFFFFFF)
        t: int = cur ^ self._size
        self._node_id[t] = self._node_id[t] >> 32 << 32 | self._free
        self._free: int = t
        while cur != 1:
            d: int = self._node[cur ^ 1]
            if w > d:
                w = d
            cur >>= 1
            self._node[cur] = w
        return now
    def find_top(self) -> tuple[int, int]:
        '''
        待機キュー内の重み最小の頂点nowをどれか1つ選び、(dist(now), now)を返します。
        待機キューが空になる場合、(inf, now)を返します。
        popと違い、この関数では待機キューから頂点nowの取り出しは行いません。参照だけです。
        '''
        now: int = self._lazy_update()
        return (self.inf, now) if now == -1 else (self._node[~ now], now)
    def dist(self, now: int) -> int:
        '頂点nowの現在の重みを返します。'
        if now < 0:
            now += self.N
        assert 0 <= now < self.N
        return self._node[~ now]


#入力受取
input = __import__('sys').stdin.readline
N, M, C = list(map(int, input().split()))
G: list[list[int]] = [[] for _ in range(N)]
for _ in range(M):
    Ui, Vi, Wi = map(int, input().split())
    Ui, Vi = Ui - 1, Vi - 1
    G[Ui].append(Vi << 32 | Wi)
    G[Vi].append(Ui << 32 | Wi)

#1. 頂点0からダイクストラ
dST = dijkstra_SegTree(N << 1)
dST.chmin(0, 0)
for now in dST:
    for x in G[now]:
        nxt, Wi = x >> 32, x & 0xFFFFFFFF
        dST.chmin(nxt, dST.dist(now) + Wi + C)
DP: list[int] = [dST.dist(now) for now in range(N)]

#2. DP[i << 1 | f]: 頂点N - 1から頂点iへの最短路であって、チケットをf := 使用済/未使用
dST.clear()
dST.chmin(N - 1 << 1 | 0, 0)
for y in dST:
    now, f = y >> 1, y & 1
    for x in G[now]:
        nxt, Wi = x >> 32, x & 0xFFFFFFFF
        dST.chmin(nxt << 1 | f, dST.dist(y) + Wi + C)
        if f == 0:
            dST.chmin(nxt << 1 | 1, dST.dist(y) + 0 + C)

ans: list[str] = [''] * (N - 1)
for now in range(1, N):
    ans[now - 1] = str( min(DP[N - 1], DP[now] + min(dST.dist(now << 1), dST.dist(now << 1 | 1))) )
__import__('sys').stdout.write('\n'.join(ans))