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

2022/10/02(日) 17:43:58.66

↑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/13(木) 21:29:29.75

その離散凸解析の本は理論系の中でもかなり競プロに役立つ方の本な気がする
けど、知識をつけて飛躍的に伸びるのはAtCoderの中でもABCで、そのABCで出てくるぐらいの知識なら特別な勉強をしなくても、問題解いて蟻本あたり読んでいれば身につくものという印象（Exは除く）
だから理論系の勉強がコスパがよいかというと微妙
ただ、競プロ抜きにしてもアルゴリズムの勉強は面白い部分があると思うし、そもそも競プロとは独立して価値があるものなので勉強して損はないんじゃないかなと思う

2022/10/13(木) 22:15:44.40

要約すると、理論的な本は競技プログラミングに役に立つことがあります

2022/10/13(木) 22:31:16.40

というのはまあ冗談で、少なくともレート2000以下とかならそんなのいらん
鉄則本や蟻本に習熟して、AtCoderを練習しまくて遭遇した知らなかったアルゴリズムを覚えればいいだけ
ヘタに大学生向けの参考書なんか読むより大学受験レベルの整数問題を解く練習したほうがいいくらい

2022/10/14(金) 01:47:17.08

こどふぉのdiv4難易度の上限がatcoderの500点問題くらいだから初心者にとっては早解きの練習になってありがたい

2022/10/14(金) 21:00:56.55

理論は楽しいから、競プロを手段化することで競プロへのモチベになる

2022/10/15(土) 19:47:28.91

今日も頑張るぞ
今日、ちゃんとCまでは解ければ茶色にはなれる

2022/10/15(土) 20:38:54.13

誤差の問題が出るから整数型でなんとかしよう

2022/10/15(土) 22:43:48.07

こういう重いのやるなら1問だけやれよ、ビギナーで1問70行とか無いわ

2022/10/15(土) 22:46:38.09

AtCoder を始めて10回ぐらい経ちましたが, A問題しか解けない状態が続いてます.
A：簡単
B：いくつかWA→解決できずに終了
といった感じです.
原因はコードを見てWAになる理由（そうなるケース）を見つけられないことだと思うのですが,
みなさんどのように対処されているのでしょうか

2022/10/15(土) 22:52:32.49

Aしか解けない人の気持ちはわからん
なんか計算量とか前提知識が足りてなさすぎる気がするから、AtCodeer本とか読んでみたら？
競プロは問題に書かれたことをシミュレーションするコードを書くコンテストじゃなくて、たくさんのアルゴリズム知識を駆使したうえでの数学のコンテストだよ

2022/10/15(土) 22:57:00.60

唯一、A問題だけはシミュレーションすれば解けるから、競プロ用の知識が足りてないのかなと思った

2022/10/15(土) 23:12:41.37

B問題に関しては計算量解析もそんなに問われないから、計算量の知識というよりはプログラミングコードを書くところとか、問題文の状況を考える基礎力とかかなあ
あんまいいアドバイスできないけど練習あるのみだよ、ABC-Bをたくさんやるのがいいと思う
競プロはよく役に立たないと言われているけど、ABCのC問題までは本当にプログラミングの基礎力と関わってそうだから、できないのなら練習して損はないと思うよ

2022/10/15(土) 23:14:09.46

永続データ構造ってどの色くらいから常識になる？というかどこからそういう知識を身につけてるんだ
あの問題文を読んで木構造を作るぞって気持ちに初見でなれるものなのかな

2022/10/15(土) 23:15:16.34

まあ今日のBはそこそこ解きにくい方だったと思う

2022/10/15(土) 23:15:18.35

おれも永続データ構造は全然知らんけど、木でいけそうだなということにはすぐ気づけたよ

2022/10/15(土) 23:18:30.16

Dまでは早解き安定して出来るけどEから不安定になるから水色以上埋めていくしかないか

2022/10/15(土) 23:18:43.87

>>113
ネットで競プロっぽいこと検索してたら結構出てくる
はまやんさんのブログとかにまとまってるやつオススメ
あれは別に木構造作ろうというよりは、

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

みたいな感じで思いつくのが自然な気がする

2022/10/15(土) 23:20:23.90

テストケースの公開って普段はコンテスト後何日ぐらいで行われるんですか？

2022/10/15(土) 23:23:11.47

>>117
思考過程が分かりやすくて助かるわ　ありがとう

2022/10/15(土) 23:24:39.60

>>118
そんなにすぐじゃないイメージ、今のところ2～3週間遅れぐらい？
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=0
そもそも作業者のAtCoder運営自体がテストケースを直接見てデバッグってスタイルをそんなに好きじゃなさそうだから作業モチベも低そう
ここに貼ってくれれば誰かしらが見て指摘したりはできると思うけど

2022/10/15(土) 23:38:17.61

Ex、問題文がもろにStern Brocot木で笑ったな
Exをガチ目に解きに来る人はみんな知ってるだろ

2022/10/15(土) 23:47:59.64

Stern Brocot木の必要部分だけを取ってきた木の辺の数がf(T)か？
知識一発芸ならもっとたくさんの人が解いてるだろうし、ここからもいろいろ考えなきゃダメそうだな

2022/10/15(土) 23:49:13.54

辺というか頂点か

2022/10/15(土) 23:59:48.98

A問題で初歩的なループや再帰を解禁したの
整数パズルみたいなのよりええな

2022/10/16(日) 00:19:15.15

競プロっぽい問題得意じゃない人からしたら整数パズルより愚直ループのが解きやすいし、整数パズルできるやつからしたらその辺の文法覚えるのは簡単だろうしで、最近のAの難易度からするとループ縛りは実情にあってなかった

2022/10/16(日) 07:01:44.35

『競技プログラミングの鉄則』という本の問題A19のナップザック問題について質問です。
アマゾンのレビューでも指摘がありますが、dp[i][j]に品物1からiまでの中から合計重量が
ぴったりjになるという条件を満たすナップザックへの入れ方のうち合計価値が最大になる
ときの合計価値を入れています。

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

これはなぜですか？

2022/10/16(日) 11:47:32.10

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

鉄則本持っとらんけど、このあたりの理由か？
二番目が多分重要で、競プロではちょうどwで書く人の方が多い気がするぞ

2022/10/16(日) 14:38:27.53

昨日初めてコンテストに挑戦しましたが、2問しか正解できませんでした
C++だけじゃなく、もう1個文字列操作用の言語を使った方が良いような気がしました
Perlが理想なのですが、VSCODEでのデバッグ環境の構築方法がわかりません

2022/10/16(日) 14:58:25.40

Perlは遅すぎてc問題でも解けない可能性あるからやめた方がいい
スクリプト言語ならPythonが無難

2022/10/16(日) 15:13:58.77

Rust使えば？

2022/10/16(日) 15:39:30.37

他の言語覚えるより、C++でどうやるか、だけを準備したほうが確実に良いよ

2022/10/16(日) 17:18:45.75

std::stringの機能で競プロのニーズ的には十分な気がするけど

2022/10/16(日) 18:24:36.77

プロは道具にこだわる。

2022/10/16(日) 19:26:57.71

perlってpythonより遅いんですね
とりあえずC++でコンテストに慣れて、それからpythonも使おうと思います

2022/10/16(日) 20:54:02.10

ARC

2022/10/16(日) 22:07:03.07

A問題とけたぞおお

2022/10/16(日) 23:14:41.13

C問題、方針は良かったのにgrundy数の計算を永遠にバグらせてて死んだ

2022/10/16(日) 23:36:23.97

普段と比べると難しい印象はないけど、ARCらしく素直に解けない問題が多かった気がする

2022/10/17(月) 10:18:40.91

https://i.imgur.com/Q53m3ww.jpg
無事茶色達成
しかし将棋ウォーズで言えば1級レベルなのか
もっと頑張ります

2022/10/17(月) 12:15:14.38

コドフォdiv. 1も不足してるしAGCも不足してるな
div. 2とかABCレベルが枯渇することはないだろうが、今後高レベル帯では問題を作りやすい実装ゲー、高度知識ゲーが増えていくんだろうか
あるいは新しい分野が開拓されるか

2022/10/17(月) 12:15:58.61

>>139
おめ

2022/10/17(月) 12:37:31.22

>>141

2022/10/17(月) 12:37:50.91

途中送信してしもうた
さんくすうう

2022/10/18(火) 19:26:06.06

デジタル庁が開発エンジニアを募集　任期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・モバイル技術、及び大規模サービスの運用に対する確かな理解と技術を深く掘り下げる能力
・現在においても、開発・実装業務に直接携わっていること。
・複雑で不慣れな実装、及び開発言語にも素早く適応できる柔軟性
・英語で書かれた技術文書を理解できる語学力

2022/10/18(火) 19:50:00.45

場合の数を998244353で割った余りを求める能力だけで雇って欲しい

2022/10/18(火) 22:59:15.61

省庁の予算とかも32ビットで収まらないから998244353の余りを使うようにしよう
商が違っても余りが一致してればまあ合ってるやろ

2022/10/19(水) 06:50:43.51

998244353だけだと不安だから1000000007で割った余りも保持しとこう

2022/10/19(水) 08:54:58.33

エドモンズの花アルゴリズムを使わないと解けない問題はありますか？

2022/10/19(水) 14:46:26.69

あるが一般的なコンテストじゃまず出ない

2022/10/19(水) 14:50:58.95

>>149
ありがとうございました。

2022/10/19(水) 17:30:20.54

ICPC は一般的ではなかった？

2022/10/19(水) 18:07:42.87

スニペットって登録すべき？　今まではライブラリからコピペしてたんだけど

2022/10/19(水) 18:21:55.17

そんなんなんでもよくね
小手先の効率化よりも、考察力を鍛えよう

2022/10/19(水) 18:44:37.47

するだけなら別に手間じゃないしやっとけばいいと思うぞ
決定的に強くなるわけじゃないけどそれで拾えるレートもあるだろう

2022/10/20(木) 03:26:34.39

離散フーリエ変換を知った時は感動した
競プロ界隈じゃ常識かもしれないけど

2022/10/20(木) 06:38:24.64

>>152
Unionfind入れとくとかなり便利よ

2022/10/20(木) 11:12:32.08

FFTは今でこそ半ば常識だけど、蟻本が本の中で扱わないぐらいのトピックだった
形式的べき級数の流行やACLで普及したのかな？
フーリエ変換なんて周波数成分とってきたり微分方程式解いたりするときに使うものという印象だったから、計算量削減に活用できるのにはびっくり

2022/10/20(木) 14:07:16.92

形式的べき級数が流行しているというのは本当ですか？
どうしてですか？
母関数とかと関係がありますか？

2022/10/20(木) 14:15:25.40

FFTについてはCLRSの第3版に分かりやすく書いてあって、読んだのですが、すごいなと思いました。
フーリエ変換とか難しい解析学の話を全く知らなくても大丈夫ですよね。

2022/10/20(木) 17:38:04.69

Nyaan回のABCが形式的冪級数講座と言われる位には出題されてるだろ
立式も高速化も機械的にできて考察部分を減らせるならそりゃ使うわな

2022/10/20(木) 17:54:47.90

形式的べき級数がABCで想定解法の1番目にくるようなことはないと思うし、便利だということに気づけない人も多そう

2022/10/20(木) 17:57:29.17

Nyaan回って何ですか？

2022/10/20(木) 19:01:43.10

形式的べき級数は、Liuの『組合せ数学入門I』とかKnuthの『Concrete Mathematics』に
書いてありますね。

競技プログラミングにどのように役立つのか分かりませんが。

2022/10/20(木) 19:34:32.29

Nyaan回というのはNyaanさんという人がwriterをやっているコンテストのこと
特にABCでは、Exに形式的べき級数の発展的な技法（ラグランジュの反転公式の利用とか）が解法に来ることがあり、解説も丁寧に書かれていてかなり勉強になる

2022/10/20(木) 19:43:13.83

>>164
ありがとうございました。

2022/10/20(木) 19:48:25.32

形式的べき級数の利用法として典型的なのは、数え上げのDP遷移を畳み込みとみなして高速化することかな
FFT使ってO(N^2)をO(NlogN)にする
maspyさんのブログの「数え上げとの対応付け」の記事とかが分かりやすい
同じ形の遷移をＱ回するときとかは、周波数領域表現の方で各点を累乗すればいいとか、DP遷移の「逆変換」を考えたいときがあって、それは逆関数に対応するから機械的な代数学的操作で導出できるようになったり、恩恵はいろいろ

2022/10/20(木) 19:56:58.93

解析学の知識がなきゃ理解できないという部分はなさそう
形式的べき級数の微分とかオイラーの等式とか、基礎的な知識は要求されるけど、高校数学ちゃんとやってきた人なら適宜ググればどうにかなるレベル

2022/10/20(木) 20:35:33.61

形式的べき級数を使って解く問題ですが、なんかアルゴリズムの問題としては特殊すぎませんか？

例えば、プログラミングコンテストに、整数論的なアルゴリズムを使って解くような問題が出たとしたら、
場違いな感じがしますが、それと同じような感じがします。

2022/10/20(木) 21:33:57.26

情報科学の基礎や離散数学的なアルゴリズムが守備範囲のコンテストだから特殊とは思わないかな
学究的な観点ではそれらも十分アルゴリズムのメジャー領域かと

2022/10/21(金) 08:24:36.19

競技プログラミングという名前に引っ張られすぎ
整数論とかも全然メインストリートやで

2022/10/21(金) 09:58:25.01

mod 素数数え上げのときモジュラ逆数を O(logP) で求めるのは整数論的アルゴリズム？だけどそれも場違いだと思ってる？

2022/10/21(金) 11:01:06.99

競プロ全体でもそこそこ整数論を使うけど、AtCoderだと特に出題傾向が高いよな
実装が重い有名アルゴリズムは出さないって公式で宣言してるから、結果的に考察偏重にしようと数学ばっかりになってる

2022/10/21(金) 13:46:22.49

趣味が合わないならコドフォに移るのもあり

2022/10/22(土) 00:53:27.78

学生時代はこんなもんいつ使うんだよｗ
と思ってたのに、仕事でFFT実装する羽目になった
使い道は確かに素晴らしいものの

2022/10/22(土) 01:21:13.01

FFTってライブラリに突っ込むだけじゃないの・・・・

2022/10/22(土) 13:04:38.07

可変長のビット列を扱うにはどうすればいいのでしょうか？

2022/10/22(土) 13:37:36.07

キーエンス産の問題難しいイメージあるから不安

2022/10/22(土) 13:48:45.77

>>176
vector<bool>を使いたいという話？

2022/10/22(土) 13:59:43.71

問題提供キーエンスなのか
社内にこういうのができる人員を抱えてるのはええな

2022/10/22(土) 16:48:43.35

>>178
それだと出力がtrue/falseになってしまうので、01で扱えると嬉しいです

2022/10/22(土) 17:29:32.23

>>180
vectorのboolだけ特殊化されてるのよ

2022/10/22(土) 18:12:42.91

確かキーエンスは、不可能な問題を解決する会社だから、
バリバリ理系のイメージある

Google の面接の難問、
無限格子の桂馬の位置の電気抵抗を求めよとか

2022/10/22(土) 18:22:25.60

キーエンスは営業が強くて徹底的に収益をプランニングするB2Bボッタクリ企業のイメージが・・・

2022/10/22(土) 18:28:53.32

一部の問題提供ってどうせ前半だからあんま関係ないな
前は典型をそのまま出してて噴飯ものだったわ

2022/10/22(土) 20:09:16.07

競プロってなんか意味あるの？
よく知らんけど実務とも学問とも違うだろあれ

2022/10/22(土) 20:45:00.56

パズルゲームだね
こういうパズルゲームを好きな人が競プロをきっかけに興味関心の幅を広げて情報科学の勉強につながることもあるから、役に立たないとは思わないけど、別に好きじゃないんならやらなくてもいいと思う

2022/10/22(土) 20:50:00.17

意味あるからGoogleなんて20年近くも前からコンテストやり続けてるじゃん

2022/10/22(土) 22:40:12.40

Dですが、部分和問題だと気づいたのですが、実装まで行きませんでした。

2022/10/22(土) 23:06:40.62

F、G辺りに置かれてても問題文の主旨自体は簡潔なことって結構あるんだね
普段Eくらいまでしか解けないからそこら辺の問題は歯が立たないのかなって思い込んでスルーしがちだったけど軽いアプローチくらいなら思いつくしもう少し上のレベルの問題も取り組んでいくべきか

2022/10/22(土) 23:12:40.39

ABCだったらExですら知識一発芸が結構出るから、後ろの問題だから考察難しいって感じでもないよ

2022/10/22(土) 23:24:01.65

なるほど
ABCとARCAGCで傾向結構違うのは感じてたけどABC産なら典型寄りだろうし解説見るハードル下げても良さそうな感じか

2022/10/22(土) 23:26:14.59

Fとか脳死で最適化ライブラリにぶっこんで解けるような問題出してほしい

**デフォルトの名無しさん** (ｽﾌｯ Sda2-JIE3) · 2022/10/22(土) 23:28:05.75

D解かれすぎな気が
部分和とはいえ実装バグりやすいでしょこれ

2022/10/22(土) 23:30:21.82

ナップサックDPはABC中盤に出すぎてちょっとした変形入れてもみんな対応してくるな

2022/10/22(土) 23:35:42.74

>>191
ABCは1問30分ぐらい考えて考察生えなきゃもう解説見ていいレベルだと思うわ
ABCクラスの問題ならAtCoderでもCodeForcesでも無限にコンテストで新問が提供されるし、考える練習はコンテストでやればいい

2022/10/22(土) 23:53:18.15

D問題とけんかった・・・
XとYの行ける位置を全部セットに詰め込んで計算してたけど
4つほど不正解が出る

あと関係なさそうだけど
2 2 1
2 1
が入力としたら答えはNoだよね
同じ位置じゃ線分にならんし、90度も無理あるし

2022/10/23(日) 00:22:16.64

Ex解説見てるけどNimberなんてものがあるのか、知らなかった
というか辞書順比較とロリハって勝手に相性が悪いと思ってたけど、LCP求めて一文字分比較するだけだからロリハでも普通に高速でできるね

2022/10/23(日) 00:25:48.30

>>196
Noだね

2022/10/23(日) 00:32:57.33

LCP求める方法はいろいろあるけど、ロリハにぶたんは直感的にわかりやすくて便利

2022/10/23(日) 00:37:05.68

>>196
どういうこと？Yesでは？

2022/10/23(日) 00:39:06.13

Nimberとかちょっと前に流行った概念Exに出がちだけど次出んのいつやねんという気持ちに