競技プログラミング総合スレ 65

■ このスレッドは過去ログ倉庫に格納されています
2022/12/26(月) 12:47:37.63ID:CkzYHyzir
!extend:checked:vvvvv:1000:512
↑2行になるようにする

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

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

※前スレ
競技プログラミング総合スレ 64
https://mevius.5ch.net/test/read.cgi/tech/1664700238/
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
2022/12/30(金) 09:57:28.45ID:H46YuG/U0
運営がワールドワイドならそれも可能だろうけどこれはしゃーねえべ(´・ω・`)ぽれはお盆の時期とか出たくないのに逆にコンテスト生やしてくるし
2022/12/30(金) 12:12:30.73ID:1cdhane2r
俺も正月はいいや、暇だけど実家だから回線悪い(´・ω・｀)
2022/12/30(金) 12:51:42.69ID:E9c39SFN0
ｍｈバチャしようぜ！
2022/12/30(金) 12:52:06.77ID:E9c39SFN0
ｍｈは謎の入力ミス
2022/12/30(金) 14:52:31.97ID:DWxAyMkpM
整数と場合の数だと大学への数学のやつかな
あれを全部スラスラ解けるぐらいにしとくと捗る
43デフォルトの名無しさん (ﾜｯﾁｮｲ e355-s0Sd)
垢版 |
2022/12/30(金) 14:57:53.70ID:3r6Oj/Bn0
初等整数論とか組合せ論の初歩についてあまり詳しくないけれど、
プログラミングコンテストでは強いっていう人はいるんですか？

プログラミングコンテストで強い人はみな数学にも強いのではないですか？
2022/12/30(金) 15:18:16.52ID:jg66J2pLM
プログラミングコンテストにもいろいろあって、競技プログラミングのアルゴリズムという分野のコンテスト（具体的にはAtCoderのABC、ARC、AGCは全部そう）は、整数、組合せ論の問題が離散数学の一部として出題されるので、もろに成績に関係する
一方で、ヒューリスティックだったりKaggleに関しては、実はそうでもないんじゃないかという気がする
当然、基礎的な能力として、整数と組合せ論を最低限勉強しておいた方が離散数学的な操作に慣れて思考の助けになるところはあると思うし、勉強さえすればレベルの高いところまでできるような人がいずれのコンテストでも上に来ると思うけど
2022/12/30(金) 15:41:25.54ID:SISDjQCo0
組合わせ論・数論の精選とかパーフェクトマスターみたいな数オリ用対策用の参考書って競プロにも役立つの？たまに買ってる人見かけるけど黄色以上で効くのかな
2022/12/30(金) 15:43:17.20ID:bLivZhNAM
競プロに必要なことは競プロで身につく派
47デフォルトの名無しさん (ﾜｯﾁｮｲ e355-s0Sd)
垢版 |
2022/12/30(金) 15:47:04.57ID:3r6Oj/Bn0
繁野麻衣子著『ネットワーク最適化とアルゴリズム』を買いましたが、積読状態です。
この本は競技プログラミングに役立ちますか？
2022/12/30(金) 15:54:21.28ID:1cdhane2r
あっとこなら問題解くだけで良さそう
2022/12/30(金) 15:58:00.92ID:jg66J2pLM
いつだったか、数オリ高度典型の幾何がAGCかARCに出てて話題になったからごくたまに効くんじゃないか
2022/12/30(金) 16:03:39.51ID:mLpRFjn60
>>47
未読なので目次見ただけだけど、この本のアルゴリズムは全部競プロで頻出だと思うので、知らない知識を摂取するって意味だとどれも役立ちそうかな？
51デフォルトの名無しさん (ﾜｯﾁｮｲ e355-s0Sd)
垢版 |
2022/12/30(金) 16:10:15.82ID:3r6Oj/Bn0
>>44,48,50
ありがとうございました。

>>50
読んでみます。
2022/12/30(金) 18:13:16.86ID:EYdMYpIMM
純粋な学術書は体系的すぎて競プロで使うには多く説明しすぎてることもあるから、効率がいいかはわからんな
ただ、普通に競プロ関係なく勉強になるところはいい
2022/12/30(金) 18:23:53.70ID:iKE0Xuujr
最悪計算量と何ができるか知ってるだけでも競プロでは使えるな
順位クエリ処理できる二分探索木の仕組み分かってないけど他人のライブラリコピペして使ってるわ
2022/12/31(土) 13:45:22.58ID:iNV3O62Z0
新年ABCもう三つも入ってるのか
2022/12/31(土) 13:50:39.96ID:Yd+ifoMYa
なかなか灰色から上がることが難しそうですね...
とりあえずアルゴリズム×数学 本 か鹿本(AtCoder入門)を買ってみませんか
茶色に上がってみましょう
2022/12/31(土) 13:51:25.78ID:iNV3O62Z0
和を積に変換
https://twitter.com/noshi91/status/1608869946792235008

和のままで十分性質がいいじゃん！と先入観で思ってしまうが、あえて多項式を使った式を介して積にした方がtop treeに乗せやすいみたい
面白い
https://twitter.com/5chan_nel (5ch newer account)
2022/12/31(土) 13:54:08.95ID:iNV3O62Z0
>>55
数学が苦手な人は入茶でもかなり時間かかる時代な気がするね
灰色を分割して階級をさらに分けるのは真面目にありだと思ってるけど
2022/12/31(土) 14:48:43.15ID:kgmqtCAB0
toptreeとか初めて聞いたわ
2022/12/31(土) 14:50:30.16ID:VUYQSQV/M
部分列（連続ではない）の和の総和は[x]Π(2+ax)か
この場合はそんなに役立ってる感ないが
2022/12/31(土) 15:00:28.46ID:++4zxiH/M
TopTreeて高度典型みたいなやつだろ
俺も名前しか知らん
2022/12/31(土) 15:07:27.00ID:ST9eXwUwM
LC木の上位互換でLC木に乗らないものが乗ったりするが、そもそもLC木自体がマニアックでAtCoderではなかなか使用機会ないだろうな
強いデータ構造がなきゃ解けない問題、強いデータ構造で一瞬で解けてしまう問題をAtCoderがそもそも好まないというのもあるし
2022/12/31(土) 15:33:19.70ID:ST9eXwUwM
データ構造に載せるモノイド、頑張れば多項式か行列に帰着できる説
2022/12/31(土) 15:51:06.59ID:uDVZ4h8P0
半束とかはモノイドだけど多項式や行列にはならなくないか
2022/12/31(土) 16:04:37.43ID:ST9eXwUwM
適当に和に相当する演算を導入して半環の積にできんかとか考えたけど無理か
2022/12/31(土) 18:13:36.09ID:iNV3O62Z0
あまり半束であって束じゃない例について考えたことなかったけど根付木のLCAとか？
66デフォルトの名無しさん (ﾜｯﾁｮｲ 1a55-9yt5)
垢版 |
2022/12/31(土) 18:22:00.74ID:zJ9NYHz+0
>>65
ところで、束論はどの本で勉強しましたか？
離散数学の本にすこしだけ書いてあることがありますが、役に立ちますか？
2022/12/31(土) 18:40:09.52ID:iNV3O62Z0
>>66
min, maxの一般化であるってことと定義を知っているってだけで、まともに勉強したことないかなあ
どこで最初に知ったんだろ、雪江代数にあったっけ？
ゼータ変換を束を使って捉え直すことができるみたいなのはあった気がするけど、束論自体をつきつめることが直接競プロにプラスになる感じではない印象
というか、抽象代数の勉強は全般的にそんな感じな気がする
2022/12/31(土) 18:59:35.78ID:zUUU5DPH0
(1+a_k)の積を微分していったら定数項に基本対称式が全部出るのか 嬉しいかなあ
2022/12/31(土) 19:05:33.95ID:iNV3O62Z0
今日日モーメント母関数がそんなにうれしいものなのかという話になりそう
2022/12/31(土) 19:28:10.86ID:fzjWly+gM
何の捻りもないけど、セグ木にのせてrange M次対称式 query（与えられた区間内の要素のM次対称式を出力）がQMlogNで解ける
2022/12/31(土) 19:33:39.16ID:fzjWly+gM
と思ったけどlogMつくか
更新ないんならセグ木に乗せるんじゃなくて累積和でやる方がいいな
2022/12/31(土) 23:33:15.73ID:iNV3O62Z0
どっかで出てそうと思ってelementary symmetric polynomials segment treeとか検索してるけど意外とないもんだ
73デフォルトの名無しさん (ﾜｯﾁｮｲ 1a2f-ed2K)
垢版 |
2023/01/01(日) 10:08:11.89ID:30E/zMtT0
https://nunjuk.in/35c41f
74デフォルトの名無しさん (ﾜｯﾁｮｲ 1a55-9yt5)
垢版 |
2023/01/01(日) 10:12:49.91ID:+0Q+h7mh0
>>67
ありがとうございました。
2023/01/01(日) 13:05:49.08ID:jk3nqRU4M
初ARC初AGCはいつ入るか
2023/01/01(日) 17:23:02.16ID:HtIB66xPr
鯖のcpu性能が上がったせいで過去の問題が別の解法(計算量悪化)で通せるようになることってあるのかな？
パソコン新しくしようとしてて気になった
2023/01/01(日) 17:35:44.53ID:jk3nqRU4M
N=2*10^5だとガチガチにチューニングしたC++で非想定が通ってしまうからN=3*10^5にしたみたいな問題だと、普通に非想定通るようになってそうだな
2023/01/01(日) 18:51:37.63ID:BuEF5d0U0
2014年くらいの問題でそういうのあったと思う
2023/01/02(月) 16:31:00.87ID:5iFotiMhM
お、ARC生えたか
2023/01/02(月) 18:38:41.71ID:1lMhDqk90
ABCと土日逆転してるのって何か意味あるのかな
2023/01/02(月) 19:37:24.20ID:Bxk6jeghM
土夜と日夜だったら普通の人は土夜の方が予定入りやすいとかあるんかな
2023/01/02(月) 22:43:11.18ID:xXWO03uC0
日曜ははよ寝たならんか
2023/01/02(月) 22:49:42.58ID:mvKrG9xT0
テレワークで出勤時間なくなってからは24時までに寝られれば十分になった
84デフォルトの名無しさん (ﾜｯﾁｮｲ 5bb3-3363)
垢版 |
2023/01/03(火) 00:54:06.77ID:u0M4IWsD0
AtCoderの過去問って他人の提出検索できるけど、case_11.txt だけ間違えてるやつ一覧みたいのって取ってこれるんかな？
2023/01/03(火) 01:00:58.84ID:l1uyhUQar
同じようなテストケース通し具合のコードを持ってくるサービスあった気がする
探したけど見つからなかった
確か赤コーダーTLで見つけたはず
86sage (ｵｯﾍﾟｹ Srbb-A544)
垢版 |
2023/01/03(火) 01:14:46.33ID:3U7/noadr
>>84 >>85
もしかして: AtCoder Companions
2023/01/03(火) 01:39:20.81ID:5KR4gJydM
言語仕様の勘違い由来のバグ取りはかなり気付くの難しいから、初心者がそういうの見つけるのに使えそうだな
2023/01/04(水) 01:26:53.42ID:WeNv9SlE0
今年こそ青に定着したいのに三が日何もやってねえ...(´・ω・`)
2023/01/04(水) 08:04:52.46ID:aNwmJoG10
正月で生活リズムが整っちゃってこどふぉに出られなくなっちゃった
2023/01/04(水) 15:05:35.57ID:JS//sD6wM
Hello 2023普通に良コンテストだったぞ
ドンマイ
2023/01/04(水) 22:15:22.80ID:vSzNCwvu0
えAtCoder Companions有能すぎるんだけど. これ何でテンプレ入ってないん?
2023/01/04(水) 23:19:19.62ID:mr/FCdH/0
TL少し長めの問題なら、10^9回計算する解法でも通るんだね（想定解法じゃなかったけど）
2023/01/05(木) 06:17:26.70ID:7AKtp3Yz0
重複組合せの式nHrで、整数のオーバーフローをできるだけ避けて計算したいのですが

とある、場合の数を数える問題で、普通はたぶんDP的に解くんだけど、規則的な形だった
ので、「これって重複組合せじゃん」と見抜いたんですよ
でnHrを例の階乗の公式(n+r)!/n!/r!で計算して、テストケースを走らせるとnやrが小さい
のは通るのでやはりおkらしい。ただnやrが大きくなると階乗がオーバーフローしてしまう
解が数式で求まったのに数値的にはそんなに便利じゃないって?

でも普通nHrの計算って分子と分母でキャンセルして結果は大きくならないことが多い
ですよね。うまいこと変形したらオーバーフローしなさそう。もしそういうのが既にあれば
nHrの漸化式みたいので計算する手もありそう、って結局DPみたいなことしてる気がw
2023/01/05(木) 10:09:29.03ID:36BPqP5u0
ちなみにnとrはどういう大きさの値？
2023/01/05(木) 10:51:51.53ID:7AKtp3Yz0
>>94
どちらも2から60ぐらいの間の整数がランダムな感じでセットされるようです
2023/01/05(木) 11:18:12.30ID:36BPqP5u0
>>95
(n+r)!/n!/r! = n+r C r
と変形して、あとはKnuthのTAOCPに載ってるオーバーフローしにくいやり方で組み合わせを計算してみよう
https://stackoverflow.com/questions/1838368/calculating-the-amount-of-combinations/1838732#1838732
97デフォルトの名無しさん (ﾜｯﾁｮｲ 362a-3363)
垢版 |
2023/01/05(木) 12:36:04.14ID:BpZRjrYb0
パスカルの三角形で計算する方が確実かな
2023/01/05(木) 12:51:55.08ID:7AKtp3Yz0
>>96
どうもです。が、n, mは実際には100ぐらいまでいくようで（すみません）、
リンク先の最初のコードだと 100 C 99 とかで間違った答えが。おっとクヌース先生敗北?

こういう場合は普通にCの性質より 100 C 99 = 100 C (100-99) = 100 C 1 とすれば
精度も計算量も良さそうです
というわけで... 全テストケースクリアしました! ありがとうございます
2023/01/05(木) 13:03:57.95ID:dpF3fKIy0
100C50はint64に収まらないからね
2023/01/05(木) 13:23:09.26ID:7AKtp3Yz0
>>99
そうですね、nCrで r=n/2付近はでかい数になりますよね
テストケースではそういう場合は除外されているようです

そういうわけで、組み合わせを直接計算するとテストケースでは64bit整数がいるんですが、
組み合わせの直接計算でなく、DPで再帰的に場合の数を計算するようなコードだと
32bit整数で大丈夫な感じなんですが... ええと
2023/01/05(木) 13:39:53.75ID:7AKtp3Yz0
ああそうか、それが実質的には >>97 パスカルの三角形を上向きに登っていくのと等価なの
かな。三角形がでかい場合はあんま三角形の底辺の真ん中の方には行かない場合のみで
と自己納得w
2023/01/05(木) 14:48:33.70ID:WkAYqVn/d
よくわからんけど答えが32bit整数に収まる程度なら適当に大きめのmodとればいいんじゃないの
2023/01/07(土) 18:03:15.80ID:Fs1C7h8fp
ARC3週連続か
2023/01/07(土) 19:51:43.95ID:SPR4wSEy0
ARC生えまくり
嬉しいけど息切れしないか心配
105デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:45:57.01ID:LoL6HnAVa
Dの解説読んでもわけわからん
まず、割り切れるのがわかってるんだから、iの最大値なんて関係なくない？

iの2乗で割り切れる時に解が見つかるとして計算したけど時間内に解が求められなかった。
糞問題じゃないのこれ？
2023/01/07(土) 22:47:21.33ID:j8FCEvhl0
どんまい
2023/01/07(土) 22:47:32.24ID:/Ri7nxfpM
解けなかったら糞問
で、おまえのレートは？
2023/01/07(土) 22:49:07.34ID:e3AWo2MYp
Dで素因数分解出来ることが保証されてるのが頭から抜けてたせいで絶対想定解じゃないだろって思いながら無駄にミラーラビン素数判定法とか使ってしまった
2023/01/07(土) 22:51:15.35ID:e3AWo2MYp
素因数分解出来ることっていうより素因数分解の一意性か
2023/01/07(土) 22:52:05.10ID:SPR4wSEy0
問題は全然クソじゃないと思うけど、i=1,2,…,⌊N^(1/3)⌋のうち、N が i で割り切れるような最大の i って書き方が何か変で、i=2,…,⌊N^(1/3)⌋のうちNを割り切る最小のiと言った方が正しいような気がする
2023/01/07(土) 22:54:54.84ID:SPR4wSEy0
G、本質パートからしてボリュームあるのにさらに任意ｍod二項係数使うんかいって思ったけど、想定解は全然使ってなかった
2023/01/07(土) 22:57:18.84ID:SPR4wSEy0
>>105
ちなみに、そのやり方でTLEしないと思うんだけど、N^(1/3)までで探索打ち切った？
113デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:58:15.60ID:LoL6HnAVa
あー、二乗の計算時間もだめだってのか。効率化難しいな。
sqrt使うところに頭が向かわなかったわ。
お前らよく解けるねこれ...
114デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 22:59:01.50ID:LoL6HnAVa
>>105
打ち切った。でもダメだった。
2023/01/07(土) 23:00:27.31ID:j8FCEvhl0
Dは想定回じゃなくても、いろんなテクで解けるし、みんないずれかの解法にサクッとたどり着いてる感じだな
2023/01/07(土) 23:01:13.52ID:SPR4wSEy0
>>113
なんかその書きぶりだと、もしかしてj^2 = N/iになるようなjも探索で出した感じ？
2023/01/07(土) 23:01:47.41ID:e3AWo2MYp
Eが素直なDFSすぎてDと逆でも良いだろとは思った
2023/01/07(土) 23:03:43.12ID:SPR4wSEy0
Eはむしろ個人的には意表を突かれた感じでギョッとした
Fの方が実は素直にロリハやるだけだったりする
119デフォルトの名無しさん (ｱｳｱｳｳｰ Sa85-mbJl)
垢版 |
2023/01/07(土) 23:04:53.24ID:LoL6HnAVa
>112
すまん、冷静に考えたら打ち切ってない
必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。

ただ、自分のやり方だと解を二乗根に絞って計算したせいで最大値がN^(1/2)/2になってしまったんだね。
そのせいか...
120デフォルトの名無しさん (ﾜｯﾁｮｲ 11bd-vxq+)
垢版 |
2023/01/07(土) 23:06:46.63ID:SPR4wSEy0
>>119
>必ず1個の解が見つかるはずで、解が見つかったら打ち切ったら良いんだから、N^(1/3)までカウントアップしないと思ったんだ。だから、N^(1/3)で止めるロジックは無意味だと思ってる。
確かにそれはそう、ナンセンスな質問ですまない
O(N^(1/2))になってたのがTLEの原因っぽいね
2023/01/07(土) 23:08:57.85ID:j8FCEvhl0
EやFはサクッと解けたけど、おれもDはちょっとギョッとしたよ
おれも数学弱だな
てかEなんてほぼナイーブで解けるレベルに感じたし、500点問題としてはあまりにも簡単すぎでは
2023/01/07(土) 23:47:37.23ID:XF8T3NwUM
Ex、Polya の原理や包除原理知ってても簡単に見えないし、ABCで出した理由は有名問題だからなんかな
2023/01/07(土) 23:49:55.07ID:XF8T3NwUM
というか、GみたいのもOEISにあるのな
この問題用に出てきた謎の量にしか見えなかったが
2023/01/08(日) 00:04:08.29ID:lAEXMGQ20
なんちゃらのフルイ使わないでやったらTLEして
脳死で数値設定したら足りなくてWAした雑魚
125デフォルトの名無しさん (ﾜｯﾁｮｲ 5bba-wqvi)
垢版 |
2023/01/08(日) 01:25:51.19ID:4thZdV2f0
ついこないだライブラリ作ったポラード・ローの高速素因数分解でDをしばき倒せたので良かった
2023/01/08(日) 11:32:11.67ID:4xTAT7w0a
Dは簡単すぎて本当にこれでいいのか何度も見直したんだが

まず2から順に素数で割っていって割り切れたものがpかq
さらに同じ数で割って割り切れたらp確定
その場合はp*pで割った商がq

割り切れなかった場合はその素数がqなので割った商の平方根がp
2023/01/08(日) 11:59:00.32ID:VXOhkNVAd
それの計算量解析ができるか？って問題だからな
2023/01/08(日) 12:11:35.54ID:4xTAT7w0a
できるだろ
素数の判定・列挙はO(sqr(N))
2023/01/08(日) 12:14:36.88ID:xVz3ul4wp
そうじゃなくて小さい方がNの平方根で抑えられるかを見抜けるのが本質では
2023/01/08(日) 12:14:57.98ID:xVz3ul4wp
平方根じゃなくて立方根
2023/01/08(日) 12:16:33.74ID:PLtXzXPr0
>>128
N≤9×10¹⁸ なのでそれではだめ
2023/01/08(日) 12:17:04.65ID:4xTAT7w0a
ていうか小さい順に割っていくならpとqの最大値で最も時間がかかるからO(root3(N)*T)
2023/01/08(日) 12:17:37.84ID:4xTAT7w0a
>>131
なんでよ？
2023/01/08(日) 12:22:05.66ID:xVz3ul4wp
>>133
p,qのうちの大きくない方は必ずNの立方根(2×10^6程度)になって、昇順から自然数を見ると割り切れた時点で素因数なのは確定するから素数の判定は実は関係ない(だからp,qが最悪ケースの√N(10^9オーダー)であっても素数判定をする必要はない)っていうのがDのポイントだと思う
2023/01/08(日) 12:23:24.79ID:PLtXzXPr0
>>132
ああ、そこを見積もりできてるならおｋ
2023/01/08(日) 12:24:29.59ID:xVz3ul4wp
>>134
最悪ケースは　p=2,q=10^18程度　だった
2023/01/08(日) 12:33:13.02ID:4xTAT7w0a
>>136
pが2なら最善だろ
真面目に素因数分解するんじゃなくpかqのどちらかになる素因数を一つみつけたら後はO(1)
2023/01/08(日) 12:35:54.01ID:xVz3ul4wp
>>137
もし素数判定をするならこのqがめちゃくちゃ大きい素数のケースが判定出来ない(けど実際は必要ないことを見抜けば良い)って話
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況