競技プログラミング総合スレ 64

競技プログラミング総合スレ 64 at TECH

[前50を表示]
300:デフォルトの名無しさん
22/10/31 12:31:58.77 qgwFPKRF0.net
問題に付いてるサンプルケースでは正解なのに、ソースコード提出すると他のテストケースで不正解となるんです
おそらくどこかでオーバーフローしていることが原因です
過去のコンテストのテストケースって全部どこかにアップロードされているんでしょうか？

301:デフォルトの名無しさん
22/10/31 13:05:29.42 MMRjCKAsd.net
URLﾘﾝｸ(atcoder.jp)
ないものも多いですしテストケースを見ることは推奨されていません
自力でテストケースを作って頑張る方法を身につけるのがいい
参考：URLﾘﾝｸ(betrue12.hateblo.jp)

302:デフォルトの名無しさん
22/10/31 13:10:33.60 MMRjCKAsd.net
オーバーフローならC++(gcc)だったら-fsanitize=undefinedで見つかるかも

303:デフォルトの名無しさん
22/10/31 13:25:03.50 xYj0Vm7Pa.net
オーバーフローしていることが原因とまで当たりついてるなら、一ヶ所ずつ型変えて提出してみたら

304:デフォルトの名無しさん
22/10/31 13:29:23.39 lvkiQp2cM.net
オーバーフローが原因だと分かってるんならもうACはすぐそこじゃないか
頑張れ

305:デフォルトの名無しさん
22/10/31 14:29:51.95 qgwFPKRF0.net
>>301
>>302
貴重な情報ありがとうございます
 >>303
>>304
unsigned longでもオーバーフローしてしまいます

306:デフォルトの名無しさん
22/10/31 14:46:00.66 yghxSU5fd.net
実はオーバーフローしてないんじゃない？

307:デフォルトの名無しさん
22/10/31 15:57:04.81 XwJ24qqi0.net
まさか余りをとる時に負になるケースを考慮していないとか？
ABC-DEFとか

308:デフォルトの名無しさん
22/10/31 16:02:58.05 I3dWRJ7/0.net
(-m) % n がマイナスの余りになるという仕様になっているのはなぜですか？
((-m) % n) + n とするのが面倒です。

309:デフォルトの名無しさん
22/10/31 16:03:27.21 cNn+NHKm0.net
>>288,299,300 が同一人物だとしたら、そのレベルならあらゆるミスをしそうだし、原因はなんともかんとも
愚直で応えるコードを書いてもバグらせそうだし、他の人がACしたコードと比べてみるのがいいんじゃないか・・・

310:デフォルトの名無しさん
22/10/31 16:27:35.89 4XZxl/4jM.net
WAの原因なんてオーバーフロー以外にも無数にあるぞ
バグ、mod取り忘れ、コーナーケース、そもそも解法が間違ってる、等

311:デフォルトの名無しさん
22/10/31 16:34:07.66 yghxSU5fd.net
>>308
C++の整数型は(m/n)*n + m%n == mが成り立つことになっていて、除算は0方向に丸めることが規定されているからです（C++11以降）
modintがおすすめ

312:デフォルトの名無しさん
22/10/31 17:50:46.88 lvkiQp2cM.net
標準的な型の演算規則ぐらいは身に染み付いてた方が良いと思うので、modintなしで地雷踏み尽くして覚えていくのもありではある

313:デフォルトの名無しさん
22/10/31 18:15:49.14 hz0WOit40.net
競プロって意味ないって言われてるけどどうなんだろうね？俺は楽しいからやってるけど
確かにこのアルゴリズムを直接的に実務で使うことはあまりないかもしれないけど、バグの発見とかは競プロで鍛えると速くなる気はしてる

314:デフォルトの名無しさん
22/10/31 18:22:42.24 cNn+NHKm0.net
まあ高校の数学と同程度には役に立つよ
ようするにめったに使わないし、そんな知識を活用せずに大成功してるひとのほうが多いくらい

315:デフォルトの名無しさん
22/10/31 19:21:20.60 sCpxrilS0.net
脳トレが出来るオンラインゲームみたいなもんだし実生活に役立ったら美味しいくらいの気持ちで良さそう

316:デフォルトの名無しさん
22/10/31 19:28:31.38 GYR048690.net
ABCのD問題までスムーズに解けたらあとは趣味程度に思った方がいいと思うよ
逆にD問題までスムーズに通せるようになることで、ある言語で手早くスクラッチする力や計算量を意識する力はかなり身につくと思う

317:デフォルトの名無しさん
22/10/31 19:36:01.13 GYR048690.net
あと、アルゴリズムに興味を持つきっかけになるかな
スタックがLIFOでキューがFIFOだとか基礎教養でやったとき、正直つまらない暗記対象としか思ってなかったけど、ちゃんと意味があって重要だということが分かった
SQLでB木使うとかも競プロやらなかったら意識しなかっただろうし
ハマる人とっては情報科学の入口として優秀じゃないかな、競プロと相性悪い人はストレートに勉強した方がいいんだろうけど

318:デフォルトの名無しさん
22/10/31 19:48:50.64 cNn+NHKm0.net
>>317
おれは先に業務してから競プロやってるけど、RDBでB木使うとかは最初からめっちゃ意識してたぞ
インデックス効かないクエリを実行すると遅すぎてすぐ障害になるからな
そんでRDBだけでは実装が難しすぎる機能とかあったりするから、他のデータ構造も学ぶようになった
競プロはほとんどのひとはすぐ挫折して継続できないみたいだし、どっちのほうが良いかと言うと難しい

319:デフォルトの名無しさん
22/10/31 20:01:16.37 GYR048690.net
>>318
そこは人や環境によるところかな
自分はデータ分析職やってるけど、エンジニア職ではないせいか、ちゃんと理解してる人、意識してる人が少ない
役に立つのに、低レイヤーに触れる文化がないから、自発的にアルゴ勉強する発想が出にくい
あと競プロに相性いいのは、情報系に向いてる人というよりも、元々中受算数か高校数学、高校物理みたいなのがめちゃくちゃ好きとか数オリ経験者みたいなタイプだろうね

320:デフォルトの名無しさん
22/10/31 20:18:35.23 gsksQcSqM.net
割と役に立つこと多いけど数論だけは未だに活用できた試しがない

321:デフォルトの名無しさん
22/10/31 20:32:10.84 GYR048690.net
純粋な離散数学や暗号理論も守備範囲にいれたいとすると、数論みたいな普通のエンジニアリングやデータ解析の範疇じゃ役立てるのが難しい内容も扱いうる
今の競プロの源流のICPCや情オリも、そもそもアカデミックな動機付けでやってるものだし

322:デフォルトの名無しさん
22/10/31 20:42:28.12 Z4/NCeJU0.net
競プロ初心者でコーダーの俺
こっちの業務の役には立たないと思ってる
情報処理の資格を無駄に取得して給料アップ程度
競プロ面では、素直に実装してTLE連発
こんなガチガチに実装したら仕様変更に耐えられないだろうな
と思いながらAC取りにいく

323:デフォルトの名無しさん
22/10/31 20:47:49.35 A5R63J6ka.net
話題乗り遅れたけど、rustなら x.rem_euclid(m) で余りが常に正になる
みんなrust使おう

324:デフォルトの名無しさん
22/10/31 21:29:59.58 Bx4EQ6sc0.net
ライブラリってデータ構造やアルゴリズムばかり気にしがちだけども細々としたutil系もあると便利よね

325:デフォルトの名無しさん
22/10/31 22:05:33.73 sD6lQxmdM.net
>>315
俺も同じような感じだわ。
脳トレで思ったんだけど、脳の老化防止に競技プログラミング!!
とか言って高齢者にプログラム教えたら面白いかもな。
大半はダメポだろうけど、何百人に一人は才能開花しそう。

326:デフォルトの名無しさん
22/10/31 22:09:17.19 XbU49FdB0.net
util系って例えばどういうの？

327:デフォルトの名無しさん
22/10/31 23:44:45.25 zCtN4VnKM.net
新しいFizzBazz発見した
面白いように誰もコード書けない
回答見せるとみんな悔しそうな顔をするｗ

328:デフォルトの名無しさん
22/11/01 00:19:04.44 szeLN5iaa.net
はいはい、すごいねー

329:デフォルトの名無しさん
22/11/01 02:22:23.21 SlcyotAo0.net
面接落ちまくりなので、緑で役に立つ宣伝文句教えてほしいわ（´・ω…:.;::..

330:デフォルトの名無しさん
22/11/01 07:51:58.39 3hzoyxz90.net
青でWeb系の就活したけど、競プロだけのアピールはあまり刺さらなかった印象
「自分のレートは上位3%です！」って言っても、はいはいすごいねーって感じだった
Webアプリを作って、見せるようにしたら多少ウケるようになった
いきなりゴリゴリのWebアプリを作るのは難しいから、例えば、競プロでよくあるグラフの入力をペーストすると、
巡回セールスマン問題を解いて、経路を描画してくれるみたいな、そういうアプリを作って、面接で見せれば、
「愚直にやるとO(N!)なんですけど、動的計画法を使うとO(2^N*N)で解けて嬉しいんですよ〜」
みたいなアルゴリズムの能力も見せれて、良いと思うよ

331:デフォルトの名無しさん
22/11/01 09:07:49.45 CMvcSOEo0.net
未経験からウェブ系へ転職するなら、Ruby on Rails 一択
YouTube で有名な雑食系エンジニア・KENTA や、RUNTEQ の動画を見ればよい。
KENTAのRailsサロンとか、くろかわこうへいのAWS サロンも良い
理系や競技プログラミングの知識などは、いらない。
文系で、英語・算数だけで十分
Linux, Docker, AWS、データベースなどは必須。
AWS Solution Architect も欲しい

332:デフォルトの名無しさん
22/11/01 09:30:51.55 QXtVoCESM.net
青くらいで競プロアピールしてくるのは地雷臭しかねえ

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

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

335:デフォルトの名無しさん
22/11/01 11:31:09.90 YpP1+3gDM.net
>>333
むしろその通りだから地雷なのよ

336:デフォルトの名無しさん
22/11/01 11:35:22.17 YpP1+3gDM.net
- 競プロ、まあ一応水色ですけど他に専門分野/強みあります
- ガチで競技として取り組んでててICPCメダリストです
アピールするならどっちかのスタンスだと思ってて青で下のパターンで来るやつがいてヤバいという話ね

337:デフォルトの名無しさん
22/11/01 11:35:51.24 DmCKRmd0M.net
壮大な取り違えをしててすまんが、青は高すぎて微妙って話か？
いや、まあ高すぎるってほどでもないだろ、って感覚だけど

338:デフォルトの名無しさん
22/11/01 11:38:35.93 DmCKRmd0M.net
>>336
理解したわ
そりゃ青の適切な使い方は上だし、メインウェポンに据えてるやつはヤバいだろう

339:デフォルトの名無しさん
22/11/01 11:47:34.29 qfAT5wFeM.net
>>338
でもそういう人特にjobs経由だと相当数いて競プロの評判落としてる気がするのよね
企業からしたらjobsは求人サイトの1つでしかないのにレート条件満たしてたらいけるやろと勘違いしてる的な

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

341:デフォルトの名無しさん
22/11/01 12:09:33.52 mxpwEOaI0.net
競プロある程度強いって堂々と言えるのはやっぱり黄色くらいから？
そりゃ橙赤の人から見ればまだまだだろうけどABC対象外にはなるし

342:デフォルトの名無しさん
22/11/01 12:12:20.53 1IoQMX7D0.net
>>330
競プロって見た目地味だし何がすごいのか横から見てよくわからないのが課題だから、可視化するのは効きそう
N^3をNlogNまで落とした←ほーん、で？
N=1e5だと6億倍の高速化←お？
目に見えるようにするとこれだけ速くなっている←おお！
ぐらいの印象の差が出るんじゃないかと思う

343:デフォルトの名無しさん
22/11/01 12:20:49.62 1IoQMX7D0.net
>>341
業界に競プロerがそんなにいなければ、青ぐらいでも強いと言っていいレベルだと思うかなあ
そういうところではむしろ競プロ自体がどうすごいのか伝えるのが課題になってくる
競プロerがたくさんいる企業だとすると、その人たちのレベル感次第では黄色も「頑張ってる」ぐらいの表現で留めた方がいいかもね
赤はさすがに無条件で強いと言っていい気がするけど

344:デフォルトの名無しさん
22/11/01 12:22:10.63 1IoQMX7D0.net
黄色が強い方にならない企業ってよほど限られたところだとも思うけど

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

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

347:デフォルトの名無しさん
22/11/01 12:38:40.95 DmCKRmd0M.net
まあ、仮に赤あってもほとんどの場合サブウェポンには変わらんと思うぞ

348:デフォルトの名無しさん
22/11/01 14:45:32.58 9QgByuPW0.net
黄色だけどそんな就活の役には立たんかったぞ
それよりは他に普通の開発経験を持ってて、その中で競プロをどう活かしたかの方がウケは良い
が、大抵はチーム開発経験を聞いてきて、そっちが弱いと露骨に微妙な表情するんだよな……あと最終面接で落ちる

349:デフォルトの名無しさん
22/11/01 16:21:29.40 J8SPAQYO0.net
ヒューリスティックの実績メインで採用されてるのは結構見るようになったけどね

350:デフォルトの名無しさん
22/11/01 18:54:40.62 6rlYl9tyM.net
いくらアルゴリズムに強くても即戦力から遠いからな
普通に自作した小規模の趣味のwebサイト運営してますみたいなパンチはない

351:デフォルトの名無しさん
22/11/01 18:57:26.58 6rlYl9tyM.net
webサイトを立ち上げられる　& ノウハウを持っている
セキュリティ意識が高い&ノウハウがある　←　これが一番大事
競プロ出来てもまともにクラスも書けない人
いらんわな～

352:デフォルトの名無しさん
22/11/01 19:11:55.23 mxpwEOaI0.net
CTFとかkaggle辺りでの実績ってどういう評価になるんだろう

353:デフォルトの名無しさん
22/11/02 14:13:37.34 Ea2TYzYwM.net
組合せ最適化第6版の和訳が出るぜ

354:デフォルトの名無しさん
22/11/02 18:02:49.90 9x8rFS7h0.net
URLﾘﾝｸ(github.com)
ガウス整数環での素因数分解
A+Biとしたときに|A|,|B| <= 10^9でも十分高速でできる
数論の知識が豊富なら再発明は困難でもなさそう、ABC-Gぐらいの問題っぽい？ARC/AGCタイプではない
結構知識を使うので考える過程でいろいろ勉強になった

355:デフォルトの名無しさん
22/11/02 18:08:47.53 9x8rFS7h0.net
コルテ和訳助かると思いつつも、17600円となかなか高い
第2版が値下がりしたりしないかな

356:デフォルトの名無しさん
22/11/02 19:34:08.80 eB36Kp3k0.net
コルテの本は競技プログラミングに役に立ちますか？

357:デフォルトの名無しさん
22/11/02 19:34:56.79 utiJQzSa0.net
役に立ちます

358:デフォルトの名無しさん
22/11/02 19:39:08.78 eB36Kp3k0.net
>>357
ありがとうございます。
高度な本で競技プログラミングにも役に立つというのはいいですね。
高度な内容を理解するのが主目的で、おまけとして競技プログラミングも強くなる。

359:デフォルトの名無しさん
22/11/02 21:32:43.80 AEY2Eek10.net
そうです

360:デフォルトの名無しさん
22/11/03 17:08:06.46 B0vR84k9M.net
昔のARCの問題は正直今のARCの練習には微妙な気がするな
何が一番近いんだ

361:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa9d-wg3e)
22/11/04 10:20:19.80 0KQ7LFlsa.net
数ヶ月触って思ったけど競プロって実際の開発には結びつかんね
まぁ割りと勉強的には面白いからいいけど

362:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa9d-ww+g)
22/11/04 10:56:39.54 B7tR4FmYa.net
俺はライブラリとか便利ツール作る過程で色々学んだけど元々開発経験ある人だと逆にそういうことはないか

363:デフォルトの名無しさん
22/11/05 00:18:45.61 lGny4UBo0.net
ARCも昔（3年程度前）の問題やってるとdiff一色分ぐらい今より高く評価されている印象だから、昔の問題解くんなら自分のレート+400～+800ぐらいの問題解いてるとちょうどいい思考練習になると思う

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

365:デフォルトの名無しさん
22/11/05 11:34:34.69 yYAK326QM.net
Qiitaに珍しくいい記事があったとしてその人を雇いたいと思えるか？
競プロのレートなんてそれ以下なんだな

366:デフォルトの名無しさん
22/11/05 14:54:25.86 NDP89GFMM.net
>>363
diffの基準が違うと感じることはもちろんあるが、もっと根本的に問題の傾向変わってないか？
writerの差か

367:デフォルトの名無しさん
22/11/05 20:59:06.56 jsvJjD9T0.net
さあ、緑をめざすぞ
茶色到達したってことは4完以外だとレート下がるんだろうか

368:デフォルトの名無しさん
22/11/05 22:41:58.78 OHaBQZ4Ia.net
Qiitaで記事書いてるのは社内ドキュメントとか残してくれそうで歓迎

369:デフォルトの名無しさん
22/11/05 22:42:19.35 QlP7W/960.net
いや、一個前の順列とか知らんし、Dはiが2,3番めだと思ってた。酷いｗｗ
下手したら２完だたｗｗｗ
検索しても全然出てこないからB問題まで解ければ十分だの

370:デフォルトの名無しさん
22/11/05 22:43:11.47 qDrbvCBh0.net
Cムズすぎる🥲

371:デフォルトの名無しさん
22/11/05 22:43:16.24 zoo2KB540.net
久しぶりに順調に6完できた…

372:デフォルトの名無しさん
22/11/05 22:45:59.83 H7jWLgxi0.net
C問題は、C++ならライブラリ使えるから簡単すぎるけど、ライブラリ使わない前提とすると、C問題にしてはかなり難しいような

373:デフォルトの名無しさん
22/11/05 22:47:11.30 rFNV3e/H0.net
クソインフレおもんねーわ
結局ガキの頃から脳みそ鍛えてないとｃとかで時間とけて終わるな
ワイのレートは頭打ちや

374:デフォルトの名無しさん
22/11/05 22:49:20.41 UBpIFpTC0.net
F問題方針合ってたのにBITも有理数用のライブラリも作ってないせいで実装間に合わなかったけどやっぱり作っておくべきか
三連続で有理数ライブラリ使える問題出題されてるし

375:デフォルトの名無しさん
22/11/05 22:53:52.95 H7jWLgxi0.net
>>374
BITと逆元使うだけじゃん
そんなもん理屈わかってれば実装簡単なのに何を言い訳してるのやら

376:デフォルトの名無しさん
22/11/05 22:57:52.72 nR4yZihTd.net
この難易度4完で3000位以下って…
しんどいよぉ

377:デフォルトの名無しさん
22/11/05 23:08:34.55 8c74vvij0.net
Cわりと簡単に解けたけど証明できなかったから提出するとき一番ドキドキしたw

378:デフォルトの名無しさん
22/11/05 23:12:16.55 lGny4UBo0.net
これ意外と非自明な事実かもしれないから書くけど、有理数をmodとって整数で表せって問題は徹頭徹尾有理数を使わないで正しい答えを出せる

379:デフォルトの名無しさん
22/11/05 23:14:04.30 lGny4UBo0.net
一応、素数modであることが必要かな？

380:デフォルトの名無しさん
22/11/05 23:16:02.54 lGny4UBo0.net
>>372
ライブラリなしなら結構頭使う方かもね
ARC-Aとかにありそう
ライブラリ前提の問題として配置したんだとするとちょっと微妙な気がするなあ

381:デフォルトの名無しさん
22/11/05 23:17:34.26 8c74vvij0.net
>>380
お前らC++使えよ？っていうちょくからのお達しだろうな

382:デフォルトの名無しさん
22/11/05 23:24:55.55 UBpIFpTC0.net
>>375
その二つ自体はそうなんだけど、分母はK^2になるから分子の情報だけ持てば良いっていうのを見落としてたせいで有理数の四則演算をしようとして実装が大変なことになったんだよね
初心者ですまん

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

384:デフォルトの名無しさん
22/11/05 23:35:04.99 qDrbvCBh0.net
30半ばのおっさんなんだけど初めて数ヶ月、C問題が解けたことが今まで数えるほどしかない(´・ω・｀)
お前ら天才すぎだろ

385:デフォルトの名無しさん
22/11/05 23:38:00.58 tb67Nevqr.net
こんなん安倍晋三でも全完出来るだろ

386:デフォルトの名無しさん
22/11/05 23:38:56.42 8c74vvij0.net
全完9人しかおらんやないかーい(´・ω・`)

387:デフォルトの名無しさん
22/11/05 23:39:37.36 QbgxJiUMa.net
最近c問題むずいね
以前はdiff 200くらいが目安いうてた気がするけど

388:デフォルトの名無しさん
22/11/05 23:41:52.73 h/XOIx4p0.net
紙に(1,2,3,4,5)の順列でも書き出してにらんでれば規則性がわかるだろ

389:デフォルトの名無しさん
22/11/05 23:46:13.55 lGny4UBo0.net
Cは普通にむずいと思うよ
進学校で高校数学まともに勉強してた層の中の上の方がコミュニティ作ってるから基準歪んでるけど
競技と言いながらあまり相対評価に囚われちゃいけないタイプの娯楽

390:デフォルトの名無しさん
22/11/05 23:46:43.80 QbgxJiUMa.net
まあサンプルが親切だったね
出力例2を眺めてたらわかった

391:デフォルトの名無しさん
22/11/05 23:47:47.38 8c74vvij0.net
というかコドフォdiv2のA,Bあたりによくある実験してたら規則性が見えてくるやつだからまあ妥当なんじゃないですかね(証明できるとは言ってない)

392:デフォルトの名無しさん
22/11/05 23:52:24.78 lGny4UBo0.net
Gは形式的べき級数で楽しようとして負の二項定理？っぽいところで詰まってしまったから、これも覚えておこう

393:デフォルトの名無しさん
22/11/05 23:57:57.35 H7jWLgxi0.net
>>383
たしかに1000ビットとかくらいの整数の演算を要求してたまにはC++erを殺してほしい

394:デフォルトの名無しさん
22/11/06 00:38:46.41 b6AZTKz70.net
>>384
30歳すぎたら酒飲んだりなんか食べながら気軽にやるのが吉

395:デフォルトの名無しさん
22/11/06 01:50:28.89 zmPGsgdt0.net
今回のE問題みたいなやつで、解説でDFSじゃなくてBFSが書かれてるのなんで？
最短経路が不要ならDFSでいいと思うんだけど

396:デフォルトの名無しさん
22/11/06 01:54:17.29 TnuCg6gk0.net
競プロ力ってWebとかシステムってよりかはゲームとかの方向な気がする。

397:デフォルトの名無しさん
22/11/06 10:05:08.85 BVrdb9YXM.net
>>395

398:デフォルトの名無しさん
22/11/06 10:53:13.10 v6GSz7hT0.net
DFSでもいいと思うよ
人によるけど、BFSの方が実装しやすいだけ
Pythonなど一部の言語だと、再設定しない限りDFSでは再帰上限でREになるから解説に書きづらいというのもある

399:デフォルトの名無しさん
22/11/06 11:08:07.55 PIbDNXM80.net
本当にどっちでもいいんだけど、おれもこういうときはなんとなくBFSで実装するようになってきたな
そもそも競プロの探索問題だと、DFSよりBFSを利用することのほうが多くて、BFSが手癖になってきたかな

400:デフォルトの名無しさん
22/11/06 12:52:40.41 HsT3tnctM.net
昨日のEx、F2行列操作の高速化か
こういう細々としたテク、ライブラリ化サボっちゃうしコンテスト中に思い出せる瞬発力もないんだよなあ

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

402:デフォルトの名無しさん
22/11/06 14:32:15.66 DHDxR9FJ0.net
DFSのが書きやすいと思うけど、確かに再帰って言語によって計算コストに癖があるからDFSよりもBFSの方が安定なのかもね
10^6のサイズのグリッドで2次元配列使うから、遅い言語だとやや定数倍気をつけないといけないタイプ

403:デフォルトの名無しさん
22/11/06 14:45:26.72 4JagSJ3R0.net
BFSはキューを使います。
DFSは再帰を使わない場合スタックを使います。
再帰を使わないとして、BFSのほうがDFSよりも実装が簡単ですか？

404:デフォルトの名無しさん
22/11/06 14:49:15.37 5xyAMfxFd.net
同じです

405:デフォルトの名無しさん
22/11/06 15:12:24.54 ehumOJCyM.net
今回みたいにただ連結判定するだけならBFSもDFSも同じようなもんだけど、木DPでやるような再帰を活かした+αの処理を非再帰化してスタックで実現しようとするとややめんどい

406:デフォルトの名無しさん
22/11/06 16:02:50.42 v6GSz7hT0.net
JavaだとDequeとQueueはあるがStackは古の非推奨クラスなのでBFSの方が楽

407:デフォルトの名無しさん
22/11/06 16:24:36.10 KxwCQXYpa.net
別解なんていくらでもあるんだから、BFSとDFSの差くらいで
「なんでこっちの解法じゃないの？」なんて悩んでたらすごく楽しいことになるぞ！

408:デフォルトの名無しさん
22/11/06 16:46:02.52 zmPGsgdt0.net
Dequeはスタックとしても使えるのでは

409:デフォルトの名無しさん
22/11/06 19:54:28.41 vwCXiH6d0.net
どっちみちお尻から取ってくるか前から取ってくるかの違いじゃろい

410:デフォルトの名無しさん
22/11/07 22:41:09.69 +urCymrW0.net
今日本語圏で一番知見が集積しているのってLibrary Checkerかな
英語圏、ロシア語圏、中国語圏に似たようなものはあるんだろうか

411:デフォルトの名無しさん
22/11/07 23:20:15.29 qKvylSc10.net
中国語やロシア語には競プロで使うやたらマニアックなアルゴリズムをまとめたページあるよ

412:デフォルトの名無しさん
22/11/08 16:11:47.32 g3rYetvfM.net
中国の方はまとめた辞典みたいなサイトがあったよな
前スレにあった気がする
ロシアの方は知らないんだけど、どんなやつ？

413:デフォルトの名無しさん
22/11/08 16:12:34.40 g3rYetvfM.net
しかし、赤diffとか解いてる感じでもARCは昔の方が簡単な気しかしないんだが、割と違う意見あるんだな

414:デフォルトの名無しさん
22/11/09 11:07:25.04 HMRJ6E6Wa.net
赤になりやすくなったという文脈であれば問題の難易度とはまた別の話だけどな

415:デフォルトの名無しさん
22/11/09 14:15:51.41 HotMmDzmM.net
あるdiff帯に限定して問題を抽出するとすれば、その難易度はそれぞれの問題の出題時期におけるそのレート帯への到達難易度と大体相関するやろ

416:デフォルトの名無しさん
22/11/09 15:00:23.18 PM/H7abua.net
時代とともに同じdiff帯の問題の難易度が徐々に上がるのは当たり前で、だからといってある色への到達難易度が上がるわけではない、環境だって変わってるんだから

417:デフォルトの名無しさん
22/11/09 15:23:24.57 HotMmDzmM.net
それは同じ傾向の典型問題がずっと出題され続けている場合に適用できる話だが、ARCは傾向が変わっているわけでそうとも言えない
ARCの昔の問題は今となっては典型となっているので、簡単に感じる、という話なら分かるんだが、どうも昔の方がアドホックで難しいと考えている人がいるのが自分の感覚だと意外だったってことが元々言いたかったことだな

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

419:デフォルトの名無しさん
22/11/09 16:48:50.58 oxPO+/FNa.net
> 昔の方がアドホックで難しいと考えている人がいる
これは俺も同意できないけどソース何？まあ言いたくなければ別にいいけど

420:デフォルトの名無しさん
22/11/10 21:53:35.79 YS4V/v0d0.net
ICPC終わったね
MIT強いな
PurdueとSwarthmoreもそれなりの順位につけてるし、アメリカ結構来てる？

421:デフォルトの名無しさん
22/11/10 21:57:56.30 YS4V/v0d0.net
ARCが昔と今でアドホックさに変化があるという印象はなくて、これもどちらかというとwriter依存な気がする
少し前のmaroon回はアドホックだったようなイメージ

422:デフォルトの名無しさん
22/11/10 23:05:12.88 YS4V/v0d0.net
というかカーネギーメロン大学も強いな

423:デフォルトの名無しさん
22/11/10 23:13:57.97 6CBRVknNa.net
ARCは難易度もアドホックさも時期によってばらばらなイメージある

424:デフォルトの名無しさん
22/11/11 00:03:33.94 mxUE2nf8a.net
MITってMYDのワンマンチームかと思ってたから意外や

425:デフォルトの名無しさん
22/11/11 01:28:27.41 eYUvrs+I0.net
Benqが次出るときどういうチームになるのか気になるわ

426:デフォルトの名無しさん (ｽｯｯﾌﾟ Sdb2-5krx)
22/11/11 11:36:15.83 Y094P/2Zd.net
CTFを勉強しようと以前アカウント作ったんだけど、難し過ぎてpicoCTFからやってたら最初のサイトを忘れた。。。
アカウント申請にもサイトを解析しないとダメでそれはクリアしてアカウント作ったんだけどどこか分かる？

427:デフォルトの名無しさん
22/11/11 18:24:09.39 Y094P/2Zd.net
>>426
HackTheBoxでした。
スレ汚しすいません。

428:デフォルトの名無しさん
22/11/11 19:04:07.17 LHlViBaLM.net
数列AのLCMを10^9+7のmodで取る問題が有るんだけど、
答えが合わないのは
gcd(l, Ai)とgcd(l % 10^9+7, Ai)は異なるということ？
って自分で確かめれるか。
家帰ったら確かめよ

429:デフォルトの名無しさん
22/11/11 19:24:41.27 zSld6sc8r.net
じゃあレスすんな

430:デフォルトの名無しさん
22/11/11 19:39:51.72 yEEY46ODp.net
ツッコミどころが多すぎるけど例えばl=10^9+8の場合とかを考えてみればすぐ分かるしそのレベルだと高校数学の復習をしてからの方が成長出来そう

431:デフォルトの名無しさん
22/11/11 22:17:47.19 zKcuQYM10.net
gcd(1,2)=1
gcd(1+10^9+7,2)=2

432:デフォルトの名無しさん
22/11/11 22:20:21.87 zKcuQYM10.net
しかし、その部分でひっかけ？をするのと多倍長整数扱わせたい以外の意図を感じない珍しい問題だ

433:デフォルトの名無しさん
22/11/11 22:24:57.86 zKcuQYM10.net
整数をZ/pZで扱うのは一種のハッシュ化だけど、gcdやlcmみたいな数論的性質がうまいこと保存されるハッシュ化ってなんかあるんかね

434:デフォルトの名無しさん
22/11/11 22:49:25.23 hYHvcPylM.net
ふと思ったんだけど、競技プログラミングってすぐに結果が出るじゃん。
だから、出来た!!って達成感がすぐに味わえる。
それに対して、何かをつくるってすごく時間かかるから
達成感を感じるまでにすごく時間がかかる。
FFS理論の拡散性/保存性と関係ありそうだなって感じた。
FFS理論については俺もよくわかんないんで説明しないけど
競技プログラミング好きは拡散性が高く
何かをコツコツ作るのが好きな人は保全性が高い見ないな。

435:デフォルトの名無しさん
22/11/11 23:06:55.29 zKcuQYM10.net
それはあるだろうね
FFS理論はよく知らないけど、自分は刺激がないと興味関心の対象がすぐ移るから、結果やフィードバックがすぐ返ってくる競プロが性にあう

436:デフォルトの名無しさん
22/11/11 23:35:15.66 zKcuQYM10.net
>>432
というかこれおそらくだけどN<=10^5, A_i<=10^9とかで素因数分解させて素数ごとに指数max取らせるのが想定解みたいな問題だろうから、なんかすごい的外れなこと言ってたわ

437:デフォルトの名無しさん
22/11/11 23:40:03.89 zKcuQYM10.net
レベル感的にはA_i<=10^5の方がそれっぽいか

438:デフォルトの名無しさん
22/11/12 19:57:29.12 qQOJrpEK0.net
競技プログラミングの鉄則の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;
// 出勤時刻には人数が１人増える
diffList[L]++;
// 退勤時には人数が１人減る
diffList[R]--;
}
// 各時刻の働いている人合計を出力する
int total = 0;
for(int i = 0; i < T; i++) {
total += diffList[i];
cout << total << endl;
}
return 0;
}

439:デフォルトの名無しさん
22/11/12 20:20:29.60 w7+UUAs6a.net
>>438
配列初期化してなくね
真面目に初期化するかグローバルに置くか static つけるか std::vector 使う（オススメ）か

440:デフォルトの名無しさん
22/11/12 20:31:37.25 qQOJrpEK0.net
>>439
配列のみグローバル領域に置いたら正解になりました！！
ありがとうございました！！

441:デフォルトの名無しさん
22/11/12 22:41:09.26 hWyV6Jgk0.net
5完
F,G無理無理無理

442:デフォルトの名無しさん
22/11/12 22:41:38.34 zPldldpV0.net
DのWAが１時間以上もとれない、コンテスト難しくなりすぎ・・・

443:デフォルトの名無しさん
22/11/12 22:41:46.87 YH4Xhy0P0.net
またCとけんかった
自分ではいけたと思ったのに(´・ω・｀)

444:デフォルトの名無しさん
22/11/12 22:43:20.71 /nvO95//p.net
EとFGで崖ある回キツいわ
Dでバグって2WAした時点で追いつける可能性が大幅に減って困ってた

445:デフォルトの名無しさん
22/11/12 22:44:23.30 /nvO95//p.net
Aの傾向の変わり具合もそうだけど今日のCって少し前ならDにあってもおかしくない気がするしインフレしてるんだな

446:デフォルトの名無しさん
22/11/12 22:44:29.50 I+5LPno20.net
競プロ初心者だが、D問題とけなかった。
長くなるが次のコードの何がいけないのか教えてほしい

447:デフォルトの名無しさん
22/11/12 22:46:35.73 I+5LPno20.net
2回に分ける
n, m = list(map(int, input().split(" ")))
t = {}
origin = list(map(int, input().split(" ")))
sums = sum(origin)
numbers = set()
for i in origin:
if i in t:
t[i] += 1
else:
t[i] = 1
numbers.add(i)
numbers = list(numbers)
numbers.sort()
numbers += numbers
start = 0
goal = -1
now_max = -1
now_sums = 0
last = None

448:デフォルトの名無しさん
22/11/12 22:46:51.30 I+5LPno20.net
while True:
goal += 1
if goal >= len(numbers):
break
if start is not None and goal - start + 1 > n:
break
mod_m = numbers[goal] % m
if last is None:
start = goal
now_sums = mod_m * t[mod_m]
last = mod_m
elif (last + 1) % m != mod_m:
last = mod_m
now_max = max(now_sums, now_max)
start = goal
now_sums = mod_m * t[mod_m]
else:
now_sums += mod_m * t[mod_m]
last = mod_m
now_max = max(now_sums, now_max)
print(sums - now_max)

449:デフォルトの名無しさん
22/11/12 22:55:47.75 I+5LPno20.net
見づらいですね。
画像にしました。
URLﾘﾝｸ(imgur.com)

450:デフォルトの名無しさん
22/11/12 22:58:40.53 JScHu7j6a.net
アカウント知られることに抵抗がないなら提出ページのリンク貼った方が見やすいと思うよ
こんな感じに
URLﾘﾝｸ(atcoder.jp)

451:デフォルトの名無しさん
22/11/12 23:01:52.30 I+5LPno20.net
>>450
ですね。サンクス
URLﾘﾝｸ(atcoder.jp)
こちらになります。

452:デフォルトの名無しさん
22/11/12 23:11:22.38 5N6IETenp.net
>>451
コード全然見てないから見当違いかもしれないけど、自分も殆ど同じテストケースでWAが出てソート済みの数列が全て差分1以内で連続してるパターン(0 1 2 3 4的な)でのミスが原因だったからこのパターンにも対応出来るようにしたらACになるかもしれない

453:デフォルトの名無しさん
22/11/12 23:12:37.19 Q3K7r3oy0.net
>>449
0からM-1が全部埋まってるときにバグる
あとnow_max = max(now_sums, now_max)のインデントがズレて更新がおこなわれていないとか？

454:デフォルトの名無しさん
22/11/12 23:16:22.82 t/mF+2MTa.net
cもdも座圧unionfind で芸のない出題だなと思いました

455:デフォルトの名無しさん
22/11/12 23:18:14.12 Q3K7r3oy0.net
あーDはunionfindでもできるね
そっちの方が実装方針としては楽かも

456:デフォルトの名無しさん
22/11/12 23:25:56.09 Q3K7r3oy0.net
ABC-Eってかなりの頻度で頂点を増やして最短経路問題を解く形の問題が出てる気がするね

457:デフォルトの名無しさん
22/11/12 23:28:46.84 I+5LPno20.net
>>452-453
サンクス
ああああ・・・なるほど
if start is not None and goal - start + 1 > n:
⇒
if start is not None and goal - start + 1 > m:
にしたら通った。。。悔しい。。

458:デフォルトの名無しさん
22/11/12 23:30:43.24 Q3K7r3oy0.net
>>453
よくみたらnow_max = max(now_sums, now_max)の更新はloop中でちゃんと行われてるね
失礼

459:デフォルトの名無しさん
22/11/12 23:32:16.43 mGgFo0mYr.net
33にもなってこんな連投してんのか

460:デフォルトの名無しさん
22/11/12 23:32:41.23 I+5LPno20.net
D問題、公式解説でO(NlogN)で実行できるって書いてたけど
自分の実装もそうだけどO(N)でできるんじゃないのかな。

461:デフォルトの名無しさん
22/11/12 23:33:21.48 I+5LPno20.net
>>459
IT初心者で夢中になってるので、すみません。。

462:デフォルトの名無しさん
22/11/12 23:33:43.49 1KGF598jM.net
2-SATとproject selectionってやっぱ似てるよなと最近思う

463:デフォルトの名無しさん
22/11/12 23:38:09.22 Q3K7r3oy0.net
座圧でソートが必要なときと必要じゃないときがあるけど、そこがボトルネックで死ぬことは少ないので、あまり気にされるタイミングがない

464:デフォルトの名無しさん
22/11/12 23:42:34.37 1KGF598jM.net
むしろジジイもキッズも連投しまくれ

465:デフォルトの名無しさん
22/11/12 23:54:16.97 Q3K7r3oy0.net
Ex、ARCで中盤で出てもおかしくない問題がちょくちょくある気がするけど、ABCで出ちゃったからARCでは一年ぐらいは出なそうだな感もある

466:デフォルトの名無しさん
22/11/13 00:09:53.81 LlAfmRCW0.net
Fが水色くらいになるようにしてほしいですね

467:デフォルトの名無しさん
22/11/13 00:17:24.95 vtTojVNy0.net
Fは青ぐらいがよくない？

468:デフォルトの名無しさん
22/11/13 00:23:17.33 G1i+6cdf0.net
EとFを同じ配点にするなら、同じdiffを目指してほしい

469:デフォルトの名無しさん
22/11/13 00:36:57.60 vtTojVNy0.net
それも一理あるけど、GとExは同配点ながら明らかに難易度差があるような作りになってるし、配点と難易度を一致させることがマストとは考えられていないと思う
そもそも広く競プロを見れば点数がなくて完数で評価するコンテストもあるし
個人的にはB～Gで灰から黄まで一色ずつ出現するぐらいが丁度いいABCかなあと思っている

470:デフォルトの名無しさん
22/11/13 02:01:31.35 tLYo0hkG0.net
DE緑でFG橙は流石に崖が過ぎる

471:デフォルトの名無しさん
22/11/13 08:36:37.58 2N/MD+QP0.net
Fは青黄でも十分に解ける問題だった

472:デフォルトの名無しさん
22/11/13 13:29:16.33 4fDbpPNMM.net
Fは個々のステップ自体は難しくないから素直にやれば青でもできるものだと思うが、橙diff出た要因はなんだろうな
TLが若干厳しかったのが効いてるんだろうか

473:デフォルトの名無しさん
22/11/13 13:45:12.57 2N/MD+QP0.net
自分はすぬけ君の地下鉄旅行を思い出すのに時間がかかって間に合わなかった

474:デフォルトの名無しさん
22/11/13 14:19:52.10 4fDbpPNMM.net
確かにハブ的なものを作って辺の数のオーダーを落とすという典型は微妙に有名じゃないのか

475:デフォルトの名無しさん
22/11/13 16:09:21.76 KJPDiKh4M.net
Cの嘘解法、これを思い付くほうが想定解思い付くよりずっと難しいだろみたいなところがあるな

476:デフォルトの名無しさん
22/11/13 16:10:36.90 Iz2kcZDFM.net
Cの嘘解法、これを思い付くほうが想定解思い付くよりずっと難しいだろみたいなところがあるな

477:デフォルトの名無しさん
22/11/16 02:30:47.15 tAWUIRauM.net
httf提出したあ

478:デフォルトの名無しさん
22/11/17 19:51:39.15 g99PYOoPp.net
AGC 生えてるけど冷える気しかしない

479:デフォルトの名無しさん
22/11/17 22:29:51.89 VbMz1/BwM.net
ARCも入ってるし、ICPC終わってエンジンかかってきたな

480:デフォルトの名無しさん
22/11/17 22:32:50.54 UcbbsJ/N0.net
AGCの告知2週間前とかにされるんだな

481:デフォルトの名無しさん
22/11/17 22:56:08.64 rco4UP2C0.net
今年で3回目のAGCか
だいぶ開催数減ってきちゃったね

482:デフォルトの名無しさん
22/11/17 23:01:38.63 jZi3UWjS0.net
一時的なもので外国人に協力してもらえばなんとかなるのか、本当に問題が枯渇してこれからどんどんAGC作問が厳しくなっていくのか気になるところ

483:デフォルトの名無しさん
22/11/17 23:11:25.50 sQR4cXJ3a.net
Agcあとは年末に2回やれば及第点にはなるか

484:デフォルトの名無しさん
22/11/18 04:56:12.51 +gVHkon8p.net
AGCの問題傾向よく分からん

485:デフォルトの名無しさん
22/11/18 15:45:59.95 V2j1PDas0.net
こどふぉdiv.1ははなんだかんだ生えてるがインドは生えなくなったしどこも問題枯渇してるんだろう

486:デフォルトの名無しさん
22/11/19 15:26:42.45 72lFIpVP0.net
opencupとかどういう質の問題が出てくるんだろうね
漏れ出てくる話を見る限り、割と知識バンバン使いそうな印象でAGC的な感じじゃなさそうだけど
AGC的傾向が唯一のものではなくて、そこで問題を食い合ってたら大変だなと

487:デフォルトの名無しさん
22/11/19 16:00:48.74 DFXBsNKGr.net
うんち！

488:デフォルトの名無しさん
22/11/19 16:13:20.32 UeZx7lmP0.net
Dまでにダイクストラを使った問題を2年くらい見てない気がする。やるだけになりがちなので出ない。

489:デフォルトの名無しさん
22/11/19 16:55:11.41 xSVToK+Ip.net
そりゃ直球でダイクストラをやる問題なんて中々出ないでしょ　ダイクストラに一手間加えたものは結構DEくらいで見かける気がするけど

490:デフォルトの名無しさん
22/11/19 17:01:35.33 6DxjUBOFM.net
どのコンテストの話なのかambiguousだ

491:デフォルトの名無しさん (ｱｳｱｳｳｰ Sa3b-yvkW)
22/11/19 21:53:02.57 7vm0czr1a.net
opencupはかなりあらゆる問題が出るし難易度が高すぎて質とかよくわからん

492:デフォルトの名無しさん
22/11/19 22:40:57.03 BGPGelZJ0.net
E問題
やり方思いついたけど時間間に合わんかった
マジで悔しい

493:デフォルトの名無しさん
22/11/19 22:42:42.99 UeZx7lmP0.net
同じく。Dまでが難しく時間かかるから解けそうでも足りない。
問題数増やすなら通りやすくしてほしい。

494:デフォルトの名無しさん
22/11/19 22:42:46.42 ofRg9IP90.net
G無理すぎ

495:デフォルトの名無しさん
22/11/19 22:45:13.42 CljIy5Ck0.net
6完
G真ん中先にとって対称に取れればいいけどそうじゃないときが分からん

496:デフォルトの名無しさん
22/11/19 22:47:01.65 ZOPAbYj+0.net
B問題を読み間違えたのもあるけど一時間使ってしまった😭
Cが定型問題っぽかったのに残念すぎる…

497:デフォルトの名無しさん
22/11/19 22:47:25.31 BGPGelZJ0.net
ちなみに俺が考えたE問題の解き方として
横移動するときに、移動前の列と移動後の列の差分を計算して行くっていうやり方なんだけど
これじゃアウトなんだろうか。300っていう制約があったから計算量的に足りる気がしたのだが

498:デフォルトの名無しさん
22/11/19 22:47:36.14 72lFIpVP0.net
Grundy数と真似っ子の複合でなかなか教育的な問題

499:デフォルトの名無しさん
22/11/19 22:49:01.60 BGPGelZJ0.net
URLﾘﾝｸ(imgur.com)
Dまではノーミスでできた。
緑に近づけていたらいいな

500:デフォルトの名無しさん
22/11/19 22:51:20.76 +5P4fem10.net
Fまではだいぶ素直でABCらしい回だった気がする　
問題文やたら長かったけど

501:デフォルトの名無しさん
22/11/19 22:57:02.19 xSVToK+Ip.net
EとFの難易度が釣り合ってたのも久しぶりな気がするな
数ヶ月前のD辺りに似たような問題あった気がするし逆に置かれてたらFの方が解かれてそう

502:デフォルトの名無しさん
22/11/19 23:06:18.86 72lFIpVP0.net
>>497
ちゃんと実装すればいけるんじゃない？
計算量増やさないようにする縦移動が少しめんどくさいので、二次元累積和の方が実装は簡単な気がする

503:デフォルトの名無しさん
22/11/19 23:06:20.86 BGPGelZJ0.net
ってか競技プロって実務で役立つ説ってどうなんでしょう
atCoder初めてはや３ヶ月だけど、
IT業界２年目で実務で、皆が重いって言ってる内容とか全然重く感じない
競プロによる基礎体力があるからでしょうか（願望）

504:デフォルトの名無しさん
22/11/19 23:07:43.19 72lFIpVP0.net
Fは素直だったね
確かにABC-Fはたまにかなり素直なDPが来る印象

505:デフォルトの名無しさん
22/11/19 23:09:38.17 72lFIpVP0.net
プレッシャーの中で頭使いながら速くコード書く練習してるから基礎体力をつける的な意味では十分役に立つんじゃないの？って思うね

506:デフォルトの名無しさん
22/11/19 23:10:56.74 RF+LxHZd0.net
引退します
URLﾘﾝｸ(i.imgur.com)

507:デフォルトの名無しさん
22/11/19 23:13:26.30 BGPGelZJ0.net
だよね
ただ、それ以外のサーバー知識とかlinux周りとかはやっぱり経験者の方が強いわ
でも、10年以上IT業界にいる人よりもSQLをかけたりするんだよね
こういうのって、職人の世界で言ういわば力持ちで、広く浅い（？）知識もってる人より偉くなりにくいのかね？どうなんだろう

508:デフォルトの名無しさん
22/11/19 23:17:05.43 UeZx7lmP0.net
>>503
BからC問題くらいまで解けるようになる価値はめちゃ高くて最も役に立つ帯域だと思う

509:デフォルトの名無しさん
22/11/19 23:19:13.45 r882ug7a0.net
>>503
おれも業務経験ガッツリ積んでから競プロやってるけど、競プロの知識が業務に役立つことほとんどないよ
例えばデータベースでは全レコード数をNとして、検索速度はO(logN)やO(1)らへんに落とし込むのがもともと当たり前だし、役立った気はしない
強いていうなら実装から見積もりができるようになったから、計算量やばいコードの見分けがつきやすくなったぐらいだけど、そんなことが役に立つ機会ほとんどない
なぜかというとオンメモリにたくさんデータを入れることがないからだろうな。1台の計算機でがんばるよりも、どうやってスケーラブルにするかってのが重要だし
アクションゲームのフロントエンド側とかだったら、オンメモリでいろんな幾何学的処理するからもっと役に立ちそう
どの問題が重いって言われてるのか知らんけど灰や茶が重いとか言ってもアテにならんし、ABCは他の競プロコンテストと比較すると圧倒的に実装が軽いしどういうことだろうな？

次ページ