[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
競技プログラミングにハマるプログラマのスレ 227 http://medaka.5ch.net/test/read.cgi/prog/1747628087/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
11: 仕様書無しさん [sage] 2025/05/19(月) 17:16:03.40 >>4 blackyuki http://medaka.5ch.net/test/read.cgi/prog/1747628087/11
146: 仕様書無しさん [sage] 2025/05/20(火) 20:22:00.40 mayobun http://medaka.5ch.net/test/read.cgi/prog/1747628087/146
256: 仕様書無しさん [sage] 2025/05/22(木) 02:07:22.40 4. ポテンシャル解析の考え方 ・ヒープの「アンバランスさ」や「右への偏り具合」を数値化したものを「ポテンシャル」と考える。 ・実際のコストが高い操作（長い右パスをたどる）では、多くのスワップにより 「アンバランスさ」が大きく解消され、ポテンシャルが大幅に減少する。 ・償却コスト = 実際のコスト + ポテンシャルの変化量 ・実際のコストが高くても、ポテンシャルの減少が大きければ、償却コストは小さく抑えられる。 ・逆に、実際のコストが低い操作ではポテンシャルが少し増えることもあるが、 それは将来のコストが高い操作のための「貯金」のようなもの。 ・ポテンシャル関数をうまく定義し数学的に解析すると、どの操作も平均して O(log n) の償却コストになることが示せる。 （例: 「右の子が左の子よりサイズが大きいノードの数」や「各ノードのランクの合計」などを ポテンシャルとして使う証明方法があるが、その計算は複雑） 5. 結論 meld / insert / delete-min いずれも、単発の最悪計算時間は O(n) だが、 一連の操作を通してみると、償却計算時間は O(log n) になる。 http://medaka.5ch.net/test/read.cgi/prog/1747628087/256
547: 仕様書無しさん [sage] 2025/05/23(金) 17:47:56.40 鹿児島って住みづらそうだな http://medaka.5ch.net/test/read.cgi/prog/1747628087/547
825: 仕様書無しさん [sage] 2025/05/25(日) 12:42:11.40 りにりすさんは多言語を扱うわかりやすい天才だから疑義はないですね http://medaka.5ch.net/test/read.cgi/prog/1747628087/825
877: 仕様書無しさん [sage] 2025/05/25(日) 19:26:10.40 利用規約なんて読んで理解したとしても無視するに決まってんだろ なぜなら私達は競プロerだからです http://medaka.5ch.net/test/read.cgi/prog/1747628087/877
954: 仕様書無しさん [sage] 2025/05/25(日) 20:24:41.40 バカ参り定期 http://medaka.5ch.net/test/read.cgi/prog/1747628087/954
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.043s