[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
182: 05/21(水)14:07 AAS
LLMだけでなく画像動画生成など全ての分野を総取りしようとしててすごい
183: 05/21(水)14:10 AAS
外部ﾘﾝｸ:www.profuture.co.jp
勝者がすべてを獲得する
ウィナー・テイクス・オール（Winner takes all）とは「一人勝ち」「勝者総取り」という意味です。戦いに勝ったものがすべてを獲得し、負けた者は何も得ることはない。そのような状況を指します。
184: 05/21(水)14:18 AAS
よくわからんけどGeminiの方が競プロも強くなるのか？
185(1): 05/21(水)14:25 AAS
まあGoogleは昔から競プロのAIにかなり取り組んでるし
いまOpenAIに負けてるのはそのへんの数学分野だけだからな、時間の問題だよ
今回の発表でOpenAI超えたといっているのもそりゃそうだよね、って感じ
そんぐらい基本的な実力としては ChatGPT と Gemini はかけ離れてる
Gemini は普通に一番かしこいし、コスパで見たらダントツ
186: 05/21(水)14:26 AAS
>>185
結局今日の発表で競プロ能力でも超えたのか？それだけが大事な情報
187: 05/21(水)14:29 AAS
超えたいうてるやん
188: 05/21(水)14:30 AAS
じゃあ乗り換えるか
189: 05/21(水)14:32 AAS
まだ使えないぞ早とちりすんな
190: 05/21(水)14:33 AAS
「Gemini 2.5 Pro」のさらに高度な思考モード「Deep Think」 性能は「o3」「o4-mini」超え
外部ﾘﾝｸ:news.yahoo.co.jp
191: 05/21(水)14:36 AAS
やっぱりG目指すのが最適解ということ
レールに乗りなさい
192: 05/21(水)14:38 AAS
おぺないとかいう謎の会社がGoogle様に敵うわけないだろ
193: 05/21(水)14:40 AAS
毎回スレの予言が当たってるな
マジでこの世の真理ばかり記述されてるアカシックレコードと言っても過言ではない
194: 05/21(水)14:43 AAS
Gが月額$249.99のAIサブスク「Google AI Ultra」を始めたぞ
もうGのAIプラットフォームによる搾取は始まっている
これ利用するかしないかで問題解決力が桁違いだし、貧民以外はみんな課金するだろうな
外部ﾘﾝｸ:blog.google
195: 05/21(水)14:45 AAS
貧困のインコの部分
196: 05/21(水)14:52 AAS
競プロerに多そうなタイプ
画像ﾘﾝｸ[jpeg]:i.imgur.com
197: 05/21(水)14:55 AAS
年間43万はさすがに高すぎ
ジャップモンキーには利用できない
そんなに払うくらいならアメックスセンチュリオンやJCBのブラックカードとか取得したほうがモテるだろ
198(1): 05/21(水)16:38 AAS
でもこういうの一つは契約してないと人間であったとしても余裕でGPTインコに負けうるんだよな
反AIなんかやってたら一瞬で取り残されるし、適応するしかないから、本当しょうもない時代になったよ
199: 05/21(水)16:39 AAS
>>198
これ競プロというよりは一般的な業務とかでの話ね
200(1): 05/21(水)16:48 AAS
エンジニアとかいう職業LLMの登場で更にITドカタになった感あるよな
マジで耐久性を試されてる
201: 05/21(水)17:24 AAS
外部ﾘﾝｸ:x.com
ジャップランドでもこれやらないと次世代でも負けます
202(1): 05/21(水)17:42 AAS
>>200
アルゴコーディングが死んで環境構築等の技術の導入が得意なやつが覇権を握る時代になったというわけ
理学部の純粋培養競erが完全に死んだ
203: 05/21(水)17:45 AAS
なにいってんのおまえ
中卒AI職人でいいよね
204: 05/21(水)17:47 AAS
AIは競プロでも暖色レベルだからな
205: 05/21(水)17:48 AAS
>>202
お前前もここに書き込んで恥晒してたけどエアプ書き込みやめろ
環境構築なんて質問しまくれば余裕でできるから
206: 05/21(水)17:49 AAS
環境構築で食っていけると思ってるバカはインコパークでも構築してろよ
207: 05/21(水)17:49 AAS
構築したインコパークをキッズに乗っ取られて鬱病の皆様
208: 05/21(水)17:50 AAS
結局LLMを活かすのも高知能の方が得意だし、キャパも大きいので、TKNDKSUT暖色が勝者総取りする現実は簡単には変わりません
インコは一生インコサイドです
209: 05/21(水)17:51 AAS
それはそうだがUT卒までやるのメモリの無駄遣い
210: 05/21(水)17:56 AAS
受験を競技だと勘違いして受験過学習やってるやつは全員無能
合格できればなんでもいいから努力リソースの無駄遣い
211: 05/21(水)18:11 AAS
ペパテしか特技がないやつはそうなる
212: 05/21(水)18:15 AAS
TKに多いタイプ
213: 05/21(水)18:15 AAS
UTはコスパが悪い
マーチに受かれば十分
214: 05/21(水)18:38 AAS
筑波ってどうなん
215: 05/21(水)18:43 AAS
筑波はマーチレベルだからコスパいいぞ
216: 05/21(水)19:32 AAS
マーチからではGに入れませんよ
217: 05/21(水)19:38 AAS
まーちんこ
218: 05/21(水)19:49 AAS
UTでも難しいからね、UTISには入っておきましょう
219(1): 05/21(水)20:30 AAS
お前は頭悪いから緑になれるなんてすごいっていうのかなり醜悪に感じてしまう
220: 05/21(水)20:36 AAS
真に残酷で醜悪なのはインコとの知能差だぞ
221: 05/21(水)20:43 AAS
GAFAなら新卒年収で2000万円が当たり前
外部ﾘﾝｸ:honkiku.com
222: 05/21(水)20:48 AAS
迫真OMC部競技プログラミングの裏技
223: 05/21(水)21:36 AAS
>>219
そんなこと言ってるやついる？
224: 05/21(水)21:40 AAS
緑はセンター300点レベル
緑はTOEIC230
緑は境界知能レベル
緑は社会不適合者
225: 05/21(水)21:53 AAS
実際凄いと思うけどな
センター300点TOEIC230点って受験者の下位5%に入るくらいの知能レベルだろ
それこそ、日本語の文書をかけますか四則演算できますかとかそういうレベル
そんな人間が競プロにハマって緑まで到達したのは凄いとしか言いようがない
226: 05/21(水)22:03 AAS
マスくん凄すぎる
真の努力家というわけだな
227: 05/21(水)22:19 AAS
緑が歴史的大偉業はさすがに失礼だと思う
228: 05/21(水)22:30 AAS
緑にとっては
229: 05/21(水)22:43 AAS
システム作れないバカなコンサルやPMOより
SEやPGが単価が低いって大問題じゃね？
230: 05/21(水)22:45 AAS
マスくんは才能にも環境にも恵まれなかったけれど、努力だけで成り上がった努力の天才
231: 05/21(水)22:50 AAS
SEやPGが低給与で満足してるから、ジャップランドにはそういう職種で働いてるモンキーが大勢おるんやで
232: 05/21(水)22:50 AAS
GAFAなら新卒年収で2000万円が当たり前
外部ﾘﾝｸ:honkiku.com
233: 05/21(水)22:58 AAS
AtCもこんぐらいの対応しなきゃ見限られてもう終わりだよ
メルカリ、トラブルの損害は“全額補償”へ 不正利用者の徹底排除も宣言
外部ﾘﾝｸ[html]:www.itmedia.co.jp
234: 05/21(水)23:00 AAS
AtCに不正対応を期待してるスレ民なんてまだおったんか
お前2ヶ月寝てたんか？
235: 05/21(水)23:11 AAS
でもAtCは有名度は相当高いのにエンジニア数人で回してるしgptに質問入力中に問題解決もするしchokudaiベンチマークは0%だから
236: 05/21(水)23:16 AAS
OMCの順位表も無事死亡してて草
237: 05/21(水)23:26 AAS
お陰様で社長は億万長者で嫁も可愛くて毎日セックスです
238: 05/21(水)23:39 AAS
大卒が無価値化するな
239: 05/21(水)23:41 AAS
なくていいよあんな就職予備校
240(2): 05/22(木)00:02 AAS
お湯さん、OMCもやってたんだね
yuyu様も相変わらず安定して強いね
今後も2人は要注目だ
外部ﾘﾝｸ:onlinemathcontest.com
241: 05/22(木)00:08 AAS
yuyuのX見に行ったら、自力で解いてないせいかまともな感想言えれてなくて草
242: 05/22(木)00:17 AAS
IMO金メダリストが野生の天才にフルボッコにされてて草
こういうの見るの気持ちよすぎる
243(1): 05/22(木)00:23 AAS
地頭コンプ勢だから生成AI不正集団を全力で応援したい
赤コーダーやIMO金メダリストのような地頭お化けを過去の遺物にしてくれー
244: 05/22(木)00:27 AAS
功を焦って証拠無しで詰めて逃がしたあほあほ冠さんの失態が光る
245: 05/22(木)00:29 AAS
証拠持ってから詰めりゃ未来のライバルを完全に再起不能に追い込めたのに悔しいのう悔しいのうw
246(1): 05/22(木)00:30 AAS
黒船が来航し結果的に武士や剣術が終わったように、生成AIが台当して高知能や競が終わるわけだね
今の競erは明治時代への転換期に剣術の腕を磨いていた武士と被るところがあるな
247: 05/22(木)00:35 AAS
江戸末期の殺人術tier1はピストルぶっぱじゃねーの
剣術とか黒船以前から半分おままごとだろ
248: 05/22(木)00:41 AAS
江戸時代は平和だったからな
249: 05/22(木)00:41 AAS
いうて武士は西南戦争で爆死しとるし競erも10年したら反乱失敗で爆死するでしょ
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
上下前次1-新書関写板覧索設栞歴
あと 740 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.016s