[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 176 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
391: 2024/05/13(月)21:57 AAS
流石に01bfsというか最短距離を求める問題は茶色レベルの前提知識だからARC-500で出すなって言われても困るだろ
392: 2024/05/13(月)21:57 AAS
そんなこと言ったら何も出題できないから
393: 2024/05/13(月)21:58 AAS
インコ特有の他責思考
394: 2024/05/13(月)21:59 AAS
赤紫と青紫の問題に分割するパートは考察といっていいんじゃないか簡単だけど
01BFSパートは普及しすぎているのではい
395: 2024/05/13(月)21:59 AAS
まあ自分の精進が足りてなくて知識自体不足しまくってるのはそう
396: 2024/05/13(月)22:00 AAS
普通に普段のARC-500とかARC-Cって算数パズル問題というよりもABCよりもさらに捻った応用問題って感じだけど何言ってんだこいつ
フローみたいな高度寄りの典型はARCの中盤で基本出題されないけど普通にABC-Fまでの知識は前提として要求されます
397: 2024/05/13(月)22:00 AAS
マジで明らかに普段のARCの実態がわかってないインコがピーピー文句言ってるのムカつくわ
398: 2024/05/13(月)22:01 AAS
AGCならまだしもARCって言うほど算数パズルアドホック問題ばかりじゃないぞ
399: 2024/05/13(月)22:01 AAS
のだ氏もARC出ろなんて言ってないぞ
ARCはやめとけ
400: 2024/05/13(月)22:02 AAS
そもそも01BFSは本質じゃないだろ
最短経路が解けるなら何でも良いんだし
401(1): 2024/05/13(月)22:02 AAS
ARC～500点問題に寒色アルゴが要求されたことあるか？
600点以上ならわかるが
402(1): 2024/05/13(月)22:02 AAS
>>401
実家DPなどいくらでもある もっと問題解けよ
403(1): 2024/05/13(月)22:03 AAS
>>402
いくらもはないだろ
平衡二分木が使えたらセグ木を知らなくても解けるように作られてるんじゃないのか
404: 2024/05/13(月)22:03 AAS
最近見ないけど昔はLIS出まくってたし
405: 2024/05/13(月)22:04 AAS
ARC500点以下は数強接待問題置き場なのでアルゴ問はないと言い切りたいのだが
406(1): 2024/05/13(月)22:04 AAS
>>403
なってねえよ
どうせまともに問題埋めてないインコだろうけどARCのBCくらいまでの問題くらい全部解いてこい
407: 2024/05/13(月)22:05 AAS
>>406
お前が反例を挙げればよいため
408: 2024/05/13(月)22:05 AAS
確かに数学得意タイプは今回のARC勝て無さそう
409: 2024/05/13(月)22:05 AAS
考察パートが面倒なだけで、結局は典型に落とし込むのがむしろ普通では
410(1): 2024/05/13(月)22:06 AAS
全部解いてこい（俺は解いてないし反例も上げられないけど）のカスインコ仕草やめてね
411: 2024/05/13(月)22:08 AAS
インコ人狼始まってるやん
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回目以降の更新作業を行わないところを行うようにしても間に合うよって話かなるほど
上下前次1-新書関写板覧索設栞歴
あと 531 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.024s