競技プログラミングにハマるプログラマのスレ 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/

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くんフォローして無いので

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

すぬけさんのARCでのDの提出コード
ttps://atcoder.jp/contests/arc177/submissions/53420383

536 ：仕様書無しさん：2024/05/13(月) 23:11:41.22 .net

言われると方針は難しくはないけど、まあめんどいパートはちょこちょこあるしそれに998のバグが挟まると苦しそう

537 ：仕様書無しさん：2024/05/13(月) 23:11:44.08 .net

草生えまくり

538 ：仕様書無しさん：2024/05/13(月) 23:11:52.36 .net

赤diffストリークって続けられるほど問題あるの？
インコだから分からない

539 ：仕様書無しさん：2024/05/13(月) 23:12:26.82 .net

別にマジでスレは卒業したいんだよな
普通にスレのやる気あるデア勢でdiscord作って移住してネトストゴシインコを置き去りにしたい

540 ：仕様書無しさん：2024/05/13(月) 23:12:57.27 .net

本スレに移住するだけで良かったりしない？

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

>>538
problems見ればわかるけど赤だけでも300くらいあるし銅以上含めたらもっとある

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

すぬけさんもDは解けなかったか

543 ：仕様書無しさん：2024/05/13(月) 23:14:23.50 .net

解けないというかアンレだしやる気起きなかっただけでは

544 ：仕様書無しさん：2024/05/13(月) 23:14:31.10 .net

でもメンタル限界の日に変な書き込みできませんよ

545 ：仕様書無しさん：2024/05/13(月) 23:14:33.28 .net

いたとしたら特定容易

546 ：仕様書無しさん：2024/05/13(月) 23:14:36.74 .net

AのFAってgptなのかなぁ
コードみるとそんな感じがする

547 ：仕様書無しさん：2024/05/13(月) 23:14:58.69 .net

俺はメンタル限界の日に変な書き込みをしているため

548 ：仕様書無しさん：2024/05/13(月) 23:15:09.77 .net

E通してから14分しかなかっただけの話では

549 ：仕様書無しさん：2024/05/13(月) 23:15:43.16 .net

キチゲ発散スレなので

550 ：仕様書無しさん：2024/05/13(月) 23:17:51.50 .net

たしかにGPTっぽい
判定ツール使うと高確率でAI生成されたコードと判定される

551 ：仕様書無しさん：2024/05/13(月) 23:17:58.67 .net

メンタル限界の日に憂さ晴らしにここ来てるわ

552 ：仕様書無しさん：2024/05/13(月) 23:18:36.64 .net

ガイジスレはガイジ達のハッテン場

553 ：仕様書無しさん：2024/05/13(月) 23:19:25.29 .net

discordで馴れ合うのとxで馴れ合うの、違いは何？