noshi91のメモ

データ構造のある風景

2023-02-01から1ヶ月間の記事一覧

Universal Cup. Stage 5: Osijek. D Distinct Subsequences

概要 問題の解法と、巧妙な (当社比) 定数倍高速化の方法を書く。 この高速化の方法は、heno239 さんに教えてもらった方法を式変形で導出しようとしていたら思いついた。 heno239 さんの手法は理解できていないので説明できないが、恐らく最終的に得られる式…

部分列 DP メモ

を長さ の文字列とする。 の部分列が何種類あるか数え上げる。 DP 定義 の部分列であって で終わるものの種類数 の部分列の種類数 (空列含む) DP 遷移 \begin{align} \text{dp} \lbrack i + 1 \rbrack \lbrack c \rbrack &= \begin{cases} \text{sum} \lbrac…

簡易版 LARSCH Algorithm

概要 LARSCH Algorithm の簡易版を思いついたので説明する。 時間計算量 だが実装や仕組みが単純で、コスト関数が sliding window でしか計算できない場合にも有用。 問題設定 を Monge なコスト関数として、 \begin{align} \text{dp} \lbrack i \rbrack = \…