競技プログラミングにハマるプログラマのスレ 145
■ このスレッドは過去ログ倉庫に格納されています
agerが色々の界隈の天才書き込んでるの何が目的なんだよ
お前自身が勝手に天才になって一瞬で金冠になれよ agerは他界隈の有名人じゃなくてマイナー典型とか隠れた良問を紹介しろよ >>475
何回も言われてるけど、自分がいつも競プロでボコボコにされてるから別界隈の天才を貼って自己投影することで他人の実績でマウント取ろうとしてる(なろうにハマる弱者男性とかと同じシステム)
でもあまりにも知能が低すぎて既に競プロやってる/伸びずに撤退してる人まで貼る始末 童貞の実績でヤリチンにマウント取ろうとするのと同じシステムだな 過去に半年で青達成した人を半年で橙行けるなとか言ってたの笑った
まあagerはセンター数学が本気でadhocだと思ってるようなお察し野郎だから妄想と現実で2-3色下方修正が入るのは仕方ない N以下の自然数と素数Pに対して、x! mod P(階乗)と1/x! mod P(逆元)のふたつを列挙したい
階乗列挙は誰でもO(N)で実装するが、逆元列挙になるとO(NlogP)が一定数いるというトリビア 逆元列挙は蟻本にも載ってるけどまあlogついても構わんとかじゃないの それにlogつけて落ちたこと俺もないな
こどふぉだとダメなケースもたまにありそうだが N≦5*10^5まではlog Pついてもあんま困らないしね
どうせ前計算で一回計算すればいいだけだし こどふぉdiv4(ABC以上のインコ向けコンテストで全完余裕)今夜あるからABC無くて暇してるインコは出るのオススメ 本気で落としたいとすると10^7ぐらいは要求しないといけなさそう 10^7 とかだったらさすがにlog P 毎回掛けるのはちょっと重いんじゃない?
俺はO(N+logP)でやってるわ
1!, 2!, …, N! の順に列挙
→ N! の逆数で 1/N! を求める
→ 1/(N-1)!, 1/(N-2)! …, 1/1! の順に列挙
っていうブーメランみたいな感じで
ドラケンの記事のやり方だと +log P すら落ちた記憶(些細だが) 1/xに対する拡張ユークリッドの互除法とメモ化再帰を行うことで、1/1!, 1/2!, 1/3!, …の順にO(N)で計算できます
いかがでしたか? 俺もそのブーメランパンツみたいな感じでやってる
logP消すトリッキーなやつかっこいいけど本番だと忘れちゃう nCr mod計算機はみんなブーメランで実装してると思ってたわ 二項係数、ドラケンライブラリパクってるけど困ったことないな 中学受験してない人は受験の実態を知らないから機会損失してるんだと思ってたってツイート流れてきて結構びっくりしてる。都会の人はそういう認識なのか…
逆に9割の人当てはまらないものを一般論化するツイートするの怖くないか…?大学受験に置き換えてもなおツイートするの躊躇ってしまうと思う まあ世の中の大半の人はAC射精完了の悦びを知らずに機会損失を抱えながら生きてるわけだし今に始まったことではない >>497
まあ実際に受けるかどうかは置いといて、中受の選択肢を検討する機会くらいはあってもいいよねってことが言いたいんじゃない Lucasの定理使う問題で大昔激冷えしたトラウマでちんちんがしなしなになってる 都会の人っていっても東京都にも教育困難校とか専門学科の高校もあるからX民のイキリだけ見て一概には言えないやで AGCではlucasの定理(二項係数の偶奇)結構頻出な気がする
知らなくても実験で頑張れば発見できそうだけど、知ってると時短できる 結局中受支配の原理、TKNDKS支配則から逃れられないので そもそも、競プロ知ってる中でも95%以上がインコなんだし、多数派がどうだからみたいな思考は、インコに迎合して何かしたいという下心を持っているインコルエンサー的な発想なんだよな
割とどうでもいい shuffle(1,N)
あああああああああああああああああああああああああああああああ!!!!!!!!!!!(ブリブリブリブリュリュリュリュリュリュ!!!!!!ブツチチブブブチチチチブリリイリブブブブゥゥゥゥッッッ!!!!!!! ) もしかしてルーカスの定理ってのでnCr mod3が一発?
インコ俺が頑張ってパスカルの三角形を睨みながら作ったライブラリ無駄だったのかよ あのAGC回マジで鬱病だから嫌い
後lucasの定理といえば0、1、2で何か足し算的なことする奴だっけ? >>507
lucasの定理は任意mod(素数modだったかも)に対して使えるね確か まあその経験は何かで役立つよ、知らんけど
なんでもかんでも強い定理やデータ構造でできるよねで済ませてたら思考力伸ばす機会が減る Lucasの定理関連でABC251Ex解説の、二項係数の区間和がクエリO(1)になる記事に行き着いた
おもしろそうだとおもった projecteulerってどこまで解法に関すること言及していいのかわからなくて扱いづらいんだよな paizaほど固く禁止されてないけど、あまりしないでほしい的なスタンスらしい
なにかの類題として貼るぐらいなら結構やってる人多いけどな Osaka University | kotamanegi_marunage
たまねぎくんICPC finalか たまねぎ、阪大に関するツイートしてたけどやっぱり阪大生なのか >>518,519
赤の他人巻き込むの普通にやめといた方がいいぞ またガイジスレ民のICPC嫉妬が爆発してしまうのか UT内二位チームもかなり強かったはずだが、なかなか厳しいルールだ 🧅持ち上げてるしょうもない奴一緒に逮捕されてどうぞ 🧅持ち上げると逮捕されちゃうのか
法律灰だから知らなかったわ 阪大生でもageたらヘイト買うのかよ
スレの東大支配的er怖すぎ 🧅は大喜利してるだけで裁判になりかねない怖さがある
現実的には安全だろうが まだたまねぎ観察でいらついてるのか
所持アカウント数をXとしてO(X)でブロックが可能でありこれは十分高速です 逆に5chが終わったらガイジスレ民どこにいくんだろうな >>514
Congratulations, the answer you gave to problem 148 is correct.
AC射精完了 インコは語源がゴリ押しするから置いといて、AC射精完了はXでも流行っても良くね?とは思う
nimさん任せました tourist div4で解答hackされてて順位四桁代まで落ちてて草
見た目だけでなく心まで灰インコになってしまったなんて悲しいよ こどふぉ童帝だけど有名だとhack狙われやすいとかあるの?かわいそ >>553
こどふぉくらい出ろよfake野郎がよ
別にアンレだから関係ないし、コンテスト後hackあるのはdiv3以下(えでゅふぉ含む)だけだけどね どのみち最後にみんなのhackで全体をジャッジし直すから、やりがちな嘘は一緒に落とされる set解を落とされてPython勢が阿鼻叫喚になりそう こどふぉエアプだけどsetとdictの撃墜法そんなに有名なのかよ
Wrapper噛ませてハッシュ値だけbit乱択すればいいんだっけ Wrapperとはこれのことね
PyPyのsetはPythonのdictと同じハッシュ値計算法を採用しているから原理的にはこれで対策可能なはず
ttps://codeforces.com/blog/entry/101817 unordered系とかロリハみたいなハッシュ依存のデ・アは対策してないと落とされるね 乱数に雑に時間を噛ませてもhackのプロに提出時間とかから解析されてやられることもあるらしいから、CPUの内部時間とかにしないといけないみたいな話も聞いたことある(詳細は違うかも) >>559
これ去年あたりのdiv3か何かでPython勢が撃墜されまくって有名になったんだっけ >>560
unordered系は最悪使わなくてどうにでもなるけど、ロリ八は使う機会多いから対策してないと困るな >>550
AcceptedのACとかけていてちょっと上手い ■ このスレッドは過去ログ倉庫に格納されています