競技プログラミング総合スレ 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/31(月) 21:29:59.58

ライブラリってデータ構造やアルゴリズムばかり気にしがちだけども細々としたutil系もあると便利よね

2022/10/31(月) 22:05:33.73

>>326
俺も同じような感じだわ。

脳トレで思ったんだけど、脳の老化防止に競技プログラミング!!
とか言って高齢者にプログラム教えたら面白いかもな。
大半はダメポだろうけど、何百人に一人は才能開花しそう。

2022/10/31(月) 22:09:17.19

util系って例えばどういうの？

2022/10/31(月) 23:44:45.25

新しいFizzBazz発見した
面白いように誰もコード書けない

回答見せるとみんな悔しそうな顔をするｗ

2022/11/01(火) 00:19:04.44

はいはい、すごいねー

2022/11/01(火) 02:22:23.21

面接落ちまくりなので、緑で役に立つ宣伝文句教えてほしいわ（´・ω…:.;::..

2022/11/01(火) 07:51:58.39

青でWeb系の就活したけど、競プロだけのアピールはあまり刺さらなかった印象
「自分のレートは上位3%です！」って言っても、はいはいすごいねーって感じだった

Webアプリを作って、見せるようにしたら多少ウケるようになった
いきなりゴリゴリのWebアプリを作るのは難しいから、例えば、競プロでよくあるグラフの入力をペーストすると、
巡回セールスマン問題を解いて、経路を描画してくれるみたいな、そういうアプリを作って、面接で見せれば、
「愚直にやるとO(N!)なんですけど、動的計画法を使うとO(2^N*N)で解けて嬉しいんですよ〜」
みたいなアルゴリズムの能力も見せれて、良いと思うよ

2022/11/01(火) 09:07:49.45

未経験からウェブ系へ転職するなら、Ruby on Rails 一択

YouTube で有名な雑食系エンジニア・KENTA や、RUNTEQ の動画を見ればよい。
KENTAのRailsサロンとか、くろかわこうへいのAWS サロンも良い

理系や競技プログラミングの知識などは、いらない。
文系で、英語・算数だけで十分

Linux, Docker, AWS、データベースなどは必須。
AWS Solution Architect も欲しい

2022/11/01(火) 09:30:51.55

青くらいで競プロアピールしてくるのは地雷臭しかねえ

2022/11/01(火) 11:21:20.61

別に水色ぐらいあれば、世間が競プロerに期待する人材の要件をほぼ満たす
jobsって転がってる求人もそのレベルだし
青以上になると考察力や競プロ過学習の高低の世界なわけで、そこの色の差で評価を変える理由がほとんどの企業では見当たらない
よほどの高知能者をポテンシャル採用したいときぐらいか
青でアピールするのは地雷とか純粋培養こじらせ過ぎだな

2022/11/01(火) 11:29:28.35

世間の大半は競プロerに「FizzBuzzやそれに毛が生えたようなコーディングぐらいならすぐできて、自発的にアルゴリズムの勉強ゲームをやる勤勉な人たち」程度の期待感しか持ってないし、暖色↑で始めてアピールできるようなものだと思ってるようだと、温度差で死ぬ

2022/11/01(火) 11:31:09.90

>>344
むしろその通りだから地雷なのよ

2022/11/01(火) 11:35:22.17

- 競プロ、まあ一応水色ですけど他に専門分野/強みあります

- ガチで競技として取り組んでててICPCメダリストです

アピールするならどっちかのスタンスだと思ってて青で下のパターンで来るやつがいてヤバいという話ね

2022/11/01(火) 11:35:51.24

壮大な取り違えをしててすまんが、青は高すぎて微妙って話か？
いや、まあ高すぎるってほどでもないだろ、って感覚だけど

2022/11/01(火) 11:38:35.93

>>347
理解したわ
そりゃ青の適切な使い方は上だし、メインウェポンに据えてるやつはヤバいだろう

2022/11/01(火) 11:47:34.29

>>349
でもそういう人特にjobs経由だと相当数いて競プロの評判落としてる気がするのよね

企業からしたらjobsは求人サイトの1つでしかないのにレート条件満たしてたらいけるやろと勘違いしてる的な

2022/11/01(火) 12:03:03.17

体育会系の活動は客観的な成果がそんなでもなくてもメインウェポンになる印象だから、青ぐらいでも頑張り度としては認めてほしい気持ちもあるけどねえ
もちろん、体育会系の活動を通じてわかる協調性や重労働耐性みたいなものを競プロじゃ測れないから、同様に評価されるわけはないんだけど

2022/11/01(火) 12:09:33.52

競プロある程度強いって堂々と言えるのはやっぱり黄色くらいから？
そりゃ橙赤の人から見ればまだまだだろうけどABC対象外にはなるし

2022/11/01(火) 12:12:20.53

>>341
競プロって見た目地味だし何がすごいのか横から見てよくわからないのが課題だから、可視化するのは効きそう
N^3をNlogNまで落とした←ほーん、で？
N=1e5だと6億倍の高速化←お？
目に見えるようにするとこれだけ速くなっている←おお！
ぐらいの印象の差が出るんじゃないかと思う

2022/11/01(火) 12:20:49.62

>>352
業界に競プロerがそんなにいなければ、青ぐらいでも強いと言っていいレベルだと思うかなあ
そういうところではむしろ競プロ自体がどうすごいのか伝えるのが課題になってくる
競プロerがたくさんいる企業だとすると、その人たちのレベル感次第では黄色も「頑張ってる」ぐらいの表現で留めた方がいいかもね
赤はさすがに無条件で強いと言っていい気がするけど

2022/11/01(火) 12:22:10.63

黄色が強い方にならない企業ってよほど限られたところだとも思うけど

2022/11/01(火) 12:34:48.15

青黄が社会で自分は強いとプレゼンしてもそんなに問題は起こらないだろうけど、大会でわかりやすいタイトルを取れるほどでもないから(中高生ならJOIでちょっと積めるが)、別のところでのアピールもあった方が無難

2022/11/01(火) 12:35:28.03

競プロってあくまで経験の1つとしてしか見ないよ
仕事でソロの競プロやらせるわけじゃないし…
コミュニケーションに問題ないか、とか開発経験の有無だとか、他にもいろいろチェック項目あるし競プロ以外のことも聞かなきゃならんのよ
競プロしかなさそうだな、ってひとには競技プロの取り組み方とかを掘り下げて聞くけど

2022/11/01(火) 12:38:40.95

まあ、仮に赤あってもほとんどの場合サブウェポンには変わらんと思うぞ

2022/11/01(火) 14:45:32.58

黄色だけどそんな就活の役には立たんかったぞ
それよりは他に普通の開発経験を持ってて、その中で競プロをどう活かしたかの方がウケは良い
が、大抵はチーム開発経験を聞いてきて、そっちが弱いと露骨に微妙な表情するんだよな……あと最終面接で落ちる

2022/11/01(火) 16:21:29.40

ヒューリスティックの実績メインで採用されてるのは結構見るようになったけどね

2022/11/01(火) 18:54:40.62

いくらアルゴリズムに強くても即戦力から遠いからな

普通に自作した小規模の趣味のwebサイト運営してますみたいなパンチはない

2022/11/01(火) 18:57:26.58

webサイトを立ち上げられる　& ノウハウを持っている
セキュリティ意識が高い&ノウハウがある　←　これが一番大事

競プロ出来てもまともにクラスも書けない人
いらんわな～

2022/11/01(火) 19:11:55.23

CTFとかkaggle辺りでの実績ってどういう評価になるんだろう

2022/11/02(水) 14:13:37.34

組合せ最適化第6版の和訳が出るぜ

2022/11/02(水) 18:02:49.90

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.53

コルテ和訳助かると思いつつも、17600円となかなか高い
第2版が値下がりしたりしないかな

2022/11/02(水) 19:34:08.80

コルテの本は競技プログラミングに役に立ちますか？

2022/11/02(水) 19:34:56.79

役に立ちます

2022/11/02(水) 19:39:08.78

>>368
ありがとうございます。
高度な本で競技プログラミングにも役に立つというのはいいですね。
高度な内容を理解するのが主目的で、おまけとして競技プログラミングも強くなる。

2022/11/02(水) 21:32:43.80

そうです

2022/11/03(木) 17:08:06.46

昔のARCの問題は正直今のARCの練習には微妙な気がするな
何が一番近いんだ

2022/11/04(金) 10:20:19.80

数ヶ月触って思ったけど競プロって実際の開発には結びつかんね
まぁ割りと勉強的には面白いからいいけど

2022/11/04(金) 10:56:39.54

俺はライブラリとか便利ツール作る過程で色々学んだけど元々開発経験ある人だと逆にそういうことはないか

2022/11/05(土) 00:18:45.61

ARCも昔（3年程度前）の問題やってるとdiff一色分ぐらい今より高く評価されている印象だから、昔の問題解くんなら自分のレート+400～+800ぐらいの問題解いてるとちょうどいい思考練習になると思う

2022/11/05(土) 00:41:37.71

開発って点だと自動judgeツールとか、ライブラリ整備とかは一応スキルアップにつながりそう
さらに突き詰めて、競プロ用にトランスパイラ作ってる人もたまに見る気がする
けど、こういう作業って決定的な競プロの実力向上につながるわけではないので、なかなか微妙な立ち位置だよね
まあ開発方面の技術につながる楽しみ方も一応あるということで

2022/11/05(土) 11:34:34.69

Qiitaに珍しくいい記事があったとしてその人を雇いたいと思えるか？
競プロのレートなんてそれ以下なんだな

2022/11/05(土) 14:54:25.86

>>374
diffの基準が違うと感じることはもちろんあるが、もっと根本的に問題の傾向変わってないか？
writerの差か

2022/11/05(土) 20:59:06.56

さあ、緑をめざすぞ
茶色到達したってことは4完以外だとレート下がるんだろうか

2022/11/05(土) 22:41:58.78

Qiitaで記事書いてるのは社内ドキュメントとか残してくれそうで歓迎

2022/11/05(土) 22:42:19.35

いや、一個前の順列とか知らんし、Dはiが2,3番めだと思ってた。酷いｗｗ
下手したら２完だたｗｗｗ
検索しても全然出てこないからB問題まで解ければ十分だの

2022/11/05(土) 22:43:11.47

Cムズすぎる🥲

2022/11/05(土) 22:43:16.24

久しぶりに順調に6完できた…

2022/11/05(土) 22:45:59.83

C問題は、C++ならライブラリ使えるから簡単すぎるけど、ライブラリ使わない前提とすると、C問題にしてはかなり難しいような

2022/11/05(土) 22:47:11.30

クソインフレおもんねーわ
結局ガキの頃から脳みそ鍛えてないとｃとかで時間とけて終わるな
ワイのレートは頭打ちや

2022/11/05(土) 22:49:20.41

F問題方針合ってたのにBITも有理数用のライブラリも作ってないせいで実装間に合わなかったけどやっぱり作っておくべきか
三連続で有理数ライブラリ使える問題出題されてるし

2022/11/05(土) 22:53:52.95

>>385
BITと逆元使うだけじゃん
そんなもん理屈わかってれば実装簡単なのに何を言い訳してるのやら

2022/11/05(土) 22:57:52.72

この難易度4完で3000位以下って…
しんどいよぉ

2022/11/05(土) 23:08:34.55

Cわりと簡単に解けたけど証明できなかったから提出するとき一番ドキドキしたw

2022/11/05(土) 23:12:16.55

これ意外と非自明な事実かもしれないから書くけど、有理数をmodとって整数で表せって問題は徹頭徹尾有理数を使わないで正しい答えを出せる

2022/11/05(土) 23:14:04.30

一応、素数modであることが必要かな？

2022/11/05(土) 23:16:02.54

>>383
ライブラリなしなら結構頭使う方かもね
ARC-Aとかにありそう
ライブラリ前提の問題として配置したんだとするとちょっと微妙な気がするなあ

2022/11/05(土) 23:17:34.26

>>391
お前らC++使えよ？っていうちょくからのお達しだろうな

2022/11/05(土) 23:24:55.55

>>386
その二つ自体はそうなんだけど、分母はK^2になるから分子の情報だけ持てば良いっていうのを見落としてたせいで有理数の四則演算をしようとして実装が大変なことになったんだよね
初心者ですまん

2022/11/05(土) 23:24:57.65

chokudaiはC#やkotlinも推してるからC++一強がいいとは思ってなさそうだけど、現実的にC++前提の作問が多くなるのはしょうがないところがある
他言語使いも、競プロerがC++でよくやる処理と同等のことができるようなものを用意しておいた方がいいかなあ
逆に、遠慮なく多倍長整数がバンバン出てくるような制約にしていいと思ってるんだけどね

2022/11/05(土) 23:35:04.99

30半ばのおっさんなんだけど初めて数ヶ月、C問題が解けたことが今まで数えるほどしかない(´・ω・｀)
お前ら天才すぎだろ

2022/11/05(土) 23:38:00.58

こんなん安倍晋三でも全完出来るだろ

2022/11/05(土) 23:38:56.42

全完9人しかおらんやないかーい(´・ω・`)

2022/11/05(土) 23:39:37.36

最近c問題むずいね
以前はdiff 200くらいが目安いうてた気がするけど

2022/11/05(土) 23:41:52.73

紙に(1,2,3,4,5)の順列でも書き出してにらんでれば規則性がわかるだろ

2022/11/05(土) 23:46:13.55

Cは普通にむずいと思うよ
進学校で高校数学まともに勉強してた層の中の上の方がコミュニティ作ってるから基準歪んでるけど
競技と言いながらあまり相対評価に囚われちゃいけないタイプの娯楽

2022/11/05(土) 23:46:43.80

まあサンプルが親切だったね
出力例2を眺めてたらわかった

2022/11/05(土) 23:47:47.38

というかコドフォdiv2のA,Bあたりによくある実験してたら規則性が見えてくるやつだからまあ妥当なんじゃないですかね(証明できるとは言ってない)

2022/11/05(土) 23:52:24.78

Gは形式的べき級数で楽しようとして負の二項定理？っぽいところで詰まってしまったから、これも覚えておこう

2022/11/05(土) 23:57:57.35

>>394
たしかに1000ビットとかくらいの整数の演算を要求してたまにはC++erを殺してほしい

2022/11/06(日) 00:38:46.41

>>395
30歳すぎたら酒飲んだりなんか食べながら気軽にやるのが吉

2022/11/06(日) 01:50:28.89

今回のE問題みたいなやつで、解説でDFSじゃなくてBFSが書かれてるのなんで？
最短経路が不要ならDFSでいいと思うんだけど

2022/11/06(日) 01:54:17.29

競プロ力ってWebとかシステムってよりかはゲームとかの方向な気がする。

2022/11/06(日) 10:05:08.85

>>406

2022/11/06(日) 10:53:13.10

DFSでもいいと思うよ
人によるけど、BFSの方が実装しやすいだけ
Pythonなど一部の言語だと、再設定しない限りDFSでは再帰上限でREになるから解説に書きづらいというのもある

2022/11/06(日) 11:08:07.55

本当にどっちでもいいんだけど、おれもこういうときはなんとなくBFSで実装するようになってきたな
そもそも競プロの探索問題だと、DFSよりBFSを利用することのほうが多くて、BFSが手癖になってきたかな

2022/11/06(日) 12:52:40.41

昨日のEx、F2行列操作の高速化か
こういう細々としたテク、ライブラリ化サボっちゃうしコンテスト中に思い出せる瞬発力もないんだよなあ

2022/11/06(日) 14:27:17.74

ARC/AGCが補充されないけど、来月にはさすがにAGC生やすのかな？
赤が競えないサイトってAtCoderの思想的にまずいような
ARCは今年それなりに多かったし、息切れされても困るから無理に生やさなくてもいいと思うけど（そもそも今どういう内部状況か全然知らんけど）

2022/11/06(日) 14:32:15.66

DFSのが書きやすいと思うけど、確かに再帰って言語によって計算コストに癖があるからDFSよりもBFSの方が安定なのかもね
10^6のサイズのグリッドで2次元配列使うから、遅い言語だとやや定数倍気をつけないといけないタイプ

2022/11/06(日) 14:45:26.72

BFSはキューを使います。
DFSは再帰を使わない場合スタックを使います。
再帰を使わないとして、BFSのほうがDFSよりも実装が簡単ですか？

2022/11/06(日) 14:49:15.37

同じです

2022/11/06(日) 15:12:24.54

今回みたいにただ連結判定するだけならBFSもDFSも同じようなもんだけど、木DPでやるような再帰を活かした+αの処理を非再帰化してスタックで実現しようとするとややめんどい

2022/11/06(日) 16:02:50.42

JavaだとDequeとQueueはあるがStackは古の非推奨クラスなのでBFSの方が楽

2022/11/06(日) 16:24:36.10

別解なんていくらでもあるんだから、BFSとDFSの差くらいで
「なんでこっちの解法じゃないの？」なんて悩んでたらすごく楽しいことになるぞ！

2022/11/06(日) 16:46:02.52

Dequeはスタックとしても使えるのでは

2022/11/06(日) 19:54:28.41

どっちみちお尻から取ってくるか前から取ってくるかの違いじゃろい

2022/11/07(月) 22:41:09.69

今日本語圏で一番知見が集積しているのってLibrary Checkerかな
英語圏、ロシア語圏、中国語圏に似たようなものはあるんだろうか

2022/11/07(月) 23:20:15.29

中国語やロシア語には競プロで使うやたらマニアックなアルゴリズムをまとめたページあるよ

2022/11/08(火) 16:11:47.32

中国の方はまとめた辞典みたいなサイトがあったよな
前スレにあった気がする
ロシアの方は知らないんだけど、どんなやつ？

2022/11/08(火) 16:12:34.40

しかし、赤diffとか解いてる感じでもARCは昔の方が簡単な気しかしないんだが、割と違う意見あるんだな

2022/11/09(水) 11:07:25.04

赤になりやすくなったという文脈であれば問題の難易度とはまた別の話だけどな

2022/11/09(水) 14:15:51.41

あるdiff帯に限定して問題を抽出するとすれば、その難易度はそれぞれの問題の出題時期におけるそのレート帯への到達難易度と大体相関するやろ

2022/11/09(水) 15:00:23.18

時代とともに同じdiff帯の問題の難易度が徐々に上がるのは当たり前で、だからといってある色への到達難易度が上がるわけではない、環境だって変わってるんだから

2022/11/09(水) 15:23:24.57

それは同じ傾向の典型問題がずっと出題され続けている場合に適用できる話だが、ARCは傾向が変わっているわけでそうとも言えない
ARCの昔の問題は今となっては典型となっているので、簡単に感じる、という話なら分かるんだが、どうも昔の方がアドホックで難しいと考えている人がいるのが自分の感覚だと意外だったってことが元々言いたかったことだな

2022/11/09(水) 15:48:45.39

まあ、到達難易度に関しては、最大限リソースを競プロにぶち込んだときにその色になれる確率の話か、その色になるための平均的なコストの話か、でも全然違うから、その辺り明示しないと無限にややこしくなりそうだな
典型性が高まってるんであれば、前者の難易度は下がってるかもな

2022/11/09(水) 16:48:50.58

> 昔の方がアドホックで難しいと考えている人がいる

これは俺も同意できないけどソース何？まあ言いたくなければ別にいいけど

2022/11/10(木) 21:53:35.79

ICPC終わったね
MIT強いな
PurdueとSwarthmoreもそれなりの順位につけてるし、アメリカ結構来てる？

2022/11/10(木) 21:57:56.30

ARCが昔と今でアドホックさに変化があるという印象はなくて、これもどちらかというとwriter依存な気がする
少し前のmaroon回はアドホックだったようなイメージ

2022/11/10(木) 23:05:12.88

というかカーネギーメロン大学も強いな

2022/11/10(木) 23:13:57.97

ARCは難易度もアドホックさも時期によってばらばらなイメージある