競技プログラミング総合スレ 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/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に出がちだけど次出んのいつやねんという気持ちに

2022/10/23(日) 00:43:07.21

>>200
あ、すまん
A1,A2,A3
x y
の並びかと思った（そんな形の入力ありえんのに）
普通にYesじゃんこれ

**196** (ﾜｯﾁｮｲ 0279-SGBs) · 2022/10/23(日) 00:45:48.66

あ、、、自分のミスだった
最後のA[N]でジャスト(x,y)にたどり着くのか
勝手に最後だけ距離が未定義だと思ってた
すみませんでした！

2022/10/23(日) 00:51:07.79

>>201
こどふぉで役に立つかも精神で・・・
そういえば、ARCはDEとかで割と高度典型が出現することあるけど、AGC後半ってどのぐらい知識が役に立つ問題出るんだろうね
AGCはアドホックの祭典という評判だけはずっと聞いているが、後ろの問題は手をつけていないので実態は知らない

2022/10/23(日) 14:02:32.86

昨日のC問題が全然わからん😭

2022/10/23(日) 14:11:03.89

親子関係を図で書いていったら何すればいいか見通しがいいと思うよ

2022/10/23(日) 15:00:21.51

日本語が難しかったね
ナンバリングの法則がちょっとイメージしにくかったかも

2022/10/23(日) 15:50:26.46

こどふぉdiv 1だ
少ないと思ったら急にたくさん生えてきた

2022/10/23(日) 16:04:19.15

今日のこどふぉ2連続間隔15分しかないのおかしい　

2022/10/23(日) 19:45:09.56

昨日のABCのD問題、
なんかランタイムエラーが5つ程。
C++でもPythonでも同じ。

配列のサイズを入力した数字の合計(プラスα)から計算した値から定数値に変えたらAC

添え字のチェックして処理を飛ばしてもWAにはならずRE

どんなエラーになったか確認したくて
テストケース欲しい…
けど、社長はテストケース公開消極派なのね。
自分でテストケース作るのは難しい

2022/10/23(日) 19:51:50.60

今だってABCの範囲だと意味があるのは5問目程度までだろうから、せめてサンプル強くして難易度下げるべき

2022/10/23(日) 20:41:45.90

いうて自分でテスト書いて検証する力って、なんなら本旨の算数パズルよりもずっと実務寄りの能力な気がするが

2022/10/23(日) 20:54:13.16

>>210
とりあえず、限界値っぽいのを入れてみたら？

1000 -10000 -10000
10 10 10 10 10 10 10 10・・・1000個分

2022/10/24(月) 02:06:39.23

茶色になったばっかの新人コーダーだが、
土曜日C問題まで解いたけど若干レート下がった
時間一杯までやってしまったこともあるけど、C問題まで解いただけじゃ緑までいけないのか

2022/10/24(月) 02:22:46.20

だいたいcで茶、dで緑、eで水やね

2022/10/24(月) 02:23:04.27

安定して4完できるぐらいじゃないと緑は無理じゃないかな
緑の過去問を解く練習しよう

2022/10/24(月) 11:29:28.22

なんか勘違いしてね？