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/
0570仕様書無しさん
垢版 |
2023/12/29(金) 10:11:03.05
今週のコンテスト公開されないな、早くしてくれ
0576仕様書無しさん
垢版 |
2023/12/29(金) 13:09:07.84
ttps://rsm9.ha
tenab
log.com/entry/2021/02/01/220408
こういうの？
0579仕様書無しさん
垢版 |
2023/12/29(金) 13:59:38.98
失敗回数をおさえられる操作というのがそんなになさそう
0580仕様書無しさん
垢版 |
2023/12/29(金) 14:42:53.50
昨日ワクチン接種したんだけど、今回はなんか副反応ツレーわ
副反応がキツイ、キツくない、って何の違い？
0582仕様書無しさん
垢版 |
2023/12/29(金) 14:46:53.81
束系の代数構造と相性良さそうだけど、なんかうまくまとめられないかな
0584仕様書無しさん
垢版 |
2023/12/29(金) 16:38:40.01
未だにmRNAワクチンうってるやつはただのバカ
情弱の極み
0586仕様書無しさん
垢版 |
2023/12/29(金) 16:42:07.07
厚労省のサイトには色々データが載っているので読んだうえで判断しましょう
0592仕様書無しさん
垢版 |
2023/12/29(金) 17:25:23.25
なん爺キッズくさいから黙れ
くっさい馴れ合いがしたいならXへ
0594仕様書無しさん
垢版 |
2023/12/29(金) 17:30:39.06
>>590
受験系の天才では無いから凄さが分かりにくいんだよな
数学オリンピックはまぁまぁ知名度はあるけど、ほとんどの人間が実態を把握してないし、競技プログラミングに関しては知ってるやつすらほとんどいない
0595仕様書無しさん
垢版 |
2023/12/29(金) 17:37:55.69
実際、数オリ金と理三ってどっちのほうがすごいんだろうな
0598仕様書無しさん
垢版 |
2023/12/29(金) 17:42:55.31
imo金は毎年日本で1人くらいだけど、競技人口とか科目数を加味したら理IIIとほぼ同等なんじゃないかと思ってる
数学1科目を限界まで尖らせるか、全科目を満遍なく上位0.1%まで仕上げるかみたいな
0600仕様書無しさん
垢版 |
2023/12/29(金) 17:48:03.22
>>596
数オリ金は数学だけ偏差値95あればよくて他の科目は偏差値20でもいいけど、理IIIは全科目満遍なく偏差値80以上にしなきゃいけない感じかな
どっちが難しいかは人による
0601仕様書無しさん
垢版 |
2023/12/29(金) 17:50:40.97
マーーーータagerの理三age
理三最低点超えてた俺もage対象に入ってるってことで
0607仕様書無しさん
垢版 |
2023/12/29(金) 17:58:49.80
>>600
理三は満遍なく偏差値80にしなくても受かるし、偏差値の上げやすさが線形だと思ってる時点でエアプすぎる
0608仕様書無しさん
垢版 |
2023/12/29(金) 18:00:06.63
てか東大模試以外の偏差値気にしたことないからアレだけどそれ以外のインコ向け模試なら偏差値80とかに自然になりそうか
0611仕様書無しさん
垢版 |
2023/12/29(金) 18:03:15.19
そもそも過去のIMO金er、大体理三か理一上位合格じゃね
0613仕様書無しさん
垢版 |
2023/12/29(金) 18:05:05.56
agerはスルーして線形篩の話をしてたスレに戻そう
0614仕様書無しさん
垢版 |
2023/12/29(金) 18:09:48.93
篩の話は人間なら全員知ってる話だったのでもういいですよ
0617仕様書無しさん
垢版 |
2023/12/29(金) 18:19:58.41
agerのおかげでイキる口実ができたとばかりにイキイキしちゃうやつは同レベルだと自覚しろ
0623仕様書無しさん
垢版 |
2023/12/29(金) 18:39:35.93
agerは真面目にageたいたいならもっと調査してからにしろよ
毎回的外れなこと言ってるせいで相手されてないのに学習しねえな
0626仕様書無しさん
垢版 |
2023/12/29(金) 18:49:20.18
agerって差別発言とかスレ長とかnimみたいな不穏要素がないから
数年経つとスレあんま見ない人にとっては伝聞で少し面白い芸人みたいな枠に収まる可能性がそこそこあるな
0627仕様書無しさん
垢版 |
2023/12/29(金) 18:51:10.73
的外れって部分には反論しないってことは自覚はあるんだな
ほんと学習能力ないし緑水で停滞するのも納得
0628仕様書無しさん
垢版 |
2023/12/29(金) 18:51:29.35
今ですら誰なのかわからないのだが
特定個人？概念？
0631仕様書無しさん
垢版 |
2023/12/29(金) 18:53:47.10
ワイはいつも即飛びついてる君のほうが怖いと割と思っとるやで
0634仕様書無しさん
垢版 |
2023/12/29(金) 18:56:46.80
一人称ワイのなん爺キッズインコ最近飛来してきたよな
0637仕様書無しさん
垢版 |
2023/12/29(金) 18:58:16.16
淫夢は野獣先輩らの人権を侵害しているのでなんG語の方が標準になって欲しい
0638仕様書無しさん
垢版 |
2023/12/29(金) 18:59:36.18
昼のゴシスレ部門をやってるインコ軍団はやはりレベルが低いな
そりゃ人間は夜のデアスレ部門まで来ないわな
0639仕様書無しさん
垢版 |
2023/12/29(金) 19:02:24.49
ゴシスレ部門はデアの話についていけないどころか日本語すら怪しい奴も混じってるな
0642仕様書無しさん
垢版 |
2023/12/29(金) 19:05:48.82
>>587
いつも副反応あんまないからなんもしてなかったけど
その投稿のあとに解熱剤飲んで寝てたらめっちゃ楽になった
0644仕様書無しさん
垢版 |
2023/12/29(金) 19:06:38.39
コンテストの時間帯までは昼、それ以降は夜です(コンテストに生活リズムを合わせるべきなので)
0645仕様書無しさん
垢版 |
2023/12/29(金) 19:07:02.76
実際コンテスト後には流石にデアの話題が必ず増えるし
0646仕様書無しさん
垢版 |
2023/12/29(金) 19:08:36.03
ジャップランドに住んでる奴まだいたのか
こっちは昼だが
0649仕様書無しさん
垢版 |
2023/12/29(金) 19:16:29.07
ABC251Exの解説読んでるけど
C(N,k) = C(N//D, k//D) × C(N%D, k%D) mod P
でほんまか？ってなってる
D = P^x　xはD>√Nを満たす最小自然数
0651仕様書無しさん
垢版 |
2023/12/29(金) 19:20:18.84
松本人志がそこそこ嫌われているという事実に衝撃を受けてる奴www
0652仕様書無しさん
垢版 |
2023/12/29(金) 19:21:13.32
C(N,k)
≡ C(N//D, k//D) × C(N%D, k%D) mod D
≡ mod P^x
≡ mod P
ってことか　理解
0654仕様書無しさん
垢版 |
2023/12/29(金) 19:24:12.05
なん爺キッズインコじゃなくてせいじいキッズならデアの話も出来たのになあ
0655仕様書無しさん
垢版 |
2023/12/29(金) 19:26:42.51
nCk mod p、pが素数の場合はルーカスの定理で求まるようだけど、pが一般の自然数の場合でも頑張れば求まりそうに感じる
0656仕様書無しさん
垢版 |
2023/12/29(金) 19:47:10.40
n,kが巨大な場合以前の問題として、nCr mod 合成数って多倍長整数を使わず計算できるの？
modを素因数分解してGarnerで復元は、modが偶数のときに詰む
0657仕様書無しさん
垢版 |
2023/12/29(金) 19:52:23.93
>>656
一応、pが小さい場合に限定して考えている
自分の考えている方法ではO(p + logn)ぐらいかかりそうなので
0658仕様書無しさん
垢版 |
2023/12/29(金) 19:57:50.83
>>657
マジでわからんのだがどうやるんだ
極端な例だと nC2 mod 6 の計算ですら、mod6に2!の逆元は存在しないせいで無理だなと感じてる
0659仕様書無しさん
垢版 |
2023/12/29(金) 20:02:02.98
多倍長整数で愚直計算してから最後に割ればnCk mod 合成数は求まるが
この計算量をO(k)と評価するのは無理がないか
0661仕様書無しさん
垢版 |
2023/12/29(金) 20:09:01.18
うろ覚えなんだけどGarnerって例えばmod 6のときはmod　3での2の逆元を求められればいいんじゃなかったっけ
素因数分解できたらいつでも使える印象なんだが
0662仕様書無しさん
垢版 |
2023/12/29(金) 20:09:17.69
>>660
p=3の場合が出来るのって要はlucasの定理が裏で効いてるわけだし、一般の場合に拡張するには無理じゃね
0663仕様書無しさん
垢版 |
2023/12/29(金) 20:15:18.37
kが小さい場合は ARMERIAさんの 「合成数modでの二項係数を用いた数え上げ」が参考になる
kが大きい場合はlucasの定理の素数べき版が出来れば出来るはずだが、自分は詳しくない…（かなり複雑だが確かあったはず）
0664仕様書無しさん
垢版 |
2023/12/29(金) 20:17:04.46
mod p^nのときは素朴にlucasの定理を適用できそうな予感がする
飯食い終わったら確かめてみるわ
0665仕様書無しさん
垢版 |
2023/12/29(金) 20:19:18.38
>>662
確かに一般化は早計だったかも
けど、リンク先の図を見る感じp=4とかは普通に行けそうだと思ってる
0666仕様書無しさん
垢版 |
2023/12/29(金) 20:24:51.43
すまん頭冷やしたらできるにきまってた
nCk mod Mを計算したいとする
Lucasの定理からn,k<Mに帰着できて、これが全列挙できればOK
でMを素因数分解して、分母・分子に出現するMとの共通素因数は出現個数をカウントすればよいため
0667仕様書無しさん
垢版 |
2023/12/29(金) 20:26:50.96
リュカの定理は法が素数でないと使えないため終了した可能性があるな
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況