【逐次更新】Heap や stack を filter して pop する実装を要求する問題リスト - ブログ名
逐次更新です。該当する問題を見つけたら @ngtkana_kyopro までお知らせいただけると幸いです。 問題リスト 問題 container description ARC 181 D - Prefix Bubble Sort heap pop_while ARC 001 D - レースゲーム stack これも pop_while 系ですがライブラリで対応するのはキビシそうです ライブラリ use std::collections::BinaryHeap; use std::iter::FusedIterator; pub trait Popmore: Sized { type Item; fn pop(&mut self) -> Option<Self::Item>; fn peek(&self) -> Option<&Self::Item>; fn pop_if(&mut sel
円環上の DP を行列のトレースで考える - ブログ名
概要 円環上の DP が問題は、DP を行列積で書くことで行列のトレースになることが多いのですが、立て続けに 2 問お見かけしたため共有です。 両方とも辺被覆の話題でしたが、たまたまでしょうかね。 本文 ABC 247 F - Cards 問題リンク 長さ $n ( \ge 1)$ のサイクルグラフの辺被覆の個数 $$ \mathop{\mathrm{Tr}} \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} ^ n $$ ABC 251 E - Takahashi and Animals 問題リンク 重み $A _ 0, A _ 1, \dots, A _ { n - 1 }$ の辺を持つサイクルグラフの、最小重み辺被覆 $$ \mathop{\mathrm{Tr}} _ { \oplus, \odot } \bigodot _ { 0 \le i
Splay 木の計算量解析 - ブログ名
Splay 木概論 Splay 木の基本操作 $\newcommand {\rank}{\mathtt{rank}}$Splay 木 $T$ は $0 ≤ Φ(T) ≤ n \log(n)$（ただし $n$ は節点数）なるポテンシャル $Φ(T)$ のもと、次の操作ができる二分木です。 クエリ 引数 事前条件 効果 ポテンシャル増分 最悪時間計算量 $\mathtt{splay}$ 節点 $u$ なし inorder を保って $u$ が根になるように変形する $O(\log(n)) - h(u)$ $O(h(u))$ 従って次のことがわかります。 $\mathtt{splay}$ をばかりを $q$ 回連続して呼んだ場合、$O( (n + q)\log(n))$ 時間かかります。（なお実コストのほうで解析すると $O(nq)$ であることもわかり、$q = o(\log(n))$ のとき
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
