X

競技プログラミングにハマるプログラマのスレ 145

■ このスレッドは過去ログ倉庫に格納されています
0001仕様書無しさん
垢版 |
2023/12/27(水) 17:54:03.32
競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder http://atcoder.jp/
yukicoder http://yukicoder.me/
Codeforces http://codeforces.com/
CodeChef http://codechef.com/
Project Euler http://projecteuler.net/
CLIST http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
AtCoder Clans http://kato-hiro.github.io/AtCoderClans/

前スレ
競技プログラミングにハマるプログラマのスレ 140
https://medaka.5ch.net/test/read.cgi/prog/1702350568/
競技プログラミングにハマるプログラマのスレ 141
https://medaka.5ch.net/test/read.cgi/prog/1702735806/
競技プログラミングにハマるプログラマのスレ 142
https://medaka.5ch.net/test/read.cgi/prog/1702969685/
競技プログラミングにハマるプログラマのスレ 143
https://medaka.5ch.net/test/read.cgi/prog/1703141733/
競技プログラミングにハマるプログラマのスレ 144
https://medaka.5ch.net/test/read.cgi/prog/1703346239/
0394仕様書無しさん
垢版 |
2023/12/28(木) 17:10:00.59
八問ABCだとGとEx枠に出てくる感じ
2-SATは普通に情報系の基礎教養として知っといていい話だと思うが
0396仕様書無しさん
垢版 |
2023/12/28(木) 17:10:51.21
2-SAT、3-SATこそNPとか計算量周りの話で一番大事なところだから大学の講義で絶対やるだろ　たとえFランでも情報系なら
0399仕様書無しさん
垢版 |
2023/12/28(木) 17:11:47.64
>>391,392
2SAT使う青diffの問題なんてなくね？仕組みは青でも理解できるものだけど
0401仕様書無しさん
垢版 |
2023/12/28(木) 17:12:40.04
2-SATななんならセグ木やBITより基礎教養感強いな
まあ、人間ならどっちも勉強して理解しとけという話ではあるが
0404仕様書無しさん
垢版 |
2023/12/28(木) 17:14:13.58
ABCで勝つためには黄diff橙diff解けるように練習すべきなのに、青diff問題がないからやる必要がないと思ってるのか？
0405仕様書無しさん
垢版 |
2023/12/28(木) 17:15:43.82
>>404
ABC-G以前で出題されたの見たことないんだけど、青レベルならそういう典型身につける前にやるべきことがあるのでは
0407仕様書無しさん
垢版 |
2023/12/28(木) 17:17:05.75
>>402
じょえちゃんねるのドッキリが不成立になり謝罪動画が投稿される
0409仕様書無しさん
垢版 |
2023/12/28(木) 17:19:10.80
自分の中で青というと1800〜1999ぐらいを想像するというのがあるな
0410仕様書無しさん
垢版 |
2023/12/28(木) 17:19:42.39
純粋培養に教えてやるけど、3-SATに帰着させることで多くの問題が多項式時間で解けないことが示されてるからな
これをインコに理解させるのは難しいかもしれませんが
0415仕様書無しさん
垢版 |
2023/12/28(木) 17:22:23.82
それ　
SCCはSCCしてDPとかでまあ普通に使うし青でも知っとくべきだと思うけど、2-SATはマジで使いどころが少ないんだよな
0416仕様書無しさん
垢版 |
2023/12/28(木) 17:22:57.07
やっぱり寒色が暖色のフリして青色から学ぶべきとか語ってんのか？
0417仕様書無しさん
垢版 |
2023/12/28(木) 17:23:43.92
ガチの「青ってこんなこともできないんですよ」案件じゃん
0419仕様書無しさん
垢版 |
2023/12/28(木) 17:25:08.35
概念自体は簡単だからそんなに難しい印象がない
0421仕様書無しさん
垢版 |
2023/12/28(木) 17:26:31.14
むしろだいぶ前に寒色じゃなくなったから正確に把握してないのはある
0424仕様書無しさん
垢版 |
2023/12/28(木) 17:28:54.26
アメリカのFAKEのほうのSATは茶色レベルの難易度なのに
0426仕様書無しさん
垢版 |
2023/12/28(木) 17:32:40.25
2-SATのABCボス問、2-SATが難しいんじゃなくて、普通に何捻りか入れてきてることが多い
0427仕様書無しさん
垢版 |
2023/12/28(木) 17:36:09.76
普通にライブラリチェッカーとして出すなら水色あるか怪しいレベル(SCCやるだけ)なのでそれはそう
ライブラリチェッカー問寄りにしようとすると直球すぎて微妙だし簡単な問題は作りづらい
0428仕様書無しさん
垢版 |
2023/12/28(木) 17:37:18.73
大抵の場合、黄タッチ時に知識だけはかなりついてるから、役に立つ立たない問わずACLレベルのことは履修済ってパターンが多いだろ
0429仕様書無しさん
垢版 |
2023/12/28(木) 17:38:02.20
概念理解なら普通に数時間以内でできると思うしやっても損はしないが、寒色で学んでもそれを実践で使うのはだいぶ先になりそうという話
0430仕様書無しさん
垢版 |
2023/12/28(木) 17:38:52.30
まあACLの奴にやるだけ問題はあるから青でも触りくらいはやってもいいか(実際にレート向上に寄与するかは置いといて)
0431仕様書無しさん
垢版 |
2023/12/28(木) 17:39:54.45
汎用性高くないのに含まれてるってことは、SCCのライブラリ提供してるしついでに2-SATも提供しとくかくらいのノリなのか？
0432仕様書無しさん
垢版 |
2023/12/28(木) 17:43:36.24
twosatはそうなんだろうな
まああとSATは情報系では重要な概念だから教育的に入れとけみたいな考えもあると思う
floor sumの方は数論系で何か一つ付け足すとなった時にyosupoの趣味がでた感じか？
0433仕様書無しさん
垢版 |
2023/12/28(木) 17:45:50.85
何色から使う？という問で青は語弊があったかもな
俺が青のときに理解した、というだけ
あと普通に蟻本にあるし
0435仕様書無しさん
垢版 |
2023/12/28(木) 17:49:51.45
人間は会話できるから和解も可能なんだな
agerも早く人間に進化しろ
0436仕様書無しさん
垢版 |
2023/12/28(木) 17:50:02.22
青上位になってくると普通にボス問のマニアックな知識をたまにあててカンストパフォ出せることがあるから、ABCの橙は射程圏内なんだよな
なおこれまで出たような2SATは普通に考察パートがしっかりあるから当てられない模様
0437仕様書無しさん
垢版 |
2023/12/28(木) 17:53:07.30
でも青ってこんな問題も解けないわけだから、高度典型既習で運勝ちする前に考察力を磨きなさい
0438仕様書無しさん
垢版 |
2023/12/28(木) 17:56:03.09
結局知識勝ちしても黄溜まりで停滞するから、考察力で入黄できるようにしないと未来がない
0439仕様書無しさん
垢版 |
2023/12/28(木) 17:56:31.73
せいじいなら2-SATのボス問も解説してくれるのになあ
0440仕様書無しさん
垢版 |
2023/12/28(木) 17:57:10.29
希望単価を月額100万円未満にしてる馬鹿は開発するな↓

ストップ詐欺被害

月額100万円未満で契約させられる詐欺が多発してます
月額100万円未満の詐欺は開発しないようにして下さい

1次受注金額 200万円 詐欺被害金額 0万円
2次受注金額 160万円 詐欺被害金額 40万円
3次受注金額 120万円 詐欺被害金額 80万円
4次受注金額 80万円 詐欺被害金額 120万円
0441仕様書無しさん
垢版 |
2023/12/28(木) 17:58:15.44
2-SATはクローズと論理演算の関係をまとめとくと考えやすい
0442仕様書無しさん
垢版 |
2023/12/28(木) 17:59:47.26
2-SATのちゃんとした問題って燃やす埋めるみたいな感じで、特有のテクがありそこが難易度を引き上げてる
0443仕様書無しさん
垢版 |
2023/12/28(木) 18:03:24.40
フローの問題とかもそうだけど、いかに知ってるアルゴリズムに落とし込むか、ってところが難しいものね
0444仕様書無しさん
垢版 |
2023/12/28(木) 18:30:34.17
2-SATのABCボス問ってどれのことだろう
ABC277-Ex, ABC210-F 以外になんかある？
0445仕様書無しさん
垢版 |
2023/12/28(木) 18:37:11.07
PASTの認識だとフローとセグ木は同難度のはずなんだが、ABC-Fにフローがいた記憶がないんだよな
0446仕様書無しさん
垢版 |
2023/12/28(木) 18:41:35.23
フロー問題こそ過大評価されてる気がする
ABCで出てくるレベルだと特に
0449仕様書無しさん
垢版 |
2023/12/28(木) 18:55:53.79
>>447
一人だけ話に混じれずにそういうこと言うしかないの可哀想すぎる
人間に、なろう！
0451仕様書無しさん
垢版 |
2023/12/28(木) 19:05:08.26
（デアの話なんてやめて俺のことを見てくれええええええ涙）
0452仕様書無しさん
垢版 |
2023/12/28(木) 19:08:56.67
PASTができた当時よりセグ木がどんどん広まって難易度暴落してるのはあると思う
0454仕様書無しさん
垢版 |
2023/12/28(木) 19:09:46.38
東工大再受験を彼氏から勧められたので研究の合間に受かりたいと思います。蹴る予定なので一般で受けますが、たぶん半年やれば生命理工なら受かるでしょう。
0455仕様書無しさん
垢版 |
2023/12/28(木) 19:17:39.82
この前の関節点出すだけよりはフロー系問題の方が頭使う要素あると思う
0461仕様書無しさん
垢版 |
2023/12/28(木) 19:26:48.41
鉄則本のRMQをほぼそのままABC-Eにおいたらdiffどうなると思う？
0463仕様書無しさん
垢版 |
2023/12/28(木) 19:28:56.72
茶上位ぐらいじゃね
置く位置によっても変わると思う
0464仕様書無しさん
垢版 |
2023/12/28(木) 19:32:35.91
そいつがagerかどうかわからんけど、「年齢の割にすごい」みたいな持ち上げ方は毒にもなるからあんまやらない主義だわ
既にJMO本選には余裕で行けるレベルじゃないか
0465仕様書無しさん
垢版 |
2023/12/28(木) 19:38:50.87
RMQそのままを50分以内に解けって問題なら茶上位でも解きそう
0467仕様書無しさん
垢版 |
2023/12/28(木) 19:48:07.11
maxflowで解ける問題を初見でmincostflowで解こうとする負けパターン結構あるんだよな
0468仕様書無しさん
垢版 |
2023/12/28(木) 19:52:57.91
最小費用流はライブラリを陽に要求されることはそんな多くはないが最小費用流で解ける定式化から発展させる問題なら大量にあるイメージ
0470仕様書無しさん
垢版 |
2023/12/28(木) 20:44:36.79
Candidate Teams for ICPC Asia Championship 2023-24

Yokohama
The University of Tokyo | Speed Star
Tokyo Institute of Technology | tonosama
Osaka University | kotamanegi_marunage
Kyoto University | KUB1sharp
University of Tsukuba | GoodBye2023
Tokyo Institute of Technology | Bocchi The Tech
Kyoto University | Red Phobia
Tokyo Institute of Technology | AMATSUKAZE
National Tsing Hua University | NatsunoHanagaSakuYoihi
Waseda University | hot-k-k1
Chiba University | Type-C
Waseda University | KKT89
The University of Electro-Communications | MCF
0475仕様書無しさん
垢版 |
2023/12/28(木) 21:29:29.92
agerが色々の界隈の天才書き込んでるの何が目的なんだよ
お前自身が勝手に天才になって一瞬で金冠になれよ
0476仕様書無しさん
垢版 |
2023/12/28(木) 21:30:26.75
俺も俵万智ageとか始めちゃっていいの？
0478仕様書無しさん
垢版 |
2023/12/28(木) 21:34:22.23
agerは他界隈の有名人じゃなくてマイナー典型とか隠れた良問を紹介しろよ
0479仕様書無しさん
垢版 |
2023/12/28(木) 21:34:40.68
>>475
何回も言われてるけど、自分がいつも競プロでボコボコにされてるから別界隈の天才を貼って自己投影することで他人の実績でマウント取ろうとしてる(なろうにハマる弱者男性とかと同じシステム)
でもあまりにも知能が低すぎて既に競プロやってる/伸びずに撤退してる人まで貼る始末
0480仕様書無しさん
垢版 |
2023/12/28(木) 21:35:57.33
童貞の実績でヤリチンにマウント取ろうとするのと同じシステムだな
0481仕様書無しさん
垢版 |
2023/12/28(木) 21:36:13.52
過去に半年で青達成した人を半年で橙行けるなとか言ってたの笑った
まあagerはセンター数学が本気でadhocだと思ってるようなお察し野郎だから妄想と現実で2-3色下方修正が入るのは仕方ない
0483仕様書無しさん
垢版 |
2023/12/28(木) 21:45:16.04
N以下の自然数と素数Pに対して、x! mod P(階乗)と1/x! mod P(逆元)のふたつを列挙したい
階乗列挙は誰でもO(N)で実装するが、逆元列挙になるとO(NlogP)が一定数いるというトリビア
0484仕様書無しさん
垢版 |
2023/12/28(木) 21:46:48.18
逆元列挙は蟻本にも載ってるけどまあlogついても構わんとかじゃないの
0485仕様書無しさん
垢版 |
2023/12/28(木) 21:49:25.86
それにlogつけて落ちたこと俺もないな
こどふぉだとダメなケースもたまにありそうだが
0486仕様書無しさん
垢版 |
2023/12/28(木) 21:53:56.25
N≦5*10^5まではlog Pついてもあんま困らないしね
どうせ前計算で一回計算すればいいだけだし
0487仕様書無しさん
垢版 |
2023/12/28(木) 21:54:58.50
こどふぉdiv4(ABC以上のインコ向けコンテストで全完余裕)今夜あるからABC無くて暇してるインコは出るのオススメ
0488仕様書無しさん
垢版 |
2023/12/28(木) 21:55:04.44
本気で落としたいとすると10^7ぐらいは要求しないといけなさそう
0489仕様書無しさん
垢版 |
2023/12/28(木) 21:55:34.09
10^7 とかだったらさすがにlog P 毎回掛けるのはちょっと重いんじゃない？

俺はO(N+logP)でやってるわ
1!, 2!, …, N! の順に列挙
→ N! の逆数で 1/N! を求める
→ 1/(N-1)!, 1/(N-2)! …, 1/1! の順に列挙
っていうブーメランみたいな感じで

ドラケンの記事のやり方だと +log P すら落ちた記憶（些細だが）
0491仕様書無しさん
垢版 |
2023/12/28(木) 21:56:09.20
1/xに対する拡張ユークリッドの互除法とメモ化再帰を行うことで、1/1!, 1/2!, 1/3!, …の順にO(N)で計算できます
いかがでしたか？
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況