[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

259: 05/22(木)02:20 AA×


[240|320|480|600|100%|JPG|べ|ﾚｽ栞|ﾚｽ消]
259: [sage] 2025/05/22(木) 02:20:43.20 はい、承知いたしました。Skew Heapの償却O(log n)解析（RightHeavyノードをポテンシャルとして使用）を記述します。 Skew Heapの償却O(log n)解析 (RightHeavyポテンシャル) 1. 定義 - 部分木のサイズ size(x): ノード x を根とする部分木に含まれるノードの総数。 - 左の子 lc(x)、右の子 rc(x): ノード x のそれぞれ左の子、右の子。 - RightHeavyノード: ノード x が右の子 rc(x) を持ち、かつ size(rc(x)) > size(lc(x)) である場合、ノード x は RightHeavy であると定義します。（左の子がない場合は size(lc(x))=0 とします。） - ポテンシャル関数 Φ(H): ヒープ H に含まれるRightHeavyノードの総数。 2. Meld操作の償却解析 Skew Heapの主な操作である meld(H1, H2) について考えます。簡単のため、H1 の根のキーが H2 の根のキー以下であると仮定します（そうでない場合は H1 と H2 を交換します）。H1 の根を x_0 とします。 Meld操作は、x_0 から始まる右パス P = (x_0, x_1, ..., x_k) に沿って再帰的に処理を行います。各ノード x_i (0 <= i <= k) において、以下の処理が行われます： 1) x_i の元の右の子 R_i (= x_{i+1} または H2 の一部) と、H2 の残り（または R_i が H2 そのものの場合もある）を再帰的にmeldし、その結果を x_i の新しい右の子 R'_i とします。 2) x_i の元々の左の子 L_i と、新しい右の子 R'_i をスワップします。つまり、meld後の x_i の左の子は R'_i、右の子は L_i となります。 このパスの長さ（スワップが行われる回数）を m=k+1 とすると、meld操作の実際のコスト C は O(m) です。 http://medaka.5ch.net/test/read.cgi/prog/1747628087/259
はい承知いたしました の償却 解析ノードをポテンシャルとして使用を記述します の償却 解析 ポテンシャル 定義 部分木のサイズ ノード を根とする部分木に含まれるノードの総数 左の子 右の子 ノード のそれぞれ左の子右の子 ノード ノード が右の子 を持ちかつ である場合ノード は であると定義します左の子がない場合は とします ポテンシャル関数 ヒープ に含まれるノードの総数 操作の償却解析 の主な操作である について考えます簡単のため の根のキーが の根のキー以下であると仮定しますそうでない場合は と を交換します の根を とします 操作は から始まる右パス に沿って再帰的に処理を行います各ノード において以下の処理が行われます の元の右の子 または の一部 と の残りまたは が そのものの場合もあるを再帰的にしその結果を の新しい右の子 とします の元の左の子 と新しい右の子 をスワップしますつまり後の の左の子は 右の子は となります このパスの長さスワップが行われる回数を とすると操作の実際のコスト は です

---

上下前次1-新書関写板覧索設栞歴

---

あと 743 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.041s