競技プログラミングにハマるプログラマのスレ 145
■ このスレッドは過去ログ倉庫に格納されています
でも、簡単に素因数を一個高速で導出できるとi^k列挙でも役に立つし、素数列挙以外でも結構応用がありそうな技術に見える floor sum自体は未だに謎技術感が拭えないけど、一応役に立つ問題はちらほらある（ACLにあるから出題されてるのでは？感もあるが…） 線形篩周りは面白いテクだけど、競プロだと区別不能なんじゃないかなあと思う aclの意義、遅延セグ木を出しまくれるようになったこと（AtCoderにはライブラリゲーは良問になりにくいという思想があるので） floor sum, 直線と格子点の数の関係でイメージしてるけどこれが役に立つ問題あまり解いたことないな CHTとか凸包(幾何系)もだいぶライブラリ力が大事な気がするけど、なんで入れないんだろ floor sumは値側から√N個愚直、答え側から√N個区間を計算すればO(√N) ライブラリ整備したからCHTやるだけ問題また来てくれ ACLの2-SATライブラリも使ったことないな 競技プログラミングやってたけどつまらなくて茶タッチでやめた 黄色タッチまではやったうちに含まれないし、そこまで楽々いけない時点で低知能確定なのではい 八問ABCだとGとEx枠に出てくる感じ 2-SAT、3-SATこそNPとか計算量周りの話で一番大事なところだから大学の講義で絶対やるだろ たとえFランでも情報系なら >>391 ,392 2-SATななんならセグ木やBITより基礎教養感強いな ABCで勝つためには黄diff橙diff解けるように練習すべきなのに、青diff問題がないからやる必要がないと思ってるのか？ >>404 >>402 >>399 自分の中で青というと1800〜1999ぐらいを想像するというのがあるな 純粋培養に教えてやるけど、3-SATに帰着させることで多くの問題が多項式時間で解けないことが示されてるからな >>408 誰も2-SAT使う問題を具体的にあげない時点ではい SCCはわりと使ったけど、2-SATはまだ出番ないな それ やっぱり寒色が暖色のフリして青色から学ぶべきとか語ってんのか？ ガチの「青ってこんなこともできないんですよ」案件じゃん >>410 むしろだいぶ前に寒色じゃなくなったから正確に把握してないのはある >>420 アメリカのFAKEのほうのSATは茶色レベルの難易度なのに 2-SATのABCボス問、2-SATが難しいんじゃなくて、普通に何捻りか入れてきてることが多い 普通にライブラリチェッカーとして出すなら水色あるか怪しいレベル(SCCやるだけ)なのでそれはそう 大抵の場合、黄タッチ時に知識だけはかなりついてるから、役に立つ立たない問わずACLレベルのことは履修済ってパターンが多いだろ 概念理解なら普通に数時間以内でできると思うしやっても損はしないが、寒色で学んでもそれを実践で使うのはだいぶ先になりそうという話 まあACLの奴にやるだけ問題はあるから青でも触りくらいはやってもいいか(実際にレート向上に寄与するかは置いといて) 汎用性高くないのに含まれてるってことは、SCCのライブラリ提供してるしついでに2-SATも提供しとくかくらいのノリなのか？ twosatはそうなんだろうな 何色から使う？という問で青は語弊があったかもな >>433 人間は会話できるから和解も可能なんだな 青上位になってくると普通にボス問のマニアックな知識をたまにあててカンストパフォ出せることがあるから、ABCの橙は射程圏内なんだよな でも青ってこんな問題も解けないわけだから、高度典型既習で運勝ちする前に考察力を磨きなさい 結局知識勝ちしても黄溜まりで停滞するから、考察力で入黄できるようにしないと未来がない せいじいなら2-SATのボス問も解説してくれるのになあ 希望単価を月額100万円未満にしてる馬鹿は開発するな↓ 2-SATはクローズと論理演算の関係をまとめとくと考えやすい 2-SATのちゃんとした問題って燃やす埋めるみたいな感じで、特有のテクがありそこが難易度を引き上げてる フローの問題とかもそうだけど、いかに知ってるアルゴリズムに落とし込むか、ってところが難しいものね 2-SATのABCボス問ってどれのことだろう PASTの認識だとフローとセグ木は同難度のはずなんだが、ABC-Fにフローがいた記憶がないんだよな フロー問題こそ過大評価されてる気がする >>447 （デアの話なんてやめて俺のことを見てくれええええええ涙） PASTができた当時よりセグ木がどんどん広まって難易度暴落してるのはあると思う 東工大再受験を彼氏から勧められたので研究の合間に受かりたいと思います。蹴る予定なので一般で受けますが、たぶん半年やれば生命理工なら受かるでしょう。 この前の関節点出すだけよりはフロー系問題の方が頭使う要素あると思う 地味にmincostflowの使い所も少ないんだよな >>458 鉄則本のRMQをほぼそのままABC-Eにおいたらdiffどうなると思う？ 茶上位ぐらいじゃね そいつがagerかどうかわからんけど、「年齢の割にすごい」みたいな持ち上げ方は毒にもなるからあんまやらない主義だわ RMQそのままを50分以内に解けって問題なら茶上位でも解きそう maxflowで解ける問題を初見でmincostflowで解こうとする負けパターン結構あるんだよな 最小費用流はライブラリを陽に要求されることはそんな多くはないが最小費用流で解ける定式化から発展させる問題なら大量にあるイメージ Candidate Teams for ICPC Asia Championship 2023-24 ■ このスレッドは過去ログ倉庫に格納されています
