結果
問題 |
No.345 最小チワワ問題
|
ユーザー |
![]() |
提出日時 | 2025-08-13 17:52:52 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,540 bytes |
コンパイル時間 | 488 ms |
コンパイル使用メモリ | 82,448 KB |
実行使用メモリ | 62,156 KB |
最終ジャッジ日時 | 2025-08-13 17:52:57 |
合計ジャッジ時間 | 3,907 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 WA * 1 |
ソースコード
from collections.abc import Iterable from enum import IntEnum, auto from functools import cache class E(IntEnum): S = 0 C = auto() W1 = auto() W2 = auto() def nexts(self): match self: case E.S: return [E.C] case E.C: return [E.W1] case E.W1: return [E.W2] case E.W2: return [] 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, *, is_reset=True): dp = [e] * len(E) for k, v in init.items(): dp[k] = v for x in xs: pp = [e] * len(E) if is_reset else dp.copy() 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: if fm_v == (INF, INF): return False return True def op(to: E, to_v, fm: E, fm_v, iv): res = (INF, INF) d, p = fm_v[0], -fm_v[1] # (距離, 文字インデックス) i, v = iv match to: case E.C if v == 'c': res = min(res, (0, -i)) case E.W1 | E.W2 if v == 'w': res = min(res, (d+(i-p), -i)) return min(to_v, res) INF = 1 << 60 S = input() dp = state_dp(enumerate(S), op, (INF, INF), {E.S: (0, 0)}, is_reset=False) ans, _ = dp[E.W2] if ans == INF: print(-1) else: print(ans+1)