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

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん (ﾗｸｯﾍﾟﾍﾟ MM7f-osoq)
垢版 |
2022/10/02(日) 17:43:58.66ID:FqAfPtIrM
↑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/

※前スレ
競技プログラミング総合スレ 63
https://mevius.5ch.net/test/read.cgi/tech/1627477128
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
VIPQ2_EXTDAT: checked:vvvvv:1000:512:: EXT was configured
2022/10/10(月) 22:00:30.58ID:7uvMEE6l0
>>73
強い人見てると解けなくても数か月間寝かせて後から解き直すみたいなのを繰り返しているから、そもそも解ける前に解説を読まない方がベターなのかも？
知識不足で解けない場合はかなりのタイムロスになっちゃうけど、知識面はABCの問題をたくさん解くことで十分身につくと思う
2022/10/10(月) 23:41:25.22ID:JKYZYhBMM
この俺が解説見るなんて的な負けん気がある人じゃないと強くなれない説
2022/10/11(火) 00:12:21.28ID:CzXzMy/W0
地頭がない人は自力で解こうとしても時間をドブに捨てるだけ
2022/10/11(火) 00:12:26.05ID:P0AZplWQ0
ABCの問題だとさっさと見て典型吸収したほうがいい場合のほうが多そう
2022/10/11(火) 00:31:31.56ID:bhgQugsYa
二分探索はめぐる式もいいけど、やっぱり解がありうる範囲の幅に着目するのがいいんじゃないかと思う
これはめぐる式ほど何も考えずできるやり方じゃないけど、少なくともバグらない
幅に着目して、毎回幅が必ず半分以下になるようにすれば、無限ループとかも起こらないし
すべての要素が完全に意識内にあるようにできるから、デバッグも簡単
2022/10/11(火) 10:00:24.46ID:IsJjbRgg0
ARCがレート的に事故になるのって何色コーダーくらいから？
あと、緑（欲言えば水色）はABCのE問題まで完だけでなれるもの？
2022/10/11(火) 10:19:37.71ID:M34VhHTIH
偏見だけどめぐる式使わない人めぐる式書いたことない
2022/10/11(火) 11:59:44.82ID:Icxkwi4V0
片っ端から解説開くタイプだけど暖色にはなれたから、黄色までなら知識偏重でもいいんじゃないかな
赤は知らん
82デフォルトの名無しさん (ﾜｯﾁｮｲ 4a55-Phf8)
垢版 |
2022/10/11(火) 12:11:38.75ID:PLpmTy2t0
米田の『プログラミングコンテストの鉄則』を読んでいますが、コードが分かりやすくて、バグもないですね。
さすがレッドコーダーですね。
2022/10/11(火) 12:15:12.17ID:8WPPu4cTM
米田は説明とかコードを大分使い回ししてるからこなれてきてるイメージあるわ
2022/10/11(火) 12:16:27.59ID:IKEA8vjg0
>>79
EどころかDまで早解き(30-40分)繰り返してたら絶対に入水できるよ
85デフォルトの名無しさん (ﾜｯﾁｮｲ 4a55-Phf8)
垢版 |
2022/10/11(火) 13:34:55.25ID:PLpmTy2t0
正しいアイディアが得られてから、素早く実装するにはどうすればいいのでしょうか？
いつも仮に正しいアイディアが得られたとしても、実装でもたついてしまいます。
86デフォルトの名無しさん (ｱｳｱｳｳｰ Sa2f-Rtu3)
垢版 |
2022/10/11(火) 13:37:37.48ID:ZP0AWOS7a
まず3000acまで精進しましょう
自然と実装が早くなります
87デフォルトの名無しさん (ﾜｯﾁｮｲ 4a55-Phf8)
垢版 |
2022/10/11(火) 13:41:56.59ID:PLpmTy2t0
>>86
ありがとうございます。気が遠くなりますが、3000までいかなくても、次第に速くはなっていくと考えてがんばります。
88デフォルトの名無しさん (ﾜｯﾁｮｲ 83bd-iygP)
垢版 |
2022/10/11(火) 14:51:38.87ID:YbYCnUmy0
>>79
これを見るとE安定（1500pt安定）の人なら水中位は固い
いろいろ噛み合えば青タッチもできるレベルだと思うね
このグラフは他の色についても分析できるから便利
https://twitter.com/kiri8128/status/1561356750355570689
https://twitter.com/kiri8128/status/1576256376518897665
https://twitter.com/kiri8128/status/1566074062786658307
https://twitter.com/5chan_nel (5ch newer account)
89デフォルトの名無しさん (ﾜｯﾁｮｲ ca56-H/N1)
垢版 |
2022/10/11(火) 16:46:50.56ID:1kSE0RtX0
AC数800台で黄コーダーになった中学生
2022/10/11(火) 17:57:52.46ID:Uh95guzZd
実装の速さは紙上デバッグを細部まで終わらせて迷いなく書くことだと思う
2022/10/11(火) 23:17:45.46ID:OYUWyscQa
実装を速くするコツは２つあると考えてる。
１　思考の手間を省く。
　競プロでは毎回全く違うプログラムってことはあんまりなくて、DFSとか1次元DPとか累積和とか毎回書き方が同じ部品というのは結構ある。
　こういう部品に対しては、事前に書き方を決めておくことで、その部分はもう考えずに書けるようになる。
２　隅々まで理解する。
　複雑な問題を解くとき、なんとなくわかった状態で実装を始めている人は多いと思う。気持ちはわかるし、簡単な問題ならそれでいいと思う。
　でも、実装と深い思考は両立するのが難しい。複雑な思考が必要な問題では、先に最後まで（何行目に何を書くかまで）考えておいた方が速い。
2022/10/12(水) 21:59:18.79ID:xx4XrjX60
chokudaiが同じ実力でも1年間で50程度レートが下がるみたいな感じの調査を見たって言ってるけど、ソースは何だろう
個人的には大体そんなもんな気がする
2022/10/13(木) 13:35:28.53ID:XaQsN642a
https://twitter.com/not_522/status/1580130152482099200?t=aj8v0JeHSojee_MKdb-TTw&s=19
https://twitter.com/5chan_nel (5ch newer account)
2022/10/13(木) 16:44:42.51ID:jfaR96gz0
>>93
ありがとう
予想するに、logit([AよりBの方が難しく感じる確率]) = β_0 + β_1 [problems上のdifficultyの差] + β_2 [出題時点の差（単位は年）]としてβ_2/β_1 = 50だった的な感じかな
こういう回帰係数って素朴に割り算していいのかわからないけど
[problems上のdifficultyの差]と[出題時点の差]って独立っぽいから多重共線性とかはなさそう
95デフォルトの名無しさん (ﾜｯﾁｮｲ 4a55-rqSc)
垢版 |
2022/10/13(木) 17:29:37.68ID:S5qtayIE0
>>90-91
ついつい、あせってアイディアが整理されていなくても書き始めてしまうんですよね。。。

『離散凸解析と最適化アルゴリズム』という本の第1章を読んだのですが、このような
理論的な本は競技プログラミングに役に立つことがありますか？

問題を解くばかりでは飛躍的な上達はなかなか難しいのではないかという気もします。
96デフォルトの名無しさん (ﾜｯﾁｮｲ 86e2-iGwm)
垢版 |
2022/10/13(木) 17:54:44.70ID:GP86fHNY0
>>95
atcoderは大人のsapixなので役に立たないです
2022/10/13(木) 18:58:22.49ID:H7IUAqHb0
理論的な本は競技プログラミングに役に立つことがあります
2022/10/13(木) 20:38:36.86ID:mU98+Q0JM
>>95
mas 氏が離散凸を題材に作問されていたね。arc130_f。
2022/10/13(木) 21:10:49.03ID:UluXeA7t0
凡人は数学の難しい話が役に立つところまでレートを伸ばせない
100デフォルトの名無しさん (ﾜｯﾁｮｲ 86e2-iGwm)
垢版 |
2022/10/13(木) 21:28:38.71ID:GP86fHNY0
ABCで黄色以上でた問題は存在しないも同然じゃからのぉ
実務的には調べながら1問に3時間くらいかけて解ければ十分みたいな感じかと
2022/10/13(木) 21:29:29.75ID:jfaR96gz0
その離散凸解析の本は理論系の中でもかなり競プロに役立つ方の本な気がする
けど、知識をつけて飛躍的に伸びるのはAtCoderの中でもABCで、そのABCで出てくるぐらいの知識なら特別な勉強をしなくても、問題解いて蟻本あたり読んでいれば身につくものという印象（Exは除く）
だから理論系の勉強がコスパがよいかというと微妙
ただ、競プロ抜きにしてもアルゴリズムの勉強は面白い部分があると思うし、そもそも競プロとは独立して価値があるものなので勉強して損はないんじゃないかなと思う
2022/10/13(木) 22:15:44.40ID:H7IUAqHb0
要約すると、理論的な本は競技プログラミングに役に立つことがあります
2022/10/13(木) 22:31:16.40ID:H7IUAqHb0
というのはまあ冗談で、少なくともレート2000以下とかならそんなのいらん
鉄則本や蟻本に習熟して、AtCoderを練習しまくて遭遇した知らなかったアルゴリズムを覚えればいいだけ
ヘタに大学生向けの参考書なんか読むより大学受験レベルの整数問題を解く練習したほうがいいくらい
2022/10/14(金) 01:47:17.08ID:Ws94+F1up
こどふぉのdiv4難易度の上限がatcoderの500点問題くらいだから初心者にとっては早解きの練習になってありがたい
2022/10/14(金) 21:00:56.55ID:sN1rZFZxa
理論は楽しいから、競プロを手段化することで競プロへのモチベになる
2022/10/15(土) 19:47:28.91ID:XR8bXiW50
今日も頑張るぞ
今日、ちゃんとCまでは解ければ茶色にはなれる
2022/10/15(土) 20:38:54.13ID:Hf8AKj6X0
誤差の問題が出るから整数型でなんとかしよう
108デフォルトの名無しさん (ﾜｯﾁｮｲ efe2-TyQf)
垢版 |
2022/10/15(土) 22:43:48.07ID:ipApAIVt0
こういう重いのやるなら1問だけやれよ、ビギナーで1問70行とか無いわ
2022/10/15(土) 22:46:38.09ID:dFjmbf/S0
AtCoder を始めて10回ぐらい経ちましたが, A問題しか解けない状態が続いてます.
A：簡単
B：いくつかWA→解決できずに終了
といった感じです.
原因はコードを見てWAになる理由（そうなるケース）を見つけられないことだと思うのですが,
みなさんどのように対処されているのでしょうか
2022/10/15(土) 22:52:32.49ID:fGPCLDVo0
Aしか解けない人の気持ちはわからん
なんか計算量とか前提知識が足りてなさすぎる気がするから、AtCodeer本とか読んでみたら？
競プロは問題に書かれたことをシミュレーションするコードを書くコンテストじゃなくて、たくさんのアルゴリズム知識を駆使したうえでの数学のコンテストだよ
2022/10/15(土) 22:57:00.60ID:fGPCLDVo0
唯一、A問題だけはシミュレーションすれば解けるから、競プロ用の知識が足りてないのかなと思った
2022/10/15(土) 23:12:41.37ID:+G+SyjUt0
B問題に関しては計算量解析もそんなに問われないから、計算量の知識というよりはプログラミングコードを書くところとか、問題文の状況を考える基礎力とかかなあ
あんまいいアドバイスできないけど練習あるのみだよ、ABC-Bをたくさんやるのがいいと思う
競プロはよく役に立たないと言われているけど、ABCのC問題までは本当にプログラミングの基礎力と関わってそうだから、できないのなら練習して損はないと思うよ
2022/10/15(土) 23:14:09.46ID:EzFe164Rp
永続データ構造ってどの色くらいから常識になる？というかどこからそういう知識を身につけてるんだ
あの問題文を読んで木構造を作るぞって気持ちに初見でなれるものなのかな
2022/10/15(土) 23:15:16.34ID:+G+SyjUt0
まあ今日のBはそこそこ解きにくい方だったと思う
2022/10/15(土) 23:15:18.35ID:fGPCLDVo0
おれも永続データ構造は全然知らんけど、木でいけそうだなということにはすぐ気づけたよ
2022/10/15(土) 23:18:30.16ID:EzFe164Rp
Dまでは早解き安定して出来るけどEから不安定になるから水色以上埋めていくしかないか
117デフォルトの名無しさん (ﾜｯﾁｮｲ 2bbd-spri)
垢版 |
2022/10/15(土) 23:18:43.87ID:+G+SyjUt0
>>113
ネットで競プロっぽいこと検索してたら結構出てくる
はまやんさんのブログとかにまとまってるやつオススメ
あれは別に木構造作ろうというよりは、

ページにAのデータ全部コピーするとオーバーヘッドやばい
↓
ポインタアクセスで処理したい
↓
どうせ末尾しか毎回アクセスしないし、linked listっぽくすればよさそう
↓
というか、データ自体は時系列テーブル上に保存しとけばよくないか？

みたいな感じで思いつくのが自然な気がする
2022/10/15(土) 23:20:23.90ID:P4PRQhICa
テストケースの公開って普段はコンテスト後何日ぐらいで行われるんですか？
2022/10/15(土) 23:23:11.47ID:EzFe164Rp
>>117
思考過程が分かりやすくて助かるわ　ありがとう
2022/10/15(土) 23:24:39.60ID:+G+SyjUt0
>>118
そんなにすぐじゃないイメージ、今のところ2〜3週間遅れぐらい？
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
そもそも作業者のAtCoder運営自体がテストケースを直接見てデバッグってスタイルをそんなに好きじゃなさそうだから作業モチベも低そう
ここに貼ってくれれば誰かしらが見て指摘したりはできると思うけど
2022/10/15(土) 23:38:17.61ID:TnqVSCZIM
Ex、問題文がもろにStern Brocot木で笑ったな
Exをガチ目に解きに来る人はみんな知ってるだろ
2022/10/15(土) 23:47:59.64ID:TnqVSCZIM
Stern Brocot木の必要部分だけを取ってきた木の辺の数がf(T)か？
知識一発芸ならもっとたくさんの人が解いてるだろうし、ここからもいろいろ考えなきゃダメそうだな
2022/10/15(土) 23:49:13.54ID:TnqVSCZIM
辺というか頂点か
124デフォルトの名無しさん (ｱｳｱｳｳｰ Sacf-Txcf)
垢版 |
2022/10/15(土) 23:59:48.98ID:FT6wiWdXa
A問題で初歩的なループや再帰を解禁したの
整数パズルみたいなのよりええな
2022/10/16(日) 00:19:15.15ID:zH+PZ1kvM
競プロっぽい問題得意じゃない人からしたら整数パズルより愚直ループのが解きやすいし、整数パズルできるやつからしたらその辺の文法覚えるのは簡単だろうしで、最近のAの難易度からするとループ縛りは実情にあってなかった
126デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/16(日) 07:01:44.35ID:ayOmFxSE0
『競技プログラミングの鉄則』という本の問題A19のナップザック問題について質問です。
アマゾンのレビューでも指摘がありますが、dp[i][j]に品物1からiまでの中から合計重量が
ぴったりjになるという条件を満たすナップザックへの入れ方のうち合計価値が最大になる
ときの合計価値を入れています。

普通に考えると、dp[i][j]には部分問題の答えを入れると思います。
つまり、品物1からiの中から合計重量がj以下になるという条件を満たすナップザックへの
入れ方のうち合計価値が最大になるときの合計価値を入れるのが普通だと思います。

これはなぜですか？
2022/10/16(日) 11:47:32.10ID:zH+PZ1kvM
・計算量的にも実装の複雑さもほとんど変わらない(最後に全体maxをとるかどうかは微々たる差)
・重量合計がちょうどwになるときの最大価値の方が、重量合計がw以下になるときの最大価値よりも得られる情報が多い
・形式的冪級数で定式化したとき少しだけきれい

鉄則本持っとらんけど、このあたりの理由か？
二番目が多分重要で、競プロではちょうどwで書く人の方が多い気がするぞ
2022/10/16(日) 14:38:27.53ID:ixOB/E6y0
昨日初めてコンテストに挑戦しましたが、2問しか正解できませんでした
C++だけじゃなく、もう1個文字列操作用の言語を使った方が良いような気がしました
Perlが理想なのですが、VSCODEでのデバッグ環境の構築方法がわかりません
129デフォルトの名無しさん (ｱｳｱｳｳｰ Sacf-Txcf)
垢版 |
2022/10/16(日) 14:58:25.40ID:WDOvRoY2a
Perlは遅すぎてc問題でも解けない可能性あるからやめた方がいい
スクリプト言語ならPythonが無難
130デフォルトの名無しさん (ﾜｯﾁｮｲ 8b01-+w9B)
垢版 |
2022/10/16(日) 15:13:58.77ID:yPZsgFrS0
Rust使えば？
2022/10/16(日) 15:39:30.37ID:+XvlfMW9p
他の言語覚えるより、C++でどうやるか、だけを準備したほうが確実に良いよ
2022/10/16(日) 17:18:45.75ID:hu3fQSZo0
std::stringの機能で競プロのニーズ的には十分な気がするけど
133デフォルトの名無しさん (ﾜｯﾁｮｲ 8b01-+w9B)
垢版 |
2022/10/16(日) 18:24:36.77ID:jxKItKj70
プロは道具にこだわる。
2022/10/16(日) 19:26:57.71ID:ixOB/E6y0
perlってpythonより遅いんですね
とりあえずC++でコンテストに慣れて、それからpythonも使おうと思います
2022/10/16(日) 20:54:02.10ID:hu3fQSZo0
ARC
2022/10/16(日) 22:07:03.07ID:2u3vkIPv0
A問題とけたぞおお
2022/10/16(日) 23:14:41.13ID:gtISzeY80
C問題、方針は良かったのにgrundy数の計算を永遠にバグらせてて死んだ
2022/10/16(日) 23:36:23.97ID:hu3fQSZo0
普段と比べると難しい印象はないけど、ARCらしく素直に解けない問題が多かった気がする
139デフォルトの名無しさん (ﾜｯﾁｮｲ dfbd-EMpt)
垢版 |
2022/10/17(月) 10:18:40.91ID:4D5lyUw10
https://i.imgur.com/Q53m3ww.jpg
無事茶色達成
しかし将棋ウォーズで言えば1級レベルなのか
もっと頑張ります
2022/10/17(月) 12:15:14.38ID:5a5BYNfKM
コドフォdiv. 1も不足してるしAGCも不足してるな
div. 2とかABCレベルが枯渇することはないだろうが、今後高レベル帯では問題を作りやすい実装ゲー、高度知識ゲーが増えていくんだろうか
あるいは新しい分野が開拓されるか
2022/10/17(月) 12:15:58.61ID:5a5BYNfKM
>>139
おめ
2022/10/17(月) 12:37:31.22ID:n8OzEy840
>>141
2022/10/17(月) 12:37:50.91ID:n8OzEy840
途中送信してしもうた
さんくすうう
2022/10/18(火) 19:26:06.06ID:KPHiYJNj0
デジタル庁が開発エンジニアを募集　任期1年の非常勤　
https://hayabusa9.5ch.net/test/read.cgi/news/1666079673/
年収最大1千数百万円　賞与なし

必須スキル
・Webアプリケーション開発経験５年以上
・TypeScript、React、Vue、GitHub等を用いた開発経験２年以上
・DevOpsの設計・開発、アジャイル開発経験２年以上
・C#によるWebバックエンドアプリケーション（MVC、Web API、Entity Framework）開発経験３年以上
・パブリッククラウドサービス（Azure、AWS、GCPなど）でホストするシステムの開発経験２年以上

・データベース設計経験２年以上
・Web・モバイル技術、及び大規模サービスの運用に対する確かな理解と技術を深く掘り下げる能力
・現在においても、開発・実装業務に直接携わっていること。
・複雑で不慣れな実装、及び開発言語にも素早く適応できる柔軟性
・英語で書かれた技術文書を理解できる語学力
145デフォルトの名無しさん (ﾜｯﾁｮｲ 9f10-Vt39)
垢版 |
2022/10/18(火) 19:50:00.45ID:XVoXwl440
場合の数を998244353で割った余りを求める能力だけで雇って欲しい
2022/10/18(火) 22:59:15.61ID:B5JNCuxS0
省庁の予算とかも32ビットで収まらないから998244353の余りを使うようにしよう
商が違っても余りが一致してればまあ合ってるやろ
2022/10/19(水) 06:50:43.51ID:QJq8aW4Z0
998244353だけだと不安だから1000000007で割った余りも保持しとこう
148デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/19(水) 08:54:58.33ID:T4QuduyG0
エドモンズの花アルゴリズムを使わないと解けない問題はありますか？
2022/10/19(水) 14:46:26.69ID:zvz72aPAa
あるが一般的なコンテストじゃまず出ない
150デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/19(水) 14:50:58.95ID:T4QuduyG0
>>149
ありがとうございました。
2022/10/19(水) 17:30:20.54ID:UoSqWJe30
ICPC は一般的ではなかった？
2022/10/19(水) 18:07:42.87ID:B4JLsZ8Hp
スニペットって登録すべき？　今まではライブラリからコピペしてたんだけど
2022/10/19(水) 18:21:55.17ID:Lddii/xFa
そんなんなんでもよくね
小手先の効率化よりも、考察力を鍛えよう
2022/10/19(水) 18:44:37.47ID:pbOv57aYM
するだけなら別に手間じゃないしやっとけばいいと思うぞ
決定的に強くなるわけじゃないけどそれで拾えるレートもあるだろう
155デフォルトの名無しさん (ﾜｯﾁｮｲ fbbd-EMpt)
垢版 |
2022/10/20(木) 03:26:34.39ID:7dYF2Oin0
離散フーリエ変換を知った時は感動した
競プロ界隈じゃ常識かもしれないけど
2022/10/20(木) 06:38:24.64ID:h2hzFpVPM
>>152
Unionfind入れとくとかなり便利よ
2022/10/20(木) 11:12:32.08ID:zuiO6CV10
FFTは今でこそ半ば常識だけど、蟻本が本の中で扱わないぐらいのトピックだった
形式的べき級数の流行やACLで普及したのかな？
フーリエ変換なんて周波数成分とってきたり微分方程式解いたりするときに使うものという印象だったから、計算量削減に活用できるのにはびっくり
158デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/20(木) 14:07:16.92ID:mYhqP5aW0
形式的べき級数が流行しているというのは本当ですか？
どうしてですか？
母関数とかと関係がありますか？
159デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/20(木) 14:15:25.40ID:mYhqP5aW0
FFTについてはCLRSの第3版に分かりやすく書いてあって、読んだのですが、すごいなと思いました。
フーリエ変換とか難しい解析学の話を全く知らなくても大丈夫ですよね。
2022/10/20(木) 17:38:04.69ID:EI9V1HUe0
Nyaan回のABCが形式的冪級数講座と言われる位には出題されてるだろ
立式も高速化も機械的にできて考察部分を減らせるならそりゃ使うわな
2022/10/20(木) 17:54:47.90ID:vkRYV1070
形式的べき級数がABCで想定解法の1番目にくるようなことはないと思うし、便利だということに気づけない人も多そう
162デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/20(木) 17:57:29.17ID:mYhqP5aW0
Nyaan回って何ですか？
163デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/20(木) 19:01:43.10ID:mYhqP5aW0
形式的べき級数は、Liuの『組合せ数学入門I』とかKnuthの『Concrete Mathematics』に
書いてありますね。

競技プログラミングにどのように役立つのか分かりませんが。
2022/10/20(木) 19:34:32.29ID:zuiO6CV10
Nyaan回というのはNyaanさんという人がwriterをやっているコンテストのこと
特にABCでは、Exに形式的べき級数の発展的な技法（ラグランジュの反転公式の利用とか）が解法に来ることがあり、解説も丁寧に書かれていてかなり勉強になる
165デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/20(木) 19:43:13.83ID:mYhqP5aW0
>>164
ありがとうございました。
2022/10/20(木) 19:48:25.32ID:zuiO6CV10
形式的べき級数の利用法として典型的なのは、数え上げのDP遷移を畳み込みとみなして高速化することかな
FFT使ってO(N^2)をO(NlogN)にする
maspyさんのブログの「数え上げとの対応付け」の記事とかが分かりやすい
同じ形の遷移をＱ回するときとかは、周波数領域表現の方で各点を累乗すればいいとか、DP遷移の「逆変換」を考えたいときがあって、それは逆関数に対応するから機械的な代数学的操作で導出できるようになったり、恩恵はいろいろ
2022/10/20(木) 19:56:58.93ID:zuiO6CV10
解析学の知識がなきゃ理解できないという部分はなさそう
形式的べき級数の微分とかオイラーの等式とか、基礎的な知識は要求されるけど、高校数学ちゃんとやってきた人なら適宜ググればどうにかなるレベル
168デフォルトの名無しさん (ﾜｯﾁｮｲ 9f55-ZPbQ)
垢版 |
2022/10/20(木) 20:35:33.61ID:mYhqP5aW0
形式的べき級数を使って解く問題ですが、なんかアルゴリズムの問題としては特殊すぎませんか？

例えば、プログラミングコンテストに、整数論的なアルゴリズムを使って解くような問題が出たとしたら、
場違いな感じがしますが、それと同じような感じがします。
2022/10/20(木) 21:33:57.26ID:zuiO6CV10
情報科学の基礎や離散数学的なアルゴリズムが守備範囲のコンテストだから特殊とは思わないかな
学究的な観点ではそれらも十分アルゴリズムのメジャー領域かと
2022/10/21(金) 08:24:36.19ID:DpTirTZh0
競技プログラミングという名前に引っ張られすぎ
整数論とかも全然メインストリートやで
171デフォルトの名無しさん (ﾃﾃﾝﾃﾝﾃﾝ MM7f-GGBy)
垢版 |
2022/10/21(金) 09:58:25.01ID:6qeEzBTbM
mod 素数数え上げのときモジュラ逆数を O(logP) で求めるのは整数論的アルゴリズム？だけどそれも場違いだと思ってる？
2022/10/21(金) 11:01:06.99ID:enxIjOIS0
競プロ全体でもそこそこ整数論を使うけど、AtCoderだと特に出題傾向が高いよな
実装が重い有名アルゴリズムは出さないって公式で宣言してるから、結果的に考察偏重にしようと数学ばっかりになってる
2022/10/21(金) 13:46:22.49ID:Pi8u3vHmM
趣味が合わないならコドフォに移るのもあり
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。