競技プログラミングにハマるプログラマのスレ 227

[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次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

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

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ AAｻﾑﾈｲﾙ

ぬこの手ぬこTOP 0.206s*