[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
118: 05/20(火)12:20:23.19 AAS
まだ言ってない
124: 05/20(火)12:37:17.19 AAS
ぶっ壊れ最強チートキャラだからな
134: 05/20(火)16:33:54.19 AAS
じぇねるしでも きのあうともだち みつかるひが くるのかな
いばしょ🧸
227: 05/21(水)22:19:30.19 AAS
緑が歴史的大偉業はさすがに失礼だと思う
261: 05/22(木)02:22:11.19 AAS
償却コスト A は、 A = C + ΔΦ = O(m) + m_LH - m_RH です。
m = m_RH + m_LH + m_EQ （ここで m_EQ は size(L_i) <= size(R_i) であり、スワップ後もRightHeavyにならないノード）とすると、
A = O(m_RH + m_LH + m_EQ) + m_LH - m_RH
A ≈ O(1) * (m_RH + m_LH + m_EQ) + m_LH - m_RH = O(m_LH + m_EQ) + (const-1)m_RH
もし実際のコストの係数が1に近いと仮定できれば、A ≈ 2m_LH + m_EQ となります。
ここで重要なのは、m_LH + m_EQ の部分、つまりmeldパス上で元々 size(R_i) <= size(L_i) であったノードの数です。
あるノード x で size(rc(x)) <= size(lc(x)) が成り立つ場合、size(rc(x)) <= (size(x) - 1) / 2 となります。これは、右の子の部分木のサイズが、その親を根とする部分木全体のサイズの半分以下であることを意味します（左の子が存在する場合）。
このような性質を持つノードが右パスに連続して多数現れると、部分木のサイズは急速に減少します。したがって、任意の右パスにおいて、size(rc(x)) <= size(lc(x)) を満たすノードの数は高々 O(log n) 個しか存在できません。
Meld操作がたどる右パス上のノードのうち、m_LH と m_EQ に分類されるノードは、まさにこの条件 size(R_i) <= size(L_i) を（スワップ前に）満たしています。
よって、m_LH + m_EQ = O(log n) となります。
省1
274: 05/22(木)06:34:39.19 AAS
なろうアニメにハマるインコの心理だよ
520: 05/23(金)16:50:18.19 AAS
アンフェアだろ
それならAI拓也と比べろよ
636: 05/24(土)10:47:32.19 AAS
鳩山家の優秀な遺伝子を恵んでもらえ
821: 05/25(日)12:01:29.19 AAS
ただの前処理部分なのでそこ言及するの非本質なのわかるな
GPTの言ったことおうむ返ししてる可能性上がる
832: 05/25(日)12:48:23.19 AAS
BANされずに続けてくれた方がここで話題に出来るからありがたいまである
850: 05/25(日)15:50:36.19 AAS
学歴＝知能だと思っている人も多いし、Xの学歴界隈だと知能差別がメインコンテンツと化しているよな
872: 05/25(日)19:22:33.19 AAS
は〜〜心が痛むわ〜〜
心が痛すぎるわ〜〜😣😣
899: 05/25(日)19:41:40.19 AAS
Nachia大学さん不幸にも間引きされてしまう
931: 05/25(日)20:03:09.19 AAS
>>879
不正erパワーすげぇ
972: 05/25(日)20:41:14.19 AAS
>>965
責任感じてるな
997: 05/25(日)23:42:58.19 AAS
40人くらい消えてる気がする
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.073s