結果

問題 No.838 Noelちゃんと星々3
コンテスト
ユーザー norioc
提出日時 2025-06-06 03:20:04
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 141 ms / 2,000 ms
コード長 1,391 bytes
コンパイル時間 1,152 ms
コンパイル使用メモリ 81,720 KB
実行使用メモリ 93,716 KB
最終ジャッジ日時 2025-06-06 03:20:09
合計ジャッジ時間 3,873 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections.abc import Iterable
from enum import IntEnum, auto
from functools import cache


class E(IntEnum):
    A = 0
    B = auto()

    def nexts(self):
        match self:
            case E.A: return [E.A, E.B]
            case E.B: return [E.A]

        assert False

    @staticmethod
    @cache
    def states():
        res = []
        for fm in E:
            for to in fm.nexts():
                res.append((fm, to))

        return res


def state_dp(xs: Iterable, op, e, init: dict):
    dp = [e] * len(E)
    for k, v in init.items():
        dp[k] = v

    for x in xs:
        pp = [e] * len(E)
        dp, pp = pp, dp
        for fm, to in E.states():
            if not is_valid(to, pp[fm], x): continue
            dp[to] = op(to, dp[to], fm, pp[fm], x)

    return dp


def is_valid(to: E, fm_v, v) -> bool:
    return True


def op(to: E, to_v, fm: E, fm_v, iv):
    i, v = iv
    if i == N-1:
        if to == fm:
            return min(to_v, fm_v)
        return to_v

    match to:
        case E.A:  # 合わせる
            return min(to_v, fm_v + abs(Y[i] - Y[i+1]))
        case E.B:  # 合わせない
            assert fm == E.A
            return min(to_v, fm_v)

    assert False


INF = 1 << 60
N = int(input())
Y = list(map(int, input().split()))
Y.sort()

ivs = list(enumerate(Y))
dp = state_dp(ivs, op, INF, {E.B: 0})
ans = dp[E.A]
print(ans)
0