競技プログラミングにハマるプログラマのスレ 176

1 ：仕様書無しさん：2024/05/12(日) 23:43:01.26 .net

競技プログラミング、オンラインジャッジ、プログラミングコンテストやCTFに関する雑談スレ
次スレは>>950

AtCoder http://atcoder.jp/
yukicoder http://yukicoder.me/
Codeforces http://codeforces.com/
CodeChef http://codechef.com/
Project Euler http://projecteuler.net/
CLIST http://clist.by/
AtCoder Problems http://kenkoooo.com/atcoder/
AtCoder Clans http://kato-hiro.github.io/AtCoderClans/

前スレ
競技プログラミングにハマるプログラマのスレ 168
https://medaka.5ch.net/test/read.cgi/prog/1711463770/
競技プログラミングにハマるプログラマのスレ 169
https://medaka.5ch.net/test/read.cgi/prog/1711884759/
競技プログラミングにハマるプログラマのスレ 170
https://medaka.5ch.net/test/read.cgi/prog/1712220373/
競技プログラミングにハマるプログラマのスレ 171(旧)
https://medaka.5ch.net/test/read.cgi/prog/1712726816/
競技プログラミングにハマるプログラマのスレ 171(新)
https://medaka.5ch.net/test/read.cgi/prog/1712726828/
競技プログラミングにハマるプログラマのスレ 172
https://medaka.5ch.net/test/read.cgi/prog/1713176839/
競技プログラミングにハマるプログラマのスレ 173
https://medaka.5ch.net/test/read.cgi/prog/1714042920/
競技プログラミングにハマるプログラマのスレ 174
https://medaka.5ch.net/test/read.cgi/prog/1714572646/
競技プログラミングにハマるプログラマのスレ 175
https://medaka.5ch.net/test/read.cgi/prog/1714981816/

435 ：仕様書無しさん：2024/05/13(月) 22:24:08.29 .net

相変わらず書き込みからレートと学歴が透けることよ
でワンパン案件だからレスバしなくていいです

436 ：仕様書無しさん：2024/05/13(月) 22:24:45.29 .net

>>434
全部水レベルだからそれは中度

437 ：仕様書無しさん：2024/05/13(月) 22:24:54.63 .net

>>433
それは話が混ざってるぞ
ここではARC500点に寒色アルゴは出ない話をしているが知識問の話はしていない

438 ：仕様書無しさん：2024/05/13(月) 22:25:23.57 .net

寒色アルゴは出ないの意味がわからない
貪欲法もアルゴリズムであることには変わりないのに

439 ：仕様書無しさん：2024/05/13(月) 22:26:08.85 .net

てかまあ昨日のC解けてない時点でどんなに高く見積もっても水下位層とかだろうしまともに相手しなくていいんだよな

440 ：仕様書無しさん：2024/05/13(月) 22:26:31.09 .net

セグ木はD以上じゃないと使わないイメージ
逆にグラフアルゴリズム(フロー除く)はC以下でも結構出る

441 ：仕様書無しさん：2024/05/13(月) 22:27:18.42 .net

DPの高速化パートで普通にARC-BCくらいでも使いますよ

442 ：仕様書無しさん：2024/05/13(月) 22:28:29.92 .net

CはともかくBでは要求されん

443 ：仕様書無しさん：2024/05/13(月) 22:28:35.67 .net

昨日のC解けてないやつ(0-1BFS知ってれば解けるから知識問題っていってるやつ)と>>437は別だぞ

444 ：仕様書無しさん：2024/05/13(月) 22:30:21.08 .net

Bにgrundy置いたのかなりキモかったから二度と置かないでほしい
数強への布教に差し支えるため

445 ：仕様書無しさん：2024/05/13(月) 22:31:04.34 .net

ARC-Aでワーシャルフロイド(BFSでも可)が出たことあるんだからCで01BFS(ダイクストラでも可)が出ても驚かん

446 ：仕様書無しさん：2024/05/13(月) 22:31:53.58 .net

てかAに置かれてるならまだしもC500点で置かれてるんだからこの程度の要求知識で文句を言う方がおかしい

447 ：仕様書無しさん：2024/05/13(月) 22:32:31.56 .net

ダイクストラとか猿でもできるし01必須じゃないならもういいだろ

448 ：仕様書無しさん：2024/05/13(月) 22:33:01.68 .net

やはり寒色diffに対する言及はインコが頓珍漢なことを言って暴れ出すからABCと同じで書き込み禁止にした方がいいな

449 ：仕様書無しさん：2024/05/13(月) 22:34:06.35 .net

ちなN<500なら01BFSでなくて普通のBFSでも通る

450 ：仕様書無しさん：2024/05/13(月) 22:36:30.06 .net

尚更インコ接待だな

451 ：仕様書無しさん：2024/05/13(月) 22:36:36.96 .net

普通のBFSでどうやるの？

452 ：仕様書無しさん：2024/05/13(月) 22:37:21.42 .net

chokudaiレベルのアドホック力になるとgrundy数も自力導出できるんかな

453 ：仕様書無しさん：2024/05/13(月) 22:37:30.24 .net

どうやるの？って言ってるのわかってなさすぎるだろ
無駄な更新が増えるだけで本質は01BFSと変わらないだろ

454 ：仕様書無しさん：2024/05/13(月) 22:39:00.11 .net

01BFSの左出し左右入れの「左右入れ」を右入れに改悪するだけ
計算量は悪くなるが最短経路は2Nマス塗り替え以内で抑えられる性質が効いてO(N^3)で耐える

455 ：仕様書無しさん：2024/05/13(月) 22:39:07.51 .net

nim/grundy数はxorが都合よく性質を満たしてるパートを自分で思いつくのは流石に厳しそう

456 ：仕様書無しさん：2024/05/13(月) 22:39:07.64 .net

ダイクストラさん

457 ：仕様書無しさん：2024/05/13(月) 22:39:36.06 .net

AGCのjokerと似た感じの計算量になる

458 ：仕様書無しさん：2024/05/13(月) 22:39:36.32 .net

通らなく無いか？
同じ場所で更新がO(n)回起こり得そうじゃないか？

459 ：仕様書無しさん：2024/05/13(月) 22:40:32.86 .net

https://atcoder.jp/contests/agc044/tasks/agc044_b

これの解説読んでね

460 ：仕様書無しさん：2024/05/13(月) 22:41:09.49 .net

where is JAP editorial?

461 ：仕様書無しさん：2024/05/13(月) 22:41:24.36 .net

>>458
n^3でも通るって話か
でも美しく無いな

462 ：仕様書無しさん：2024/05/13(月) 22:41:30.96 .net

>>453
は？

463 ：仕様書無しさん：2024/05/13(月) 22:41:39.18 .net

インコは知能も低いし英語も読めないし本当ダメだな
解説動画でもみなさい

464 ：仕様書無しさん：2024/05/13(月) 22:42:04.10 .net

01BFS/ダイクストラを知らない数強に配慮してO(N^3)が通るようにしたのか

465 ：仕様書無しさん：2024/05/13(月) 22:42:26.94 .net

本質が変わってないは嘘だが更新回数の上界的にギリ通るってことねん

466 ：仕様書無しさん：2024/05/13(月) 22:42:38.80 .net

ダイクストラなんて教科書の最初の方に書いてあるレベルだろ

467 ：仕様書無しさん：2024/05/13(月) 22:43:14.24 .net

それはただ更新回数が悪化してるだけで本質自体は全く変わってないでしょ

468 ：仕様書無しさん：2024/05/13(月) 22:43:36.39 .net

ダイクストラ、今何diff？
やるだけ茶色？

469 ：仕様書無しさん：2024/05/13(月) 22:43:56.68 .net

ARCはAGCunratedの数強が一瞬で入水するためにあるらかな

470 ：仕様書無しさん：2024/05/13(月) 22:44:04.77 .net

いや本質が変わるだろ一見したらTLEするんだから

471 ：仕様書無しさん：2024/05/13(月) 22:44:05.38 .net

BFSで本来1回見たら2回目以降の更新作業を行わないところを行うようにしても間に合うよって話かなるほど

472 ：仕様書無しさん：2024/05/13(月) 22:44:32.50 .net

鉄則本の普及で茶色下位になってるかな
CにはおけないからABC-Dにお気持ち程度の捻りを加えて置いて

473 ：仕様書無しさん：2024/05/13(月) 22:45:00.32 .net

ダイクストラは茶

474 ：仕様書無しさん：2024/05/13(月) 22:45:12.58 .net

やっぱり変わってないじゃん　ちゃんと考えてどうぞ

475 ：仕様書無しさん：2024/05/13(月) 22:45:37.91 .net

340Dがdiff784だからダイクストラは茶色

476 ：仕様書無しさん：2024/05/13(月) 22:45:41.48 .net

>>467
01BFSは0を左入れすることで余分な更新を無くせることが本質だと思っているので01BFSと本質が同じであると言われるとNoと言いたくなる

477 ：仕様書無しさん：2024/05/13(月) 22:46:41.65 .net

>>476
今回の問題の本質パートは最短経路を求める部分なので、何で求めようが本質は変わらないでしょの意味でした
01BFSとBFSが別ものなのはあたりまえ

478 ：仕様書無しさん：2024/05/13(月) 22:47:16.15 .net

ダイクストラ、アカデミアだとマジで初等(知らなきゃモグリ)だけど競プロだと緑近いのか
意外だ

479 ：仕様書無しさん：2024/05/13(月) 22:47:56.25 .net

学部の最初で取り扱う例レベルだからアカデミアとすら呼べないレベルだろ

480 ：仕様書無しさん：2024/05/13(月) 22:48:18.38 .net

>>452
grundy数自力導出出来るならSFCなわけない

481 ：仕様書無しさん：2024/05/13(月) 22:48:18.82 .net

BFSでもN^3で耐える話を真に理解できていますか？
頓珍漢すぎてびっくりしているのだが

482 ：仕様書無しさん：2024/05/13(月) 22:48:23.14 .net

340Dも一見DPっぽくみえるような捻り加えられてるからね

483 ：仕様書無しさん：2024/05/13(月) 22:49:00.08 .net

>>482
ダイクストラもDPの一種ですよ

484 ：仕様書無しさん：2024/05/13(月) 22:49:19.58 .net

問題の本質的なタスクが解けることに変わりはないって話か
アルゴリズムの本質が同じに読めた

485 ：仕様書無しさん：2024/05/13(月) 22:50:39.28 .net

BFSの計算量がN^4ではなくN^3になるみたいな話をしてるのかと思ってたら
流石に01BFSの動作原理なんて知ってるに決まってる

486 ：仕様書無しさん：2024/05/13(月) 22:50:42.55 .net

りんごさんとかくらいだとgrundy数ほどの抽象化まで発想できなくても
grundy数と本質的には同等な解法を考案して解いてたりしそう

487 ：仕様書無しさん：2024/05/13(月) 22:51:28.79 .net

本質的に同等な解法とはなんですか
そこまで行くとgrundy数と名付けてるかどうかくらいに違いしかないので自力発明でよくないですか

488 ：仕様書無しさん：2024/05/13(月) 22:51:32.94 .net

>>483
そうだった

iを0から順番に更新していくDPでは無理って話

489 ：仕様書無しさん：2024/05/13(月) 22:51:35.64 .net

BFS使っても本質的には同じじゃない？
の本質の掛かる位置でそこまで煽られても...

490 ：仕様書無しさん：2024/05/13(月) 22:52:35.29 .net

>>489
計算量の話は俺じゃないけどそっちも理解できてますか

491 ：仕様書無しさん：2024/05/13(月) 22:52:43.37 .net

りんご数というわけか

492 ：仕様書無しさん：2024/05/13(月) 22:54:32.90 .net

昨日から寒色煽りされまくってるし直近のコンテストの奥の話しようかなって思ったけど普通に解けてる人3桁目弱とか2桁で話せない
あんまり奥の方の言及がないのってこういう理由だったのか
緑上位だった頃には気づかなかった

493 ：仕様書無しさん：2024/05/13(月) 22:54:55.44 .net

grundy数もDPですか？

494 ：仕様書無しさん：2024/05/13(月) 22:55:04.30 .net

>>490
無しスレだから全部お前に見えてます

495 ：仕様書無しさん：2024/05/13(月) 22:55:23.10 .net

俺か、俺以外か

496 ：仕様書無しさん：2024/05/13(月) 22:55:24.15 .net

それはそう
俺もコンテスト後にABCのボス問の話とかしたいけど流石にキツい
黄色diffでギリギリ　橙は直後はほぼ無理

497 ：仕様書無しさん：2024/05/13(月) 22:55:37.84 .net

3人が議論すると崩壊するの欠陥だろ

498 ：仕様書無しさん：2024/05/13(月) 22:55:54.86 .net

せいじいはそれでイキリまくった挙句特定されかけたからな

499 ：仕様書無しさん：2024/05/13(月) 22:56:10.62 .net

2人で自演して崩壊させたことありゅ

500 ：仕様書無しさん：2024/05/13(月) 22:56:31.82 .net

故せいじいもGかEx解きかけて特定されたんだっけ

501 ：仕様書無しさん：2024/05/13(月) 22:56:47.13 .net

おれなんて3人で自演したことあるぞ

502 ：仕様書無しさん：2024/05/13(月) 22:57:28.13 .net

>>500
たまたま難易度逆転しててE欠けF欠けみたいなのが多い回で〜Gまでの感想全て書いて終了した

503 ：仕様書無しさん：2024/05/13(月) 22:57:30.51 .net

レスバになったらム板に行くルールを作ろう

504 ：仕様書無しさん：2024/05/13(月) 22:58:11.43 .net

私の勝ちですAC射精完了

505 ：仕様書無しさん：2024/05/13(月) 22:58:19.11 .net

半日で400レス入る5ch屈指の人気スレ

506 ：仕様書無しさん：2024/05/13(月) 22:59:10.43 .net

そろそろスレ番がARCの開催数に追いつくな

507 ：仕様書無しさん：2024/05/13(月) 22:59:12.85 .net

これでもどんぐりのせいで激しく減速しています

508 ：仕様書無しさん：2024/05/13(月) 22:59:17.53 .net

せいじいが恋しい

509 ：仕様書無しさん：2024/05/13(月) 22:59:23.96 .net

今日も侃々諤々の論争が捗ったな

510 ：仕様書無しさん：2024/05/13(月) 22:59:47.22 .net

>>509
難しい言葉使うな

511 ：仕様書無しさん：2024/05/13(月) 22:59:49.78 .net

8問制で質の高かった頃の安倍晋三忖度コンテストに帰りたい

512 ：仕様書無しさん：2024/05/13(月) 23:00:11.29 .net

>>510
国弱スギィ

513 ：仕様書無しさん：2024/05/13(月) 23:00:22.61 .net

せいじい卒業ってちょうど去年くらいか

514 ：仕様書無しさん：2024/05/13(月) 23:00:29.35 .net

>>512
淫夢語録使うな

515 ：仕様書無しさん：2024/05/13(月) 23:00:55.15 .net

ワッチョイを否定するのも低能バレを回避するためだからな

516 ：仕様書無しさん：2024/05/13(月) 23:01:23.52 .net

流石に昨日のDの話はしても特定されるわけないので勿体ぶらずしてどうぞ

517 ：仕様書無しさん：2024/05/13(月) 23:01:45.31 .net

御三家序列古文sage早生まれsageARC
いつも通り

518 ：仕様書無しさん：2024/05/13(月) 23:02:01.80 .net

お？やるか？表(ム板)にでろよ

519 ：仕様書無しさん：2024/05/13(月) 23:02:08.94 .net

ワッチョイつけても俺はいいぞ
学生証と暖色証明書(解説ボタン)はいつでも用意できる

520 ：仕様書無しさん：2024/05/13(月) 23:02:48.80 .net

ワッチョイするか卒業するか

521 ：仕様書無しさん：2024/05/13(月) 23:03:20.29 .net

病治ス卒

522 ：仕様書無しさん：2024/05/13(月) 23:03:24.77 .net

dの話できることなし

523 ：仕様書無しさん：2024/05/13(月) 23:03:42.72 .net

本スレってどうなったん

524 ：仕様書無しさん：2024/05/13(月) 23:03:54.00 .net

いうて累積積パートの話も昨日あったし
EFはどうなんだ？まだ解いてないが

525 ：仕様書無しさん：2024/05/13(月) 23:04:51.40 .net

Fはlog落としがクソキモいから嫌い

526 ：仕様書無しさん：2024/05/13(月) 23:05:20.58 .net

Fのネタバレやめろ

527 ：仕様書無しさん：2024/05/13(月) 23:06:06.27 .net

どうせ解けないため

528 ：仕様書無しさん：2024/05/13(月) 23:07:42.05 .net

D問題の難しさのメイン部分はどこなんだろうな
i番目の地震でそのグループがちょうど倒れる必要十分条件の考察？
ちょうどそのグループが倒れる確率を足して更新する部分？
ゼロ割回避部分？
たまたま自分と噛み合っただけかもしれないが順位表を見るまで青上位diffくらいだと思ってたので

529 ：仕様書無しさん：2024/05/13(月) 23:08:27.74 .net

EFの話をコンテ直後にスレでしてたらそれはのいみさんだろ

530 ：仕様書無しさん：2024/05/13(月) 23:09:04.31 .net

栗さんであってほしい　こんなに解説配信の実況レスしてるのに

531 ：仕様書無しさん：2024/05/13(月) 23:10:09.22 .net

考察パートは青上位想定で実装998コーナー回避で黄色diff想定だと思う

532 ：仕様書無しさん：2024/05/13(月) 23:10:33.63 .net

というかWがそんな感じのツイートしてなかったっけ

533 ：仕様書無しさん：2024/05/13(月) 23:10:45.24 .net

赤diffストリークが続いており非常によい

534 ：仕様書無しさん：2024/05/13(月) 23:10:56.47 .net

e8くんフォローして無いので