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

[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次 1-新

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

250: 05/22(木)00:45 AAS
はやく競プロ終了してくんねーかな、　ってGoogle様も思ってます

251: 05/22(木)01:32 AAS
>>240
ykymstさんは最近すごいね

252: 05/22(木)01:39 AAS
このスレ内の250レス読んだけど競プロの具体的な話一切なし

253: 05/22(木)01:49 AAS
そんなに競の話がしたいならお前話題振れよ
skewheapが償却lognなの意味分からんからこの話でもするか

254: 05/22(木)01:53 AAS
ちなこれ
実装はインコでもできるから窃盗するならしてどうぞ
外部ﾘﾝｸ:hos.ac

255: 05/22(木)02:07 AAS
Skew Heap の償却 O(log n) が成り立つ理由

1. すべての操作は meld（ヒープの結合）に帰着する
・insert : 1 要素ヒープと既存ヒープを meld
・delete-min : 根を削除 → 残った左右の子のヒープを meld
meld の手順
(a) 2つのヒープの根を比較し、キーが小さい方の根を新しいヒープの根とする。
(b) (a)で選ばれた根の元の右の子と、もう一方のヒープ全体を再帰的に meld する。
省11

256: 05/22(木)02:07 AAS
4. ポテンシャル解析の考え方
・ヒープの「アンバランスさ」や「右への偏り具合」を数値化したものを「ポテンシャル」と考える。
・実際のコストが高い操作（長い右パスをたどる）では、多くのスワップにより
「アンバランスさ」が大きく解消され、ポテンシャルが大幅に減少する。
・償却コスト = 実際のコスト + ポテンシャルの変化量
・実際のコストが高くても、ポテンシャルの減少が大きければ、償却コストは小さく抑えられる。
・逆に、実際のコストが低い操作ではポテンシャルが少し増えることもあるが、
省8

257: 05/22(木)02:09 AAS
“swap して左に押しやる” という小技のおかげで，
「毎回の操作は派手に道を掘り返してるように見えて，実は一人ひとりはあまり働かされていない」
──これが skew heap が償却 O(log n) で済むカラクリです ✨

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
情弱ビジネスは社会貢献