[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 176 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
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桁で話せない
あんまり奥の方の言及がないのってこういう理由だったのか
緑上位だった頃には気づかなかった
493: 2024/05/13(月)22:54 AAS
grundy数もDPですか？
494: 2024/05/13(月)22:55 AAS
>>490
無しスレだから全部お前に見えてます
495: 2024/05/13(月)22:55 AAS
俺か、俺以外か
496: 2024/05/13(月)22:55 AAS
それはそう
俺もコンテスト後にABCのボス問の話とかしたいけど流石にキツい
黄色diffでギリギリ 橙は直後はほぼ無理
497: 2024/05/13(月)22:55 AAS
3人が議論すると崩壊するの欠陥だろ
498: 2024/05/13(月)22:55 AAS
せいじいはそれでイキリまくった挙句特定されかけたからな
499: 2024/05/13(月)22:56 AAS
2人で自演して崩壊させたことありゅ
500(1): 2024/05/13(月)22:56 AAS
故せいじいもGかEx解きかけて特定されたんだっけ
501: 2024/05/13(月)22:56 AAS
おれなんて3人で自演したことあるぞ
502: 2024/05/13(月)22:57 AAS
>>500
たまたま難易度逆転しててE欠けF欠けみたいなのが多い回で〜Gまでの感想全て書いて終了した
503: 2024/05/13(月)22:57 AAS
レスバになったらム板に行くルールを作ろう
504: 2024/05/13(月)22:58 AAS
私の勝ちですAC射精完了
505: 2024/05/13(月)22:58 AAS
半日で400レス入る5ch屈指の人気スレ
506: 2024/05/13(月)22:59 AAS
そろそろスレ番がARCの開催数に追いつくな
507: 2024/05/13(月)22:59 AAS
これでもどんぐりのせいで激しく減速しています
508: 2024/05/13(月)22:59 AAS
せいじいが恋しい
509(1): 2024/05/13(月)22:59 AAS
今日も侃々諤々の論争が捗ったな
510(1): 2024/05/13(月)22:59 AAS
>>509
難しい言葉使うな
511: 2024/05/13(月)22:59 AAS
8問制で質の高かった頃の安倍晋三忖度コンテストに帰りたい
512(1): 2024/05/13(月)23:00 AAS
>>510
国弱スギィ
513: 2024/05/13(月)23:00 AAS
せいじい卒業ってちょうど去年くらいか
514: 2024/05/13(月)23:00 AAS
>>512
淫夢語録使うな
515: 2024/05/13(月)23:00 AAS
ワッチョイを否定するのも低能バレを回避するためだからな
516: 2024/05/13(月)23:01 AAS
流石に昨日のDの話はしても特定されるわけないので勿体ぶらずしてどうぞ
517: 2024/05/13(月)23:01 AAS
御三家序列古文sage早生まれsageARC
いつも通り
518: 2024/05/13(月)23:02 AAS
お？やるか？表(ム板)にでろよ
519: 2024/05/13(月)23:02 AAS
ワッチョイつけても俺はいいぞ
学生証と暖色証明書(解説ボタン)はいつでも用意できる
520: 2024/05/13(月)23:02 AAS
ワッチョイするか卒業するか
521: 2024/05/13(月)23:03 AAS
病治ス卒
522: 2024/05/13(月)23:03 AAS
dの話できることなし
523: 2024/05/13(月)23:03 AAS
本スレってどうなったん
524: 2024/05/13(月)23:03 AAS
いうて累積積パートの話も昨日あったし
EFはどうなんだ？まだ解いてないが
525: 2024/05/13(月)23:04 AAS
Fはlog落としがクソキモいから嫌い
上下前次1-新書関写板覧索設栞歴
あと 477 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.020s