競技プログラミング総合スレ 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/11/01(火) 12:09:33.52ID:mxpwEOaI0
競プロある程度強いって堂々と言えるのはやっぱり黄色くらいから?
そりゃ橙赤の人から見ればまだまだだろうけどABC対象外にはなるし
2022/11/01(火) 12:12:20.53ID:1IoQMX7D0
>>341
競プロって見た目地味だし何がすごいのか横から見てよくわからないのが課題だから、可視化するのは効きそう
N^3をNlogNまで落とした←ほーん、で?
N=1e5だと6億倍の高速化←お?
目に見えるようにするとこれだけ速くなっている←おお!
ぐらいの印象の差が出るんじゃないかと思う
2022/11/01(火) 12:20:49.62ID:1IoQMX7D0
>>352
業界に競プロerがそんなにいなければ、青ぐらいでも強いと言っていいレベルだと思うかなあ
そういうところではむしろ競プロ自体がどうすごいのか伝えるのが課題になってくる
競プロerがたくさんいる企業だとすると、その人たちのレベル感次第では黄色も「頑張ってる」ぐらいの表現で留めた方がいいかもね
赤はさすがに無条件で強いと言っていい気がするけど
2022/11/01(火) 12:22:10.63ID:1IoQMX7D0
黄色が強い方にならない企業ってよほど限られたところだとも思うけど
2022/11/01(火) 12:34:48.15ID:DmCKRmd0M
青黄が社会で自分は強いとプレゼンしてもそんなに問題は起こらないだろうけど、大会でわかりやすいタイトルを取れるほどでもないから(中高生ならJOIでちょっと積めるが)、別のところでのアピールもあった方が無難
2022/11/01(火) 12:35:28.03ID:8LMgLlix0
競プロってあくまで経験の1つとしてしか見ないよ
仕事でソロの競プロやらせるわけじゃないし…
コミュニケーションに問題ないか、とか開発経験の有無だとか、他にもいろいろチェック項目あるし競プロ以外のことも聞かなきゃならんのよ
競プロしかなさそうだな、ってひとには競技プロの取り組み方とかを掘り下げて聞くけど
2022/11/01(火) 12:38:40.95ID:DmCKRmd0M
まあ、仮に赤あってもほとんどの場合サブウェポンには変わらんと思うぞ
2022/11/01(火) 14:45:32.58ID:9QgByuPW0
黄色だけどそんな就活の役には立たんかったぞ
それよりは他に普通の開発経験を持ってて、その中で競プロをどう活かしたかの方がウケは良い
が、大抵はチーム開発経験を聞いてきて、そっちが弱いと露骨に微妙な表情するんだよな……あと最終面接で落ちる
2022/11/01(火) 16:21:29.40ID:J8SPAQYO0
ヒューリスティックの実績メインで採用されてるのは結構見るようになったけどね
2022/11/01(火) 18:54:40.62ID:6rlYl9tyM
いくらアルゴリズムに強くても即戦力から遠いからな

普通に自作した小規模の趣味のwebサイト運営してますみたいなパンチはない
2022/11/01(火) 18:57:26.58ID:6rlYl9tyM
webサイトを立ち上げられる & ノウハウを持っている
セキュリティ意識が高い&ノウハウがある ← これが一番大事

競プロ出来てもまともにクラスも書けない人
いらんわな~
2022/11/01(火) 19:11:55.23ID:mxpwEOaI0
CTFとかkaggle辺りでの実績ってどういう評価になるんだろう
2022/11/02(水) 14:13:37.34ID:Ea2TYzYwM
組合せ最適化第6版の和訳が出るぜ
2022/11/02(水) 18:02:49.90ID:9x8rFS7h0
https://github.com/yosupo06/library-checker-problems/issues/895
ガウス整数環での素因数分解
A+Biとしたときに|A|,|B| <= 10^9でも十分高速でできる
数論の知識が豊富なら再発明は困難でもなさそう、ABC-Gぐらいの問題っぽい?ARC/AGCタイプではない
結構知識を使うので考える過程でいろいろ勉強になった
2022/11/02(水) 18:08:47.53ID:9x8rFS7h0
コルテ和訳助かると思いつつも、17600円となかなか高い
第2版が値下がりしたりしないかな
367デフォルトの名無しさん (ワッチョイ 1355-FQW+)
垢版 |
2022/11/02(水) 19:34:08.80ID:eB36Kp3k0
コルテの本は競技プログラミングに役に立ちますか?
2022/11/02(水) 19:34:56.79ID:utiJQzSa0
役に立ちます
369デフォルトの名無しさん (ワッチョイ 1355-FQW+)
垢版 |
2022/11/02(水) 19:39:08.78ID:eB36Kp3k0
>>368
ありがとうございます。
高度な本で競技プログラミングにも役に立つというのはいいですね。
高度な内容を理解するのが主目的で、おまけとして競技プログラミングも強くなる。
2022/11/02(水) 21:32:43.80ID:AEY2Eek10
そうです
2022/11/03(木) 17:08:06.46ID:B0vR84k9M
昔のARCの問題は正直今のARCの練習には微妙な気がするな
何が一番近いんだ
2022/11/04(金) 10:20:19.80ID:0KQ7LFlsa
数ヶ月触って思ったけど競プロって実際の開発には結びつかんね
まぁ割りと勉強的には面白いからいいけど
2022/11/04(金) 10:56:39.54ID:B7tR4FmYa
俺はライブラリとか便利ツール作る過程で色々学んだけど元々開発経験ある人だと逆にそういうことはないか
2022/11/05(土) 00:18:45.61ID:lGny4UBo0
ARCも昔(3年程度前)の問題やってるとdiff一色分ぐらい今より高く評価されている印象だから、昔の問題解くんなら自分のレート+400〜+800ぐらいの問題解いてるとちょうどいい思考練習になると思う
2022/11/05(土) 00:41:37.71ID:lGny4UBo0
開発って点だと自動judgeツールとか、ライブラリ整備とかは一応スキルアップにつながりそう
さらに突き詰めて、競プロ用にトランスパイラ作ってる人もたまに見る気がする
けど、こういう作業って決定的な競プロの実力向上につながるわけではないので、なかなか微妙な立ち位置だよね
まあ開発方面の技術につながる楽しみ方も一応あるということで
2022/11/05(土) 11:34:34.69ID:yYAK326QM
Qiitaに珍しくいい記事があったとしてその人を雇いたいと思えるか?
競プロのレートなんてそれ以下なんだな
2022/11/05(土) 14:54:25.86ID:NDP89GFMM
>>374
diffの基準が違うと感じることはもちろんあるが、もっと根本的に問題の傾向変わってないか?
writerの差か
2022/11/05(土) 20:59:06.56ID:jsvJjD9T0
さあ、緑をめざすぞ
茶色到達したってことは4完以外だとレート下がるんだろうか
2022/11/05(土) 22:41:58.78ID:OHaBQZ4Ia
Qiitaで記事書いてるのは社内ドキュメントとか残してくれそうで歓迎
380デフォルトの名無しさん (ワッチョイ 76e2-JAaf)
垢版 |
2022/11/05(土) 22:42:19.35ID:QlP7W/960
いや、一個前の順列とか知らんし、Dはiが2,3番めだと思ってた。酷いww
下手したら2完だたwww
検索しても全然出てこないからB問題まで解ければ十分だの
2022/11/05(土) 22:43:11.47ID:qDrbvCBh0
Cムズすぎる🥲
2022/11/05(土) 22:43:16.24ID:zoo2KB540
久しぶりに順調に6完できた…
2022/11/05(土) 22:45:59.83ID:H7jWLgxi0
C問題は、C++ならライブラリ使えるから簡単すぎるけど、ライブラリ使わない前提とすると、C問題にしてはかなり難しいような
384デフォルトの名無しさん (ワッチョイ 1202-Cw2/)
垢版 |
2022/11/05(土) 22:47:11.30ID:rFNV3e/H0
クソインフレおもんねーわ
結局ガキの頃から脳みそ鍛えてないとcとかで時間とけて終わるな
ワイのレートは頭打ちや
2022/11/05(土) 22:49:20.41ID:UBpIFpTC0
F問題方針合ってたのにBITも有理数用のライブラリも作ってないせいで実装間に合わなかったけどやっぱり作っておくべきか
三連続で有理数ライブラリ使える問題出題されてるし
2022/11/05(土) 22:53:52.95ID:H7jWLgxi0
>>385
BITと逆元使うだけじゃん
そんなもん理屈わかってれば実装簡単なのに何を言い訳してるのやら
387デフォルトの名無しさん (スプッッ Sd69-vwSk)
垢版 |
2022/11/05(土) 22:57:52.72ID:nR4yZihTd
この難易度4完で3000位以下って…
しんどいよぉ
2022/11/05(土) 23:08:34.55ID:8c74vvij0
Cわりと簡単に解けたけど証明できなかったから提出するとき一番ドキドキしたw
2022/11/05(土) 23:12:16.55ID:lGny4UBo0
これ意外と非自明な事実かもしれないから書くけど、有理数をmodとって整数で表せって問題は徹頭徹尾有理数を使わないで正しい答えを出せる
2022/11/05(土) 23:14:04.30ID:lGny4UBo0
一応、素数modであることが必要かな?
2022/11/05(土) 23:16:02.54ID:lGny4UBo0
>>383
ライブラリなしなら結構頭使う方かもね
ARC-Aとかにありそう
ライブラリ前提の問題として配置したんだとするとちょっと微妙な気がするなあ
2022/11/05(土) 23:17:34.26ID:8c74vvij0
>>391
お前らC++使えよ?っていうちょくからのお達しだろうな
2022/11/05(土) 23:24:55.55ID:UBpIFpTC0
>>386
その二つ自体はそうなんだけど、分母はK^2になるから分子の情報だけ持てば良いっていうのを見落としてたせいで有理数の四則演算をしようとして実装が大変なことになったんだよね
初心者ですまん
2022/11/05(土) 23:24:57.65ID:lGny4UBo0
chokudaiはC#やkotlinも推してるからC++一強がいいとは思ってなさそうだけど、現実的にC++前提の作問が多くなるのはしょうがないところがある
他言語使いも、競プロerがC++でよくやる処理と同等のことができるようなものを用意しておいた方がいいかなあ
逆に、遠慮なく多倍長整数がバンバン出てくるような制約にしていいと思ってるんだけどね
2022/11/05(土) 23:35:04.99ID:qDrbvCBh0
30半ばのおっさんなんだけど初めて数ヶ月、C問題が解けたことが今まで数えるほどしかない(´・ω・`)
お前ら天才すぎだろ
2022/11/05(土) 23:38:00.58ID:tb67Nevqr
こんなん安倍晋三でも全完出来るだろ
2022/11/05(土) 23:38:56.42ID:8c74vvij0
全完9人しかおらんやないかーい(´・ω・`)
2022/11/05(土) 23:39:37.36ID:QbgxJiUMa
最近c問題むずいね
以前はdiff 200くらいが目安いうてた気がするけど
2022/11/05(土) 23:41:52.73ID:h/XOIx4p0
紙に(1,2,3,4,5)の順列でも書き出してにらんでれば規則性がわかるだろ
2022/11/05(土) 23:46:13.55ID:lGny4UBo0
Cは普通にむずいと思うよ
進学校で高校数学まともに勉強してた層の中の上の方がコミュニティ作ってるから基準歪んでるけど
競技と言いながらあまり相対評価に囚われちゃいけないタイプの娯楽
2022/11/05(土) 23:46:43.80ID:QbgxJiUMa
まあサンプルが親切だったね
出力例2を眺めてたらわかった
2022/11/05(土) 23:47:47.38ID:8c74vvij0
というかコドフォdiv2のA,Bあたりによくある実験してたら規則性が見えてくるやつだからまあ妥当なんじゃないですかね(証明できるとは言ってない)
2022/11/05(土) 23:52:24.78ID:lGny4UBo0
Gは形式的べき級数で楽しようとして負の二項定理?っぽいところで詰まってしまったから、これも覚えておこう
2022/11/05(土) 23:57:57.35ID:H7jWLgxi0
>>394
たしかに1000ビットとかくらいの整数の演算を要求してたまにはC++erを殺してほしい
405デフォルトの名無しさん (ワッチョイ 76e2-JAaf)
垢版 |
2022/11/06(日) 00:38:46.41ID:b6AZTKz70
>>395
30歳すぎたら酒飲んだりなんか食べながら気軽にやるのが吉
2022/11/06(日) 01:50:28.89ID:zmPGsgdt0
今回のE問題みたいなやつで、解説でDFSじゃなくてBFSが書かれてるのなんで?
最短経路が不要ならDFSでいいと思うんだけど
407デフォルトの名無しさん (ワッチョイ a901-Cw2/)
垢版 |
2022/11/06(日) 01:54:17.29ID:TnuCg6gk0
競プロ力ってWebとかシステムってよりかはゲームとかの方向な気がする。
2022/11/06(日) 10:05:08.85ID:BVrdb9YXM
>>406
2022/11/06(日) 10:53:13.10ID:v6GSz7hT0
DFSでもいいと思うよ
人によるけど、BFSの方が実装しやすいだけ
Pythonなど一部の言語だと、再設定しない限りDFSでは再帰上限でREになるから解説に書きづらいというのもある
2022/11/06(日) 11:08:07.55ID:PIbDNXM80
本当にどっちでもいいんだけど、おれもこういうときはなんとなくBFSで実装するようになってきたな
そもそも競プロの探索問題だと、DFSよりBFSを利用することのほうが多くて、BFSが手癖になってきたかな
2022/11/06(日) 12:52:40.41ID:HsT3tnctM
昨日のEx、F2行列操作の高速化か
こういう細々としたテク、ライブラリ化サボっちゃうしコンテスト中に思い出せる瞬発力もないんだよなあ
2022/11/06(日) 14:27:17.74ID:DHDxR9FJ0
ARC/AGCが補充されないけど、来月にはさすがにAGC生やすのかな?
赤が競えないサイトってAtCoderの思想的にまずいような
ARCは今年それなりに多かったし、息切れされても困るから無理に生やさなくてもいいと思うけど(そもそも今どういう内部状況か全然知らんけど)
2022/11/06(日) 14:32:15.66ID:DHDxR9FJ0
DFSのが書きやすいと思うけど、確かに再帰って言語によって計算コストに癖があるからDFSよりもBFSの方が安定なのかもね
10^6のサイズのグリッドで2次元配列使うから、遅い言語だとやや定数倍気をつけないといけないタイプ
414デフォルトの名無しさん (ワッチョイ 1255-Cw2/)
垢版 |
2022/11/06(日) 14:45:26.72ID:4JagSJ3R0
BFSはキューを使います。
DFSは再帰を使わない場合スタックを使います。
再帰を使わないとして、BFSのほうがDFSよりも実装が簡単ですか?
2022/11/06(日) 14:49:15.37ID:5xyAMfxFd
同じです
2022/11/06(日) 15:12:24.54ID:ehumOJCyM
今回みたいにただ連結判定するだけならBFSもDFSも同じようなもんだけど、木DPでやるような再帰を活かした+αの処理を非再帰化してスタックで実現しようとするとややめんどい
2022/11/06(日) 16:02:50.42ID:v6GSz7hT0
JavaだとDequeとQueueはあるがStackは古の非推奨クラスなのでBFSの方が楽
2022/11/06(日) 16:24:36.10ID:KxwCQXYpa
別解なんていくらでもあるんだから、BFSとDFSの差くらいで
「なんでこっちの解法じゃないの?」なんて悩んでたらすごく楽しいことになるぞ!
2022/11/06(日) 16:46:02.52ID:zmPGsgdt0
Dequeはスタックとしても使えるのでは
2022/11/06(日) 19:54:28.41ID:vwCXiH6d0
どっちみちお尻から取ってくるか前から取ってくるかの違いじゃろい
2022/11/07(月) 22:41:09.69ID:+urCymrW0
今日本語圏で一番知見が集積しているのってLibrary Checkerかな
英語圏、ロシア語圏、中国語圏に似たようなものはあるんだろうか
2022/11/07(月) 23:20:15.29ID:qKvylSc10
中国語やロシア語には競プロで使うやたらマニアックなアルゴリズムをまとめたページあるよ
2022/11/08(火) 16:11:47.32ID:g3rYetvfM
中国の方はまとめた辞典みたいなサイトがあったよな
前スレにあった気がする
ロシアの方は知らないんだけど、どんなやつ?
2022/11/08(火) 16:12:34.40ID:g3rYetvfM
しかし、赤diffとか解いてる感じでもARCは昔の方が簡単な気しかしないんだが、割と違う意見あるんだな
2022/11/09(水) 11:07:25.04ID:HMRJ6E6Wa
赤になりやすくなったという文脈であれば問題の難易度とはまた別の話だけどな
2022/11/09(水) 14:15:51.41ID:HotMmDzmM
あるdiff帯に限定して問題を抽出するとすれば、その難易度はそれぞれの問題の出題時期におけるそのレート帯への到達難易度と大体相関するやろ
2022/11/09(水) 15:00:23.18ID:PM/H7abua
時代とともに同じdiff帯の問題の難易度が徐々に上がるのは当たり前で、だからといってある色への到達難易度が上がるわけではない、環境だって変わってるんだから
2022/11/09(水) 15:23:24.57ID:HotMmDzmM
それは同じ傾向の典型問題がずっと出題され続けている場合に適用できる話だが、ARCは傾向が変わっているわけでそうとも言えない
ARCの昔の問題は今となっては典型となっているので、簡単に感じる、という話なら分かるんだが、どうも昔の方がアドホックで難しいと考えている人がいるのが自分の感覚だと意外だったってことが元々言いたかったことだな
2022/11/09(水) 15:48:45.39ID:HotMmDzmM
まあ、到達難易度に関しては、最大限リソースを競プロにぶち込んだときにその色になれる確率の話か、その色になるための平均的なコストの話か、でも全然違うから、その辺り明示しないと無限にややこしくなりそうだな
典型性が高まってるんであれば、前者の難易度は下がってるかもな
2022/11/09(水) 16:48:50.58ID:oxPO+/FNa
> 昔の方がアドホックで難しいと考えている人がいる

これは俺も同意できないけどソース何?まあ言いたくなければ別にいいけど
2022/11/10(木) 21:53:35.79ID:YS4V/v0d0
ICPC終わったね
MIT強いな
PurdueとSwarthmoreもそれなりの順位につけてるし、アメリカ結構来てる?
2022/11/10(木) 21:57:56.30ID:YS4V/v0d0
ARCが昔と今でアドホックさに変化があるという印象はなくて、これもどちらかというとwriter依存な気がする
少し前のmaroon回はアドホックだったようなイメージ
2022/11/10(木) 23:05:12.88ID:YS4V/v0d0
というかカーネギーメロン大学も強いな
2022/11/10(木) 23:13:57.97ID:6CBRVknNa
ARCは難易度もアドホックさも時期によってばらばらなイメージある
2022/11/11(金) 00:03:33.94ID:mxUE2nf8a
MITってMYDのワンマンチームかと思ってたから意外や
2022/11/11(金) 01:28:27.41ID:eYUvrs+I0
Benqが次出るときどういうチームになるのか気になるわ
2022/11/11(金) 11:36:15.83ID:Y094P/2Zd
CTFを勉強しようと以前アカウント作ったんだけど、難し過ぎてpicoCTFからやってたら最初のサイトを忘れた。。。
アカウント申請にもサイトを解析しないとダメでそれはクリアしてアカウント作ったんだけどどこか分かる?
2022/11/11(金) 18:24:09.39ID:Y094P/2Zd
>>437
HackTheBoxでした。
スレ汚しすいません。
439デフォルトの名無しさん (ブーイモ MM96-aTO8)
垢版 |
2022/11/11(金) 19:04:07.17ID:LHlViBaLM
数列AのLCMを10^9+7のmodで取る問題が有るんだけど、
答えが合わないのは
gcd(l, Ai)とgcd(l % 10^9+7, Ai)は異なるということ?

って自分で確かめれるか。
家帰ったら確かめよ
2022/11/11(金) 19:24:41.27ID:zSld6sc8r
じゃあレスすんな
2022/11/11(金) 19:39:51.72ID:yEEY46ODp
ツッコミどころが多すぎるけど例えばl=10^9+8の場合とかを考えてみればすぐ分かるしそのレベルだと高校数学の復習をしてからの方が成長出来そう
2022/11/11(金) 22:17:47.19ID:zKcuQYM10
gcd(1,2)=1
gcd(1+10^9+7,2)=2
2022/11/11(金) 22:20:21.87ID:zKcuQYM10
しかし、その部分でひっかけ?をするのと多倍長整数扱わせたい以外の意図を感じない珍しい問題だ
2022/11/11(金) 22:24:57.86ID:zKcuQYM10
整数をZ/pZで扱うのは一種のハッシュ化だけど、gcdやlcmみたいな数論的性質がうまいこと保存されるハッシュ化ってなんかあるんかね
2022/11/11(金) 22:49:25.23ID:hYHvcPylM
ふと思ったんだけど、競技プログラミングってすぐに結果が出るじゃん。
だから、出来た!!って達成感がすぐに味わえる。
それに対して、何かをつくるってすごく時間かかるから
達成感を感じるまでにすごく時間がかかる。
FFS理論の拡散性/保存性と関係ありそうだなって感じた。
FFS理論については俺もよくわかんないんで説明しないけど
競技プログラミング好きは拡散性が高く
何かをコツコツ作るのが好きな人は保全性が高い見ないな。
2022/11/11(金) 23:06:55.29ID:zKcuQYM10
それはあるだろうね
FFS理論はよく知らないけど、自分は刺激がないと興味関心の対象がすぐ移るから、結果やフィードバックがすぐ返ってくる競プロが性にあう
2022/11/11(金) 23:35:15.66ID:zKcuQYM10
>>443
というかこれおそらくだけどN<=10^5, A_i<=10^9とかで素因数分解させて素数ごとに指数max取らせるのが想定解みたいな問題だろうから、なんかすごい的外れなこと言ってたわ
2022/11/11(金) 23:40:03.89ID:zKcuQYM10
レベル感的にはA_i<=10^5の方がそれっぽいか
449デフォルトの名無しさん (ワッチョイ 15b1-sqhU)
垢版 |
2022/11/12(土) 19:57:29.12ID:qQOJrpEK0
競技プログラミングの鉄則のB07の問題が解けません。
これがなぜ不正解なのかわかる方いらっしゃいますか(ヘッダ省略してます)?
int main()
{
int T; // 閉店時刻、出力行数
int N; // 従業員の人数

cin >> T >> N;

// 各従業員の出勤時刻を入力して、
// 時刻毎の人数差分表を作成する。
int L,R; // 出勤時刻、退勤時刻
int diffList[500009]; // 前の時刻との人数差分リスト
for(int i = 0; i < N; i++) {
cin >> L >> R;
// 出勤時刻には人数が1人増える
diffList[L]++;
// 退勤時には人数が1人減る
diffList[R]--;
}
// 各時刻の働いている人合計を出力する
int total = 0;
for(int i = 0; i < T; i++) {
total += diffList[i];
cout << total << endl;
}
return 0;
}
2022/11/12(土) 20:20:29.60ID:w7+UUAs6a
>>449
配列初期化してなくね
真面目に初期化するかグローバルに置くか static つけるか std::vector 使う(オススメ)か
451デフォルトの名無しさん (ワッチョイ 15b1-sqhU)
垢版 |
2022/11/12(土) 20:31:37.25ID:qQOJrpEK0
>>450
配列のみグローバル領域に置いたら正解になりました!!
ありがとうございました!!
2022/11/12(土) 22:41:09.26ID:hWyV6Jgk0
5完
F,G無理無理無理
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。

ニューススポーツなんでも実況