競技プログラミング総合スレ 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/10/31(月) 16:03:27.21ID:cNn+NHKm0
>>299,310,311 が同一人物だとしたら、そのレベルならあらゆるミスをしそうだし、原因はなんともかんとも
愚直で応えるコードを書いてもバグらせそうだし、他の人がACしたコードと比べてみるのがいいんじゃないか・・・
2022/10/31(月) 16:27:35.89ID:4XZxl/4jM
WAの原因なんてオーバーフロー以外にも無数にあるぞ
バグ、mod取り忘れ、コーナーケース、そもそも解法が間違ってる、等
2022/10/31(月) 16:34:07.66ID:yghxSU5fd
>>319
C++の整数型は(m/n)*n + m%n == mが成り立つことになっていて、除算は0方向に丸めることが規定されているからです（C++11以降）
modintがおすすめ
2022/10/31(月) 17:50:46.88ID:lvkiQp2cM
標準的な型の演算規則ぐらいは身に染み付いてた方が良いと思うので、modintなしで地雷踏み尽くして覚えていくのもありではある
324デフォルトの名無しさん (ﾜｯﾁｮｲ 2bbd-gcVw)
垢版 |
2022/10/31(月) 18:15:49.14ID:hz0WOit40
競プロって意味ないって言われてるけどどうなんだろうね？俺は楽しいからやってるけど

確かにこのアルゴリズムを直接的に実務で使うことはあまりないかもしれないけど、バグの発見とかは競プロで鍛えると速くなる気はしてる
2022/10/31(月) 18:22:42.24ID:cNn+NHKm0
まあ高校の数学と同程度には役に立つよ

ようするにめったに使わないし、そんな知識を活用せずに大成功してるひとのほうが多いくらい
2022/10/31(月) 19:21:20.60ID:sCpxrilS0
脳トレが出来るオンラインゲームみたいなもんだし実生活に役立ったら美味しいくらいの気持ちで良さそう
2022/10/31(月) 19:28:31.38ID:GYR048690
ABCのD問題までスムーズに解けたらあとは趣味程度に思った方がいいと思うよ
逆にD問題までスムーズに通せるようになることで、ある言語で手早くスクラッチする力や計算量を意識する力はかなり身につくと思う
2022/10/31(月) 19:36:01.13ID:GYR048690
あと、アルゴリズムに興味を持つきっかけになるかな
スタックがLIFOでキューがFIFOだとか基礎教養でやったとき、正直つまらない暗記対象としか思ってなかったけど、ちゃんと意味があって重要だということが分かった
SQLでB木使うとかも競プロやらなかったら意識しなかっただろうし
ハマる人とっては情報科学の入口として優秀じゃないかな、競プロと相性悪い人はストレートに勉強した方がいいんだろうけど
2022/10/31(月) 19:48:50.64ID:cNn+NHKm0
>>328
おれは先に業務してから競プロやってるけど、RDBでB木使うとかは最初からめっちゃ意識してたぞ
インデックス効かないクエリを実行すると遅すぎてすぐ障害になるからな
そんでRDBだけでは実装が難しすぎる機能とかあったりするから、他のデータ構造も学ぶようになった

競プロはほとんどのひとはすぐ挫折して継続できないみたいだし、どっちのほうが良いかと言うと難しい
2022/10/31(月) 20:01:16.37ID:GYR048690
>>329
そこは人や環境によるところかな
自分はデータ分析職やってるけど、エンジニア職ではないせいか、ちゃんと理解してる人、意識してる人が少ない
役に立つのに、低レイヤーに触れる文化がないから、自発的にアルゴ勉強する発想が出にくい
あと競プロに相性いいのは、情報系に向いてる人というよりも、元々中受算数か高校数学、高校物理みたいなのがめちゃくちゃ好きとか数オリ経験者みたいなタイプだろうね
2022/10/31(月) 20:18:35.23ID:gsksQcSqM
割と役に立つこと多いけど数論だけは未だに活用できた試しがない
2022/10/31(月) 20:32:10.84ID:GYR048690
純粋な離散数学や暗号理論も守備範囲にいれたいとすると、数論みたいな普通のエンジニアリングやデータ解析の範疇じゃ役立てるのが難しい内容も扱いうる
今の競プロの源流のICPCや情オリも、そもそもアカデミックな動機付けでやってるものだし
2022/10/31(月) 20:42:28.12ID:Z4/NCeJU0
競プロ初心者でコーダーの俺
こっちの業務の役には立たないと思ってる
情報処理の資格を無駄に取得して給料アップ程度

競プロ面では、素直に実装してTLE連発
こんなガチガチに実装したら仕様変更に耐えられないだろうな
と思いながらAC取りにいく
2022/10/31(月) 20:47:49.35ID:A5R63J6ka
話題乗り遅れたけど、rustなら x.rem_euclid(m) で余りが常に正になる
みんなrust使おう
2022/10/31(月) 21:29:59.58ID:Bx4EQ6sc0
ライブラリってデータ構造やアルゴリズムばかり気にしがちだけども細々としたutil系もあると便利よね
2022/10/31(月) 22:05:33.73ID:sD6lQxmdM
>>326
俺も同じような感じだわ。

脳トレで思ったんだけど、脳の老化防止に競技プログラミング!!
とか言って高齢者にプログラム教えたら面白いかもな。
大半はダメポだろうけど、何百人に一人は才能開花しそう。
2022/10/31(月) 22:09:17.19ID:XbU49FdB0
util系って例えばどういうの？
2022/10/31(月) 23:44:45.25ID:zCtN4VnKM
新しいFizzBazz発見した
面白いように誰もコード書けない

回答見せるとみんな悔しそうな顔をするｗ
2022/11/01(火) 00:19:04.44ID:szeLN5iaa
はいはい、すごいねー
340デフォルトの名無しさん (ﾜｯﾁｮｲ 7be2-tAkO)
垢版 |
2022/11/01(火) 02:22:23.21ID:SlcyotAo0
面接落ちまくりなので、緑で役に立つ宣伝文句教えてほしいわ（´・ω…:.;::..
341デフォルトの名無しさん (ﾜｯﾁｮｲ 1310-ZlL6)
垢版 |
2022/11/01(火) 07:51:58.39ID:3hzoyxz90
青でWeb系の就活したけど、競プロだけのアピールはあまり刺さらなかった印象
「自分のレートは上位3%です！」って言っても、はいはいすごいねーって感じだった

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

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

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

Linux, Docker, AWS、データベースなどは必須。
AWS Solution Architect も欲しい
2022/11/01(火) 09:30:51.55ID:QXtVoCESM
青くらいで競プロアピールしてくるのは地雷臭しかねえ
2022/11/01(火) 11:21:20.61ID:DmCKRmd0M
別に水色ぐらいあれば、世間が競プロerに期待する人材の要件をほぼ満たす
jobsって転がってる求人もそのレベルだし
青以上になると考察力や競プロ過学習の高低の世界なわけで、そこの色の差で評価を変える理由がほとんどの企業では見当たらない
よほどの高知能者をポテンシャル採用したいときぐらいか
青でアピールするのは地雷とか純粋培養こじらせ過ぎだな
2022/11/01(火) 11:29:28.35ID:DmCKRmd0M
世間の大半は競プロerに「FizzBuzzやそれに毛が生えたようなコーディングぐらいならすぐできて、自発的にアルゴリズムの勉強ゲームをやる勤勉な人たち」程度の期待感しか持ってないし、暖色↑で始めてアピールできるようなものだと思ってるようだと、温度差で死ぬ
2022/11/01(火) 11:31:09.90ID:YpP1+3gDM
>>344
むしろその通りだから地雷なのよ
2022/11/01(火) 11:35:22.17ID:YpP1+3gDM
- 競プロ、まあ一応水色ですけど他に専門分野/強みあります

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

アピールするならどっちかのスタンスだと思ってて青で下のパターンで来るやつがいてヤバいという話ね
2022/11/01(火) 11:35:51.24ID:DmCKRmd0M
壮大な取り違えをしててすまんが、青は高すぎて微妙って話か？
いや、まあ高すぎるってほどでもないだろ、って感覚だけど
2022/11/01(火) 11:38:35.93ID:DmCKRmd0M
>>347
理解したわ
そりゃ青の適切な使い方は上だし、メインウェポンに据えてるやつはヤバいだろう
2022/11/01(火) 11:47:34.29ID:qfAT5wFeM
>>349
でもそういう人特にjobs経由だと相当数いて競プロの評判落としてる気がするのよね

企業からしたらjobsは求人サイトの1つでしかないのにレート条件満たしてたらいけるやろと勘違いしてる的な
2022/11/01(火) 12:03:03.17ID:1IoQMX7D0
体育会系の活動は客観的な成果がそんなでもなくてもメインウェポンになる印象だから、青ぐらいでも頑張り度としては認めてほしい気持ちもあるけどねえ
もちろん、体育会系の活動を通じてわかる協調性や重労働耐性みたいなものを競プロじゃ測れないから、同様に評価されるわけはないんだけど
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番めだと思ってた。酷いｗｗ
下手したら２完だたｗｗｗ
検索しても全然出てこないから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
クソインフレおもんねーわ
結局ガキの頃から脳みそ鍛えてないとｃとかで時間とけて終わるな
ワイのレートは頭打ちや
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はスタックとしても使えるのでは
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況