競技プログラミング総合スレ 65
■ このスレッドは過去ログ倉庫に格納されています
!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 社長曰く以外の感じなので、例えばバックエンドエンジニアで良い評価が欲しいなら青色くらい必要
https://twitter.com/chokudai/status/1474258242452987907
AtCoderがそのまま役立つ業務ってだいぶ少なくて、
【評価高】は赤まで、
数理最適化・研究開発
【評価中】は青～水まで、（黄もまれに？）
バックエンドエンジニア・機械学習エンジニア
【評価低～評価無】は水～茶色まで、
その他のITエンジニア
くらいがプラス評価になります。関連度が高ければ高いほど高いレートが評価されやすくなり、逆に低いと低いレートですぐカンストしちゃう、って感じ。
評価低に関しては「コードが書けることが保証されてる」くらいのアピールにしかならないです。
https://twitter.com/5chan_nel (5ch newer account) 問題文によってX軸とY軸がどの方向か明記されていない場合どうすれば良いのでしょうか
左右方向がX軸
上下方向がY軸
と思って解いていたら解説の画像見ると真逆でした
例えば鉄則本のB09 - Papers >>3
プラス効果実感できそうなのが青くらいというのはそうなのかもしれない
茶色以上だったら、ないよりはある方がマシって場面はたくさんあると思うけどね
こんなのセルフプロモーション力次第だから、そこがヘタクソだと何色でも…というところがあるかな >>8
本持ってないので確認できないけど、確かに普通数学では左右がx軸、上下がy軸方向で書かれることが多いからちょっと混乱する人もいるかも
問題見た限り、答えに影響しないのでどっちで書いてもいいってことで、逆に書いたんじゃないかな
ちなみに競プロだと配列の添字の関係で逆に書く場合のメリットもあるんだよね（この問題はそのメリットも別にないけど）
明記されてない場合はほぼ答えに影響しない場合だから、勝手に自分の中で決めればいいと思う、影響するんなら質問タブから聞こう >>11
ごめん、思い切り多次元配列使うから普通にメリットあったね 軸の方向なんてだいたいどうでもいいよ
自分の好きに描いてくれとしかいえない
向きの考慮必要な問題なら普通は記載されてる
ただまあ実装としては配列操作の都合上、どっちかのほうが簡単になることはあるので、
賢いひとだと考察や実装しやすいように柔軟に向きを入れ替えてるかな >>11
＞＞答えに影響しないのでどっちで書いてもいいってことで、逆に書いたんじゃないかな
ありがとうございます 業務プログラミングでも画像処理やってるとたまに軸の順番が入れ替わるから困る googbyeみたいに定期的にall ratedコン出せるのすごいよな
逆にAtCoderが厳格すぎる 質問
apg4bが終わったばかりの競プロ初心者だけど、次に読めばいい本は3つのうちのどれですか？
・競技プログラミングの鉄則
・問題解決のためのアルゴリズム×数学
・アルゴリズムとデータ構造 apg4b終わった時点でも人によってどのくらいの行間を読めるか違うから一概に言えない
実際に書店とかで読んで選んではどう？ 新しい本だから今取り組んでる人が多いという理由で鉄則本かなあ
〇〇本を読んで上達したみたいな話は聞かないから
結局自分の努力次第だよね AtCoder Problemsで自分のレートに近いdiffの問題解いていくのが結局一番着実だったりする 蟻本完璧に咀嚼しきれたら青〜黄色はいけると思うしアレは中級者向けでしょ
螺旋本は教養としては大事だけど傾向が若干違う気もするし鉄則本かけんちょん本が良さそう 結局本とかで勉強するよりも自分の実力ちょい上の問題を解きまくる方が効果あるのは事実 黄色より上は知識とは別体系の技能だから、本読んでどうこうって感じの世界ではないかな 蟻本は難易度的には、第2章が普通に初心者向けの内容だし、初心者でも読めるでしょ
ただジャッジがPOJとかだったりして不便、という理由があるために今どきの入門者向けではないかなあ
基礎問題のあとにいきなり難易度が上がった問題が出てきたりするけど、そういうのを飛ばせば誰でも読めるだろうし、
そういうのも全部習得していけばABC卒業できるほどの基礎力が付く
鉄則本は基礎問題が中心に載ってて、解説もわかりやすいから、数学力に自信のない初心者にはとてもおすすめ おじさんが学生の頃は螺旋本読んで蟻本読んだら青になれた
最近は新しい本出てるらしいけど読んだことがないので何色向けか分からない ・数学の得意不得意
・プログラミングの経験
この二つで結構勉強方針変わるかも そうそう、初心者向けじゃない競プロの本なんてないけど、地力の違いでどれがフィットするかはちょっとずつ変わるよねえ 数学そんなに得意じゃない場合、大学数学の場合の数や整数の参考書が役に立つこともある あ、大学数学じゃなくて大学受験な
大学数学も実は役に立つ本あるんだが >>30
蟻本も人によってはくどくなくてちょうどいい入門書だからね 数学は特に得意でも不得意でも無いよ
あと、プログラミングの経験はほとんど無くてAPG4bが初めてと言っても過言では無いと思う
上で挙げた3つの本の他にけんちょんさんが書いてるAtCoder入門なんかも良さそう 運営がワールドワイドならそれも可能だろうけどこれはしゃーねえべ(´・ω・`)ぽれはお盆の時期とか出たくないのに逆にコンテスト生やしてくるし 俺も正月はいいや、暇だけど実家だから回線悪い(´・ω・｀) 整数と場合の数だと大学への数学のやつかな
あれを全部スラスラ解けるぐらいにしとくと捗る 初等整数論とか組合せ論の初歩についてあまり詳しくないけれど、
プログラミングコンテストでは強いっていう人はいるんですか？
プログラミングコンテストで強い人はみな数学にも強いのではないですか？ プログラミングコンテストにもいろいろあって、競技プログラミングのアルゴリズムという分野のコンテスト（具体的にはAtCoderのABC、ARC、AGCは全部そう）は、整数、組合せ論の問題が離散数学の一部として出題されるので、もろに成績に関係する
一方で、ヒューリスティックだったりKaggleに関しては、実はそうでもないんじゃないかという気がする
当然、基礎的な能力として、整数と組合せ論を最低限勉強しておいた方が離散数学的な操作に慣れて思考の助けになるところはあると思うし、勉強さえすればレベルの高いところまでできるような人がいずれのコンテストでも上に来ると思うけど 組合わせ論・数論の精選とかパーフェクトマスターみたいな数オリ用対策用の参考書って競プロにも役立つの？たまに買ってる人見かけるけど黄色以上で効くのかな 繁野麻衣子著『ネットワーク最適化とアルゴリズム』を買いましたが、積読状態です。
この本は競技プログラミングに役立ちますか？ いつだったか、数オリ高度典型の幾何がAGCかARCに出てて話題になったからごくたまに効くんじゃないか >>47
未読なので目次見ただけだけど、この本のアルゴリズムは全部競プロで頻出だと思うので、知らない知識を摂取するって意味だとどれも役立ちそうかな？ >>44,48,50
ありがとうございました。
>>50
読んでみます。 純粋な学術書は体系的すぎて競プロで使うには多く説明しすぎてることもあるから、効率がいいかはわからんな
ただ、普通に競プロ関係なく勉強になるところはいい 最悪計算量と何ができるか知ってるだけでも競プロでは使えるな
順位クエリ処理できる二分探索木の仕組み分かってないけど他人のライブラリコピペして使ってるわ なかなか灰色から上がることが難しそうですね...
とりあえずアルゴリズム×数学 本 か鹿本(AtCoder入門)を買ってみませんか
茶色に上がってみましょう 和を積に変換
https://twitter.com/noshi91/status/1608869946792235008
和のままで十分性質がいいじゃん！と先入観で思ってしまうが、あえて多項式を使った式を介して積にした方がtop treeに乗せやすいみたい
面白い
https://twitter.com/5chan_nel (5ch newer account) >>55
数学が苦手な人は入茶でもかなり時間かかる時代な気がするね
灰色を分割して階級をさらに分けるのは真面目にありだと思ってるけど 部分列（連続ではない）の和の総和は[x]Π(2+ax)か
この場合はそんなに役立ってる感ないが TopTreeて高度典型みたいなやつだろ
俺も名前しか知らん LC木の上位互換でLC木に乗らないものが乗ったりするが、そもそもLC木自体がマニアックでAtCoderではなかなか使用機会ないだろうな
強いデータ構造がなきゃ解けない問題、強いデータ構造で一瞬で解けてしまう問題をAtCoderがそもそも好まないというのもあるし データ構造に載せるモノイド、頑張れば多項式か行列に帰着できる説 半束とかはモノイドだけど多項式や行列にはならなくないか 適当に和に相当する演算を導入して半環の積にできんかとか考えたけど無理か あまり半束であって束じゃない例について考えたことなかったけど根付木のLCAとか？ >>65
ところで、束論はどの本で勉強しましたか？
離散数学の本にすこしだけ書いてあることがありますが、役に立ちますか？ >>66
min, maxの一般化であるってことと定義を知っているってだけで、まともに勉強したことないかなあ
どこで最初に知ったんだろ、雪江代数にあったっけ？
ゼータ変換を束を使って捉え直すことができるみたいなのはあった気がするけど、束論自体をつきつめることが直接競プロにプラスになる感じではない印象
というか、抽象代数の勉強は全般的にそんな感じな気がする (1+a_k)の積を微分していったら定数項に基本対称式が全部出るのか 嬉しいかなあ 今日日モーメント母関数がそんなにうれしいものなのかという話になりそう 何の捻りもないけど、セグ木にのせてrange M次対称式 query（与えられた区間内の要素のM次対称式を出力）がQMlogNで解ける と思ったけどlogMつくか
更新ないんならセグ木に乗せるんじゃなくて累積和でやる方がいいな どっかで出てそうと思ってelementary symmetric polynomials segment treeとか検索してるけど意外とないもんだ 鯖のcpu性能が上がったせいで過去の問題が別の解法(計算量悪化)で通せるようになることってあるのかな？
パソコン新しくしようとしてて気になった N=2*10^5だとガチガチにチューニングしたC++で非想定が通ってしまうからN=3*10^5にしたみたいな問題だと、普通に非想定通るようになってそうだな 土夜と日夜だったら普通の人は土夜の方が予定入りやすいとかあるんかな テレワークで出勤時間なくなってからは24時までに寝られれば十分になった AtCoderの過去問って他人の提出検索できるけど、case_11.txt だけ間違えてるやつ一覧みたいのって取ってこれるんかな？ 同じようなテストケース通し具合のコードを持ってくるサービスあった気がする
探したけど見つからなかった
確か赤コーダーTLで見つけたはず >>84 >>85
もしかして: AtCoder Companions 言語仕様の勘違い由来のバグ取りはかなり気付くの難しいから、初心者がそういうの見つけるのに使えそうだな 今年こそ青に定着したいのに三が日何もやってねえ...(´・ω・`) 正月で生活リズムが整っちゃってこどふぉに出られなくなっちゃった Hello 2023普通に良コンテストだったぞ
ドンマイ えAtCoder Companions有能すぎるんだけど. これ何でテンプレ入ってないん? TL少し長めの問題なら、10^9回計算する解法でも通るんだね（想定解法じゃなかったけど） 重複組合せの式nHrで、整数のオーバーフローをできるだけ避けて計算したいのですが
とある、場合の数を数える問題で、普通はたぶんDP的に解くんだけど、規則的な形だった
ので、「これって重複組合せじゃん」と見抜いたんですよ
でnHrを例の階乗の公式(n+r)!/n!/r!で計算して、テストケースを走らせるとnやrが小さい
のは通るのでやはりおkらしい。ただnやrが大きくなると階乗がオーバーフローしてしまう
解が数式で求まったのに数値的にはそんなに便利じゃないって?
でも普通nHrの計算って分子と分母でキャンセルして結果は大きくならないことが多い
ですよね。うまいこと変形したらオーバーフローしなさそう。もしそういうのが既にあれば
nHrの漸化式みたいので計算する手もありそう、って結局DPみたいなことしてる気がw >>94
どちらも2から60ぐらいの間の整数がランダムな感じでセットされるようです >>96
どうもです。が、n, mは実際には100ぐらいまでいくようで（すみません）、
リンク先の最初のコードだと 100 C 99 とかで間違った答えが。おっとクヌース先生敗北?
こういう場合は普通にCの性質より 100 C 99 = 100 C (100-99) = 100 C 1 とすれば
精度も計算量も良さそうです
というわけで... 全テストケースクリアしました! ありがとうございます >>99
そうですね、nCrで r=n/2付近はでかい数になりますよね
テストケースではそういう場合は除外されているようです
そういうわけで、組み合わせを直接計算するとテストケースでは64bit整数がいるんですが、
組み合わせの直接計算でなく、DPで再帰的に場合の数を計算するようなコードだと
32bit整数で大丈夫な感じなんですが... ええと ■ このスレッドは過去ログ倉庫に格納されています
