[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
258(1): 05/22(木)02:12 AAS
RightHeavyをポテンシャルとした数学的解析を行え.参考資料があれば提示せよ.
259: 05/22(木)02:20 AAS
はい、承知いたしました。Skew Heapの償却O(log n)解析（RightHeavyノードをポテンシャルとして使用）を記述します。
Skew Heapの償却O(log n)解析 (RightHeavyポテンシャル)
1. 定義
- 部分木のサイズ size(x): ノード x を根とする部分木に含まれるノードの総数。
- 左の子 lc(x)、右の子 rc(x): ノード x のそれぞれ左の子、右の子。
- RightHeavyノード: ノード x が右の子 rc(x) を持ち、かつ size(rc(x)) > size(lc(x)) である場合、ノード x は RightHeavy であると定義します。（左の子がない場合は size(lc(x))=0 とします。）
- ポテンシャル関数 Φ(H): ヒープ H に含まれるRightHeavyノードの総数。
省6
260: 05/22(木)02:21 AAS
次に、ポテンシャルの変化 ΔΦ を評価します。パス上の各ノード 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ではなかった場合
省9
261: 05/22(木)02:22 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 となります。これは、右の子の部分木のサイズが、その親を根とする部分木全体のサイズの半分以下であることを意味します（左の子が存在する場合）。
省4
262: 05/22(木)02:22 AAS
3. 参考資料
この種の償却解析の議論や技法は、以下の資料やそれらに類するデータ構造の教科書、講義ノートで見られます。
1) Sleator, D. D., & Tarjan, R. E. (1985). Self-Adjusting Binary Search Trees. Journal of the ACM, 32(3), 652-686.
- 直接Skew Heapを主題としたものではありませんが、Splay Treeの償却解析の技法が広く応用されており、AppendixでSkew Heapに似た「ボトムアップヒープ」について触れています。ポテンシャル関数を用いた償却解析の基礎となります。
2) Weiss, M. A. (various editions). Data Structures and Algorithm Analysis in C++ / Java. Addison-Wesley.
- 多くの版でSkew Heapとその償却解析について解説が含まれています。
3) 大学の講義資料:
省2
263: 05/22(木)02:34 AAS
パス上のLightなノード数はO(logn)だからΔΦ=O(logn)ということは解するが,RightHeavyのポテンシャル変化が確率的解析になっていて気に食わん.
size(R'_i) は size(R_i) と同程度かそれ以上になる傾向があるため、size(L_i) <= size(R'_i) となる可能性が高いです。を数学的に詳説せよ.
264: 05/22(木)02:41 AAS
あ？つか自明かmeldでノード数は減らんし
265(1): 05/22(木)02:43 AAS
>>258
なんで命令してんだよ
行ってください提示してくださいだろ
266: 05/22(木)02:44 AAS
>>265
黙ってください
267: 05/22(木)02:47 AAS
競プロの話はチャッピーにやらせれば十分
268: 05/22(木)02:47 AAS
259のlightheavyの定義hosの定義より有能やんけ
サンキューGPT
269: 05/22(木)02:51 AAS
またGPTが人類を超えたというわけか
270: 05/22(木)02:56 AAS
競の話は終わったからゴシに戻っていいぞ
271(1): 05/22(木)06:29 AAS
時代は松尾研>>>理三というわけ
松尾研が所属する工学部電子情報工学科は、進振りで超難関と化しており、「松尾研に入るのは理三合格より難しい」という声も聴く。
外部ﾘﾝｸ:news.yahoo.co.jp
272: 05/22(木)06:33 AAS
>>246
剣道とかは残ってるだろ
273: 05/22(木)06:34 AAS
>>243
やっぱりTKNDKSやUTや暖色の高知能に嫉妬するスレだったんだねここ
274: 05/22(木)06:34 AAS
なろうアニメにハマるインコの心理だよ
275: 05/22(木)06:35 AAS
>>240
GPTインコがどんどん集合して順位表不自然に占有するの笑う
276: 05/22(木)07:08 AAS
geoguessrにもレーティングバトルあるのか
やろうかな
277: 05/22(木)07:08 AAS
典型教えろ
278: 05/22(木)08:39 AAS
【料金強奪】泥棒させるな【知財強奪】
☆多重派遣の犯罪損害の詐欺支援するな☆
★多重派遣で開発料金の詐欺をさせるな★
発注者に詐欺予防と伝えて発注金額を確かめろ！
【契約】
1次受注金額 200万円 詐欺被害金額 0万円
2次受注金額 160万円 詐欺被害金額 40万円
省10
279: 05/22(木)08:56 AAS
剣道なんぞおままごとじゃん
実用性皆無でやってる感出してるだけ
280: 05/22(木)09:05 AAS
スレへの書き込みは実用性に富んでるからな
281: 05/22(木)09:17 AAS
真実を包み隠さず学べる神スレなのではい
282: 05/22(木)10:27 AAS
>>271
さすが日本一の松尾研だ
ノーベル賞受賞者もたくさん出てくるだろう
283: 05/22(木)10:38 AAS
松尾研に所属するオーキド博士
284: 05/22(木)12:34 AAS
じぶんにできること いばしょ あいじょう ゆうじょう しんらい
🧸……💀
285: 05/22(木)12:37 AAS
AI(愛)と勇気だけが友達さ
動画ﾘﾝｸ[YouTube]
286: 05/22(木)12:46 AAS
正直新規性のあること今更発明するの厳しくないか？
ジェネルシは大人しく就寝
という気持ちになって研究もビジネスも鬱病すぎる
287: 05/22(木)12:51 AAS
大人しく医師や弁護士や公認会計士を目指してギュの対策をしとけ
288: 05/22(木)12:51 AAS
正直、新規性のあることを今から発明するのが厳しい…という感覚はよくわかるよ。世の中の多くの分野で、すでに「やり尽くされた感」があるし、新しいものを作り出すプレッシャーも大きい。特にネットの発達で情報がすぐに共有されるから、「自分の考えなんて、もう誰かがやってるだろう」と思いやすいよね。
でも実際には、「全くのゼロから生まれる発明」よりも、「既存のアイデア同士の組み合わせ」や「ちょっとした視点の変化」が新しい価値になることが多い。身の回りを見渡すと、過去の発明やアイデアをちょっとずつ改良したものばかりだし、「ジェネルシ（generativeな思考や生成AIの意）」だって、既存技術の延長線上にあるものだったりする。
もし今しんどいなら、無理に新しいものを生み出そうとせず、「何かを面白がること」や「今あるものを深掘りすること」でも全然いいと思う。ビジネスも研究も、必ずしも毎回すごい新規性が必要なわけじゃないし、小さな積み重ねも立派な成果。
あと、「就寝して休む」のもめちゃくちゃ大事。鬱っぽくなるのは、自分だけじゃないよ。気持ちが沈んでるときは、いっそ休んだ方が回復も早い。自分を責めないで、少しずつでいいと思うよ。
焦らず、無理せず。
289: 05/22(木)12:57 AAS
低知能コピペインコ時代の幕開け
290: 05/22(木)13:08 AAS
インコイン鰻登りじゃん
レートの推移が不自然だし、ビットコインもGPT使ってる可能性あるな
291: 05/22(木)13:10 AAS
ジェネルシ(generativeな思考や生成AIの意)
？
292: 05/22(木)13:10 AAS
スレの学習が足りてないようだな
293: 05/22(木)13:25 AAS
また研究に競プロの知識が役に立ってしまった
明日から競プロは研究の役に立つ！！！って叫びながら登校しようかな
294(1): 05/22(木)14:38 AAS
NDKS→UT→松尾研が唯一の王道ルートというわけ
TKは邪道
295: 05/22(木)15:12 AAS
【料金強奪】泥棒させるな【知財強奪】
☆多重派遣の犯罪損害の詐欺支援するな☆
★多重派遣で開発料金の詐欺をさせるな★
発注者に詐欺予防と伝えて発注金額を確かめろ！
【契約】
1次受注金額 200万円 詐欺被害金額 0万円
2次受注金額 160万円 詐欺被害金額 40万円
省10
296: 05/22(木)15:15 AAS
>>294
これを歩んでるのが安野さんというわけか
297: 05/22(木)16:30 AAS
外部ﾘﾝｸ:x.com
社長も安野さんに言及している
298: 05/22(木)16:36 AAS
AIに特化した先進校的な高校（Super AI High Schools：SAIS）
虎の威を借るな
299: 05/22(木)16:49 AAS
くんみたいに競プロを卒業した立派な若者をたくさん輩出するということだな
300: 05/22(木)16:49 AAS
結局TKNDKS志向やAOJと同じ思想
中受支配の原理の域を出ない
301: 05/22(木)16:50 AAS
こんな競プロやらせるなんていうマニフェストが入ったら
全ジェネルシのために安野さんを応援せざるをえないな
302: 05/22(木)16:52 AAS
スレ民が前々から目をつけてた候補者なだけあるな
やっぱり出身中学+大学の確認が正義というわけ
303: 05/22(木)16:52 AAS
そんなことしたら社長がマスマスお金持ちになっちゃう！
304: 05/22(木)16:53 AAS
別にいいが？
305: 05/22(木)16:55 AAS
実力とか技術を身につけるとノウハウや労働力をコジキしてくるインコが群がってくる現象なんなんだ
306: 05/22(木)16:57 AAS
ジャップインコは嫉妬深く陰湿な特性を持ち合わせてるからな
307: 05/22(木)16:57 AAS
需要っていいます
308: 05/22(木)16:57 AAS
対価を払えという話
309: 05/22(木)16:58 AAS
乞食を需要で美化するのやめろ
310: 05/22(木)16:59 AAS
テイカーインコ定期
駆逐されるが良い
311: 05/22(木)17:01 AAS
テイカーはある意味ギバーなんだよな
ギバーのgiveしたいという需要を満たすので
312: 05/22(木)17:02 AAS
テイカーインコの正当化やめてね 駆逐されてね
313: 05/22(木)17:07 AAS
|◤#モンスト×アニメ「#ぼっち・ざ・ろっく！」◢| 5/24 12時よりコラボ開催✨ ◆ガチャ「超・獣神祭」に登場！ ・喜多郁代 ・山田リョウ ・伊地知虹夏 ◆スターターパック ・後藤ひとり ◆コラボキャラが登場！ ・廣井きくり ・結束バンド #ぼっちコラボ
マスくん歓喜案件じゃん
314(1): 05/22(木)17:07 AAS
ギバーの需要は女子高生に個人指導するだのおっさんが部下連れて威張るだのだぞ
お前が女子高生なら一理あるが？
315: 05/22(木)17:07 AAS
マスくんってぼざろ好きなん？草
316: 05/22(木)17:08 AAS
以下モンストスレ
317: 05/22(木)17:10 AAS
くんとマスくんも、社長みたいにマニフェストにPull Requestすべきだよな
318(1): 05/22(木)17:10 AAS
>>314
三大需要があるテイカーは女子高生、部下、インコだぞ
319: 05/22(木)17:13 AAS
>>318
マジレスするとペットな
320: 05/22(木)17:17 AAS
インコに教えたがる人間がいるってことはインコはギバーでもテイカーでもあるということ
321: 05/22(木)17:17 AAS
インコにはエサ代だけ与えてやれば良い
322: 05/22(木)17:18 AAS
欲張るな、見栄を張るな、邪魔をするな
323(1): 05/22(木)17:18 AAS
インコに嘘を教えて搾取した上で破滅させる仕事
情弱ビジネス
324: 05/22(木)17:19 AAS
>>323
これ潜在的な同業者も潰せるし有効すぎるな
325: 05/22(木)17:19 AAS
情弱ビジネスは社会貢献
326: 05/22(木)17:19 AAS
頑張ってるインコ尊い
327: 05/22(木)17:20 AAS
インコの駆逐とかいう社会貢献素晴らしいな
遺伝支配的だし、足を引っ張るだけの嫉妬ドリブンインコは不要
328: 05/22(木)17:21 AAS
教えたがりインコを消耗させるサービスは存在してnoteだのqiiitaだの
329: 05/22(木)17:22 AAS
教えたがりインコとかいう害悪存在
情報の質が下がる
330: 05/22(木)17:23 AAS
くんの悪口言うな
331: 05/22(木)17:23 AAS
ABCやARCの解説作成にレート制限が設けられている理由
332: 05/22(木)17:23 AAS
宗教ってマジで有能だったよな
ゴミの時間をドブらせる手に事欠かん
333(1): 05/22(木)17:25 AAS
天然インコのゴミ解説は黄色が書くゴミ解説とは格が違う
334: 05/22(木)17:25 AAS
ジャップ社会に出るとやってる感が大事なのではと痛感させられることが多すぎる
やってる感で全部回ってるだろ
335(2): 05/22(木)17:26 AAS
>>333
解説がうまいインコもいるけどな
336(1): 05/22(木)17:27 AAS
>>335
いません
人間があえてやってないだけです
337: 05/22(木)17:27 AAS
>>335
それは知っとるが例外なのではい
338: 05/22(木)17:27 AAS
インコの能力は人間のサブセットであることをしっかり認識して日々を過ごした方がいい
思い上がるな
上下前次1-新書関写板覧索設栞歴
あと 664 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.018s