[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
競技プログラミングにハマるプログラマのスレ 227 http://medaka.5ch.net/test/read.cgi/prog/1747628087/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制
です｡10分ほどで解除するので､
他のﾌﾞﾗｳｻﾞ
へ避難してください｡
118: 仕様書無しさん [sage] 2025/05/20(火) 12:20:23.19 まだ言ってない http://medaka.5ch.net/test/read.cgi/prog/1747628087/118
124: 仕様書無しさん [sage] 2025/05/20(火) 12:37:17.19 ぶっ壊れ最強チートキャラだからな http://medaka.5ch.net/test/read.cgi/prog/1747628087/124
134: 仕様書無しさん [sage] 2025/05/20(火) 16:33:54.19 じぇねるしでも きのあうともだち みつかるひが くるのかな いばしょ🧸 http://medaka.5ch.net/test/read.cgi/prog/1747628087/134
227: 仕様書無しさん [sage] 2025/05/21(水) 22:19:30.19 緑が歴史的大偉業はさすがに失礼だと思う http://medaka.5ch.net/test/read.cgi/prog/1747628087/227
261: 仕様書無しさん [sage] 2025/05/22(木) 02:22:11.19 償却コスト 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) となります。 したがって、償却コスト A = O(m_LH + m_EQ) = O(log n) と結論付けられます。 http://medaka.5ch.net/test/read.cgi/prog/1747628087/261
274: 仕様書無しさん [sage] 2025/05/22(木) 06:34:39.19 なろうアニメにハマるインコの心理だよ http://medaka.5ch.net/test/read.cgi/prog/1747628087/274
520: 仕様書無しさん [sage] 2025/05/23(金) 16:50:18.19 アンフェアだろ それならAI拓也と比べろよ http://medaka.5ch.net/test/read.cgi/prog/1747628087/520
636: 仕様書無しさん [sage] 2025/05/24(土) 10:47:32.19 鳩山家の優秀な遺伝子を恵んでもらえ http://medaka.5ch.net/test/read.cgi/prog/1747628087/636
821: 仕様書無しさん [sage] 2025/05/25(日) 12:01:29.19 ただの前処理部分なのでそこ言及するの非本質なのわかるな GPTの言ったことおうむ返ししてる可能性上がる http://medaka.5ch.net/test/read.cgi/prog/1747628087/821
832: 仕様書無しさん [sage] 2025/05/25(日) 12:48:23.19 BANされずに続けてくれた方がここで話題に出来るからありがたいまである http://medaka.5ch.net/test/read.cgi/prog/1747628087/832
850: 仕様書無しさん [] 2025/05/25(日) 15:50:36.19 学歴＝知能だと思っている人も多いし、Xの学歴界隈だと知能差別がメインコンテンツと化しているよな http://medaka.5ch.net/test/read.cgi/prog/1747628087/850
872: 仕様書無しさん [sage] 2025/05/25(日) 19:22:33.19 は〜〜心が痛むわ〜〜 心が痛すぎるわ〜〜😣😣 http://medaka.5ch.net/test/read.cgi/prog/1747628087/872
899: 仕様書無しさん [sage] 2025/05/25(日) 19:41:40.19 Nachia大学さん不幸にも間引きされてしまう http://medaka.5ch.net/test/read.cgi/prog/1747628087/899
931: 仕様書無しさん [sage] 2025/05/25(日) 20:03:09.19 >>879 不正erパワーすげぇ http://medaka.5ch.net/test/read.cgi/prog/1747628087/931
972: 仕様書無しさん [sage] 2025/05/25(日) 20:41:14.19 >>965 責任感じてるな http://medaka.5ch.net/test/read.cgi/prog/1747628087/972
997: 仕様書無しさん [sage] 2025/05/25(日) 23:42:58.19 40人くらい消えてる気がする http://medaka.5ch.net/test/read.cgi/prog/1747628087/997
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.033s