[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 176 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
412(1): 2024/05/13(月)22:08 AAS
昨日のCが知識問題とか言ってるのインコすぎる
相変わらず書き込みからレートと学歴が透けることよ
413: 2024/05/13(月)22:10 AAS
そんな低レベルなことにまでマウント取るな
414: 2024/05/13(月)22:10 AAS
>>412
知識問題じゃなきゃなんなんだ？
415: 2024/05/13(月)22:12 AAS
緑上位だった頃はお前らのこと尊敬してた(ミラーラビンやロリハの衝突について教えてくれたり、知らないアルゴリズムについて話ていたため)けどいざ黄色間近になると普通に俺より弱くてがっかりだよ
いや、単純に俺がB1だった頃にアドバイスくれたB3-M2たちが2年ちょい経って皆スレから卒業しただけか？
416(1): 2024/05/13(月)22:13 AAS
>>410
は？マジで俺は全部解いてるし暖色だぞ
お前が要求してきたからわざわざ探してやってるのにお前みたいな低レートと一緒にすんなよ
直近10回くらいでも
括弧列の必要条件を要求する典型知識問題
arc175_b
ABC-Eレベルの確率DP
省4
417: 2024/05/13(月)22:13 AAS
考察問題でしょ
お互いに影響しないことだけ考察できれば後は最短経路
418: 2024/05/13(月)22:14 AAS
今度はお前が教える番になったんだよ
419: 2024/05/13(月)22:14 AAS
誕生日憎い
420: 2024/05/13(月)22:14 AAS
マジで明らかに俺よりも問題解いてない＆レート低いインコが喧嘩売ってくるの不快すぎる 身の程をしれ
421: 2024/05/13(月)22:15 AAS
arc173aも桁dporN進法だから知識寄りだし
422(1): 2024/05/13(月)22:17 AAS
>>416
あったわすまんな
そのへんARCで出たのが不愉快過ぎて記憶から消してた
あと173ABも混ぜていいぞ
423: 2024/05/13(月)22:17 AAS
てかARC-BCくらいにはちょい捻りDPをベースにした問題があげきれないくらい出題されてるから明らかに最短距離を求めるアルゴリズム程度の茶色レベルの知識よりはその時点で知識の要求度が高い
424(1): 2024/05/13(月)22:18 AAS
>>422
お前はそんな鳥頭だから一生インコなんだよ
425: 2024/05/13(月)22:19 AAS
君たちはどうイキるか
426(1): 2024/05/13(月)22:20 AAS
>>424
高度アルゴの線引きが甘かったのはそう
セグ木遅延セグ木フローロリハみたいなのを想定してた
427(1): 2024/05/13(月)22:20 AAS
>>426
01BFSなんて茶色緑色diff程度でABCに何回も出題されてるのにそれらと同率な訳がない
428(1): 2024/05/13(月)22:21 AAS
ロリハとセグ木は高度デアではない(鉄則本にも載ってるレベル)し本当適当すぎる
429(1): 2024/05/13(月)22:21 AAS
>>427
いや何の話だよ
430: 2024/05/13(月)22:22 AAS
やはりスレ二分木を採用したほうがいいな
431: 2024/05/13(月)22:22 AAS
流石に昨日のCを知識問題として片付けるのは抽象化が下手すぎる
432: 2024/05/13(月)22:23 AAS
>>428
寒色アルゴを高度アルゴ認定する文脈なのでこれはセーフ
433(1): 2024/05/13(月)22:23 AAS
>>429
知識問題認定するラインの話をそっちが始めたんでしょうが
434(1): 2024/05/13(月)22:24 AAS
高度デアって、nim、grundy、LISとかその辺か？
435: 2024/05/13(月)22:24 AAS
相変わらず書き込みからレートと学歴が透けることよ
でワンパン案件だからレスバしなくていいです
436: 2024/05/13(月)22:24 AAS
>>434
全部水レベルだからそれは中度
437(1): 2024/05/13(月)22:24 AAS
>>433
それは話が混ざってるぞ
ここではARC500点に寒色アルゴは出ない話をしているが知識問の話はしていない
438: 2024/05/13(月)22:25 AAS
寒色アルゴは出ないの意味がわからない
貪欲法もアルゴリズムであることには変わりないのに
439: 2024/05/13(月)22:26 AAS
てかまあ昨日のC解けてない時点でどんなに高く見積もっても水下位層とかだろうしまともに相手しなくていいんだよな
440: 2024/05/13(月)22:26 AAS
セグ木はD以上じゃないと使わないイメージ
逆にグラフアルゴリズム(フロー除く)はC以下でも結構出る
441: 2024/05/13(月)22:27 AAS
DPの高速化パートで普通にARC-BCくらいでも使いますよ
442: 2024/05/13(月)22:28 AAS
CはともかくBでは要求されん
443: 2024/05/13(月)22:28 AAS
昨日のC解けてないやつ(0-1BFS知ってれば解けるから知識問題っていってるやつ)と>>437は別だぞ
444: 2024/05/13(月)22:30 AAS
Bにgrundy置いたのかなりキモかったから二度と置かないでほしい
数強への布教に差し支えるため
445: 2024/05/13(月)22:31 AAS
ARC-Aでワーシャルフロイド(BFSでも可)が出たことあるんだからCで01BFS(ダイクストラでも可)が出ても驚かん
446: 2024/05/13(月)22:31 AAS
てかAに置かれてるならまだしもC500点で置かれてるんだからこの程度の要求知識で文句を言う方がおかしい
447: 2024/05/13(月)22:32 AAS
ダイクストラとか猿でもできるし01必須じゃないならもういいだろ
448: 2024/05/13(月)22:33 AAS
やはり寒色diffに対する言及はインコが頓珍漢なことを言って暴れ出すからABCと同じで書き込み禁止にした方がいいな
449: 2024/05/13(月)22:34 AAS
ちなN<500なら01BFSでなくて普通のBFSでも通る
450: 2024/05/13(月)22:36 AAS
尚更インコ接待だな
451: 2024/05/13(月)22:36 AAS
普通のBFSでどうやるの？
452(1): 2024/05/13(月)22:37 AAS
chokudaiレベルのアドホック力になるとgrundy数も自力導出できるんかな
453(1): 2024/05/13(月)22:37 AAS
どうやるの？って言ってるのわかってなさすぎるだろ
無駄な更新が増えるだけで本質は01BFSと変わらないだろ
454: 2024/05/13(月)22:39 AAS
01BFSの左出し左右入れの「左右入れ」を右入れに改悪するだけ
計算量は悪くなるが最短経路は2Nマス塗り替え以内で抑えられる性質が効いてO(N^3)で耐える
455: 2024/05/13(月)22:39 AAS
nim/grundy数はxorが都合よく性質を満たしてるパートを自分で思いつくのは流石に厳しそう
456: 2024/05/13(月)22:39 AAS
ダイクストラさん
457: 2024/05/13(月)22:39 AAS
AGCのjokerと似た感じの計算量になる
458(1): 2024/05/13(月)22:39 AAS
通らなく無いか？
同じ場所で更新がO(n)回起こり得そうじゃないか？
459: 2024/05/13(月)22:40 AAS
外部ﾘﾝｸ:atcoder.jp
これの解説読んでね
460: 2024/05/13(月)22:41 AAS
where is JAP editorial?
461: 2024/05/13(月)22:41 AAS
>>458
n^3でも通るって話か
でも美しく無いな
462: 2024/05/13(月)22:41 AAS
>>453
は？
463: 2024/05/13(月)22:41 AAS
インコは知能も低いし英語も読めないし本当ダメだな
解説動画でもみなさい
464: 2024/05/13(月)22:42 AAS
01BFS/ダイクストラを知らない数強に配慮してO(N^3)が通るようにしたのか
465: 2024/05/13(月)22:42 AAS
本質が変わってないは嘘だが更新回数の上界的にギリ通るってことねん
466: 2024/05/13(月)22:42 AAS
ダイクストラなんて教科書の最初の方に書いてあるレベルだろ
467(1): 2024/05/13(月)22:43 AAS
それはただ更新回数が悪化してるだけで本質自体は全く変わってないでしょ
468: 2024/05/13(月)22:43 AAS
ダイクストラ、今何diff？
やるだけ茶色？
469: 2024/05/13(月)22:43 AAS
ARCはAGCunratedの数強が一瞬で入水するためにあるらかな
470: 2024/05/13(月)22:44 AAS
いや本質が変わるだろ一見したらTLEするんだから
471: 2024/05/13(月)22:44 AAS
BFSで本来1回見たら2回目以降の更新作業を行わないところを行うようにしても間に合うよって話かなるほど
472: 2024/05/13(月)22:44 AAS
鉄則本の普及で茶色下位になってるかな
CにはおけないからABC-Dにお気持ち程度の捻りを加えて置いて
473: 2024/05/13(月)22:45 AAS
ダイクストラは茶
474: 2024/05/13(月)22:45 AAS
やっぱり変わってないじゃん ちゃんと考えてどうぞ
475: 2024/05/13(月)22:45 AAS
340Dがdiff784だからダイクストラは茶色
476(1): 2024/05/13(月)22:45 AAS
>>467
01BFSは0を左入れすることで余分な更新を無くせることが本質だと思っているので01BFSと本質が同じであると言われるとNoと言いたくなる
477: 2024/05/13(月)22:46 AAS
>>476
今回の問題の本質パートは最短経路を求める部分なので、何で求めようが本質は変わらないでしょの意味でした
01BFSとBFSが別ものなのはあたりまえ
478: 2024/05/13(月)22:47 AAS
ダイクストラ、アカデミアだとマジで初等(知らなきゃモグリ)だけど競プロだと緑近いのか
意外だ
479: 2024/05/13(月)22:47 AAS
学部の最初で取り扱う例レベルだからアカデミアとすら呼べないレベルだろ
480: 2024/05/13(月)22:48 AAS
>>452
grundy数自力導出出来るならSFCなわけない
481: 2024/05/13(月)22:48 AAS
BFSでもN^3で耐える話を真に理解できていますか？
頓珍漢すぎてびっくりしているのだが
482(1): 2024/05/13(月)22:48 AAS
340Dも一見DPっぽくみえるような捻り加えられてるからね
483(1): 2024/05/13(月)22:49 AAS
>>482
ダイクストラもDPの一種ですよ
484: 2024/05/13(月)22:49 AAS
問題の本質的なタスクが解けることに変わりはないって話か
アルゴリズムの本質が同じに読めた
485: 2024/05/13(月)22:50 AAS
BFSの計算量がN^4ではなくN^3になるみたいな話をしてるのかと思ってたら
流石に01BFSの動作原理なんて知ってるに決まってる
486: 2024/05/13(月)22:50 AAS
りんごさんとかくらいだとgrundy数ほどの抽象化まで発想できなくても
grundy数と本質的には同等な解法を考案して解いてたりしそう
487: 2024/05/13(月)22:51 AAS
本質的に同等な解法とはなんですか
そこまで行くとgrundy数と名付けてるかどうかくらいに違いしかないので自力発明でよくないですか
488: 2024/05/13(月)22:51 AAS
>>483
そうだった
iを0から順番に更新していくDPでは無理って話
489(1): 2024/05/13(月)22:51 AAS
BFS使っても本質的には同じじゃない？
の本質の掛かる位置でそこまで煽られても...
490(1): 2024/05/13(月)22:52 AAS
>>489
計算量の話は俺じゃないけどそっちも理解できてますか
491: 2024/05/13(月)22:52 AAS
りんご数というわけか
492: 2024/05/13(月)22:54 AAS
昨日から寒色煽りされまくってるし直近のコンテストの奥の話しようかなって思ったけど普通に解けてる人3桁目弱とか2桁で話せない
あんまり奥の方の言及がないのってこういう理由だったのか
緑上位だった頃には気づかなかった
上下前次1-新書関写板覧索設栞歴
あと 510 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.016s