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

競技プログラミングにハマるプログラマのスレ 227 http://medaka.5ch.net/test/read.cgi/prog/1747628087/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞

---

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

---

260: 仕様書無しさん [sage] 2025/05/22(木) 02:21:42.56 次に、ポテンシャルの変化 ΔΦ を評価します。パス上の各ノード x_i に注目します。 - ケース1: x_i が元々RightHeavyだった場合 size(R_i) > size(L_i) であったため、Φ に +1 貢献していました。 スワップ後、x_i の新しい右の子は L_i、新しい左の子は R'_i となります。 size(L_i) < size(R_i) であり、size(R'_i) は size(R_i) と同程度かそれ以上になる傾向があるため、size(L_i) <= size(R'_i) となる可能性が高いです。この場合、x_i はRightHeavyではなくなります。 し

たがって、x_i によるポテンシャルの変化は -1 となります。 - ケース2: x_i が元々RightHeavyではなかった場合 size(R_i) <= size(L_i) であったため、Φ に 0 貢献していました。 スワップ後、x_i の新しい右の子は L_i、新しい左の子は R'_i となります。 - もし size(L_i) > size(R'_i) となった場合（つまり、元々の左の子 L_i が、元々の右の子 R_i と他ヒープのマージ結果 R'_i よりも大きかった場合）、x_i はRightHeavyになります。このとき、x_i によるポテンシャルの変化は +1 となります。 - もし size(L_i) <= size(R'_i) の場

合、x_i はRightHeavyのままか、RightHeavyではなくなりますが、元々0だったので変化は 0 です。 Meldパス上のノード数を m とします。 - m_RH: 元々RightHeavyだったノードの数。これらは ΔΦ に -m_RH 貢献します。 - m_LH: 元々 size(L_i) > size(R_i) であり、かつスワップ後にRightHeavyになったノードの数（つまり size(L_i) > size(R'_i) も満たす）。これらは ΔΦ に +m_LH 貢献します。 - m_EQ: 元々 size(L_i) = size(R_i) であり、スワップ後もRightHeavyにならなかったノードの数。これらは ΔΦ に 0 貢献します。 (簡単のため

、m_EQ のうちRightHeavyになるケースは m_LH に含めて考えます) したがって、ΔΦ ≈ m_LH - m_RH となります。 http://medaka.5ch.net/test/read.cgi/prog/1747628087/260

---

ﾒﾓ帳

(0/65535文字)

---

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

---

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

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.010s