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

**仕様書無しさん** · 2024/05/12(日) 23:43:01.26

競技プログラミング、オンラインジャッジ、プログラミングコンテストや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/

**仕様書無しさん** · 2024/05/13(月) 22:37:30.24

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

**仕様書無しさん** · 2024/05/13(月) 22:39:00.11

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

**仕様書無しさん** · 2024/05/13(月) 22:39:07.51

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

**仕様書無しさん** · 2024/05/13(月) 22:39:07.64

ダイクストラさん

**仕様書無しさん** · 2024/05/13(月) 22:39:36.06

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

**仕様書無しさん** · 2024/05/13(月) 22:39:36.32

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

**仕様書無しさん** · 2024/05/13(月) 22:40:32.86

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

これの解説読んでね

**仕様書無しさん** · 2024/05/13(月) 22:41:09.49

where is JAP editorial?

**仕様書無しさん** · 2024/05/13(月) 22:41:24.36

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

**仕様書無しさん** · 2024/05/13(月) 22:41:30.96

>>453
は？

**仕様書無しさん** · 2024/05/13(月) 22:41:39.18

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

**仕様書無しさん** · 2024/05/13(月) 22:42:04.10

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

**仕様書無しさん** · 2024/05/13(月) 22:42:26.94

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

**仕様書無しさん** · 2024/05/13(月) 22:42:38.80

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

**仕様書無しさん** · 2024/05/13(月) 22:43:14.24

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

**仕様書無しさん** · 2024/05/13(月) 22:43:36.39

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

**仕様書無しさん** · 2024/05/13(月) 22:43:56.68

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

**仕様書無しさん** · 2024/05/13(月) 22:44:04.77

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

**仕様書無しさん** · 2024/05/13(月) 22:44:05.38

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

**仕様書無しさん** · 2024/05/13(月) 22:44:32.50

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

**仕様書無しさん** · 2024/05/13(月) 22:45:00.32

ダイクストラは茶

**仕様書無しさん** · 2024/05/13(月) 22:45:12.58

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

**仕様書無しさん** · 2024/05/13(月) 22:45:37.91

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

**仕様書無しさん** · 2024/05/13(月) 22:45:41.48

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

**仕様書無しさん** · 2024/05/13(月) 22:46:41.65

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

**仕様書無しさん** · 2024/05/13(月) 22:47:16.15

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

**仕様書無しさん** · 2024/05/13(月) 22:47:56.25

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

**仕様書無しさん** · 2024/05/13(月) 22:48:18.38

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

**仕様書無しさん** · 2024/05/13(月) 22:48:18.82

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

**仕様書無しさん** · 2024/05/13(月) 22:48:23.14

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

**仕様書無しさん** · 2024/05/13(月) 22:49:00.08

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

**仕様書無しさん** · 2024/05/13(月) 22:49:19.58

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

**仕様書無しさん** · 2024/05/13(月) 22:50:39.28

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

**仕様書無しさん** · 2024/05/13(月) 22:50:42.55

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

**仕様書無しさん** · 2024/05/13(月) 22:51:28.79

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

**仕様書無しさん** · 2024/05/13(月) 22:51:32.94

>>483
そうだった

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

**仕様書無しさん** · 2024/05/13(月) 22:51:35.64

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

**仕様書無しさん** · 2024/05/13(月) 22:52:35.29

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

**仕様書無しさん** · 2024/05/13(月) 22:52:43.37

りんご数というわけか

**仕様書無しさん** · 2024/05/13(月) 22:54:32.90

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

**仕様書無しさん** · 2024/05/13(月) 22:54:55.44

grundy数もDPですか？

**仕様書無しさん** · 2024/05/13(月) 22:55:04.30

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

**仕様書無しさん** · 2024/05/13(月) 22:55:23.10

俺か、俺以外か

**仕様書無しさん** · 2024/05/13(月) 22:55:24.15

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

**仕様書無しさん** · 2024/05/13(月) 22:55:37.84

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

**仕様書無しさん** · 2024/05/13(月) 22:55:54.86

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

**仕様書無しさん** · 2024/05/13(月) 22:56:10.62

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

**仕様書無しさん** · 2024/05/13(月) 22:56:31.82

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

**仕様書無しさん** · 2024/05/13(月) 22:56:47.13

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

**仕様書無しさん** · 2024/05/13(月) 22:57:28.13

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

**仕様書無しさん** · 2024/05/13(月) 22:57:30.51

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

**仕様書無しさん** · 2024/05/13(月) 22:58:11.43

私の勝ちですAC射精完了

**仕様書無しさん** · 2024/05/13(月) 22:58:19.11

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

**仕様書無しさん** · 2024/05/13(月) 22:59:10.43

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

**仕様書無しさん** · 2024/05/13(月) 22:59:12.85

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

**仕様書無しさん** · 2024/05/13(月) 22:59:17.53

せいじいが恋しい

**仕様書無しさん** · 2024/05/13(月) 22:59:23.96

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

**仕様書無しさん** · 2024/05/13(月) 22:59:47.22

>>509
難しい言葉使うな

**仕様書無しさん** · 2024/05/13(月) 22:59:49.78

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

**仕様書無しさん** · 2024/05/13(月) 23:00:11.29

>>510
国弱スギィ

**仕様書無しさん** · 2024/05/13(月) 23:00:22.61

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

**仕様書無しさん** · 2024/05/13(月) 23:00:29.35

>>512
淫夢語録使うな

**仕様書無しさん** · 2024/05/13(月) 23:00:55.15

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

**仕様書無しさん** · 2024/05/13(月) 23:01:23.52

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

**仕様書無しさん** · 2024/05/13(月) 23:01:45.31

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

**仕様書無しさん** · 2024/05/13(月) 23:02:01.80

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

**仕様書無しさん** · 2024/05/13(月) 23:02:08.94

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

**仕様書無しさん** · 2024/05/13(月) 23:02:48.80

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

**仕様書無しさん** · 2024/05/13(月) 23:03:20.29

病治ス卒

**仕様書無しさん** · 2024/05/13(月) 23:03:24.77

dの話できることなし

**仕様書無しさん** · 2024/05/13(月) 23:03:42.72

本スレってどうなったん

**仕様書無しさん** · 2024/05/13(月) 23:03:54.00

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

**仕様書無しさん** · 2024/05/13(月) 23:04:51.40

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

**仕様書無しさん** · 2024/05/13(月) 23:05:20.58

Fのネタバレやめろ

**仕様書無しさん** · 2024/05/13(月) 23:06:06.27

どうせ解けないため

**仕様書無しさん** · 2024/05/13(月) 23:07:42.05

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

**仕様書無しさん** · 2024/05/13(月) 23:08:27.74

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

**仕様書無しさん** · 2024/05/13(月) 23:09:04.31

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

**仕様書無しさん** · 2024/05/13(月) 23:10:09.22

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

**仕様書無しさん** · 2024/05/13(月) 23:10:33.63

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

**仕様書無しさん** · 2024/05/13(月) 23:10:45.24

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

**仕様書無しさん** · 2024/05/13(月) 23:10:56.47

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

**仕様書無しさん** · 2024/05/13(月) 23:10:57.32

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

**仕様書無しさん** · 2024/05/13(月) 23:11:41.22

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

**仕様書無しさん** · 2024/05/13(月) 23:11:44.08

草生えまくり

**仕様書無しさん** · 2024/05/13(月) 23:11:52.36

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

**仕様書無しさん** · 2024/05/13(月) 23:12:26.82

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

**仕様書無しさん** · 2024/05/13(月) 23:12:57.27

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

**仕様書無しさん** · 2024/05/13(月) 23:13:01.52

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

**仕様書無しさん** · 2024/05/13(月) 23:13:44.25

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

**仕様書無しさん** · 2024/05/13(月) 23:14:23.50

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

**仕様書無しさん** · 2024/05/13(月) 23:14:31.10

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

**仕様書無しさん** · 2024/05/13(月) 23:14:33.28

いたとしたら特定容易

**仕様書無しさん** · 2024/05/13(月) 23:14:36.74

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

**仕様書無しさん** · 2024/05/13(月) 23:14:58.69

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

**仕様書無しさん** · 2024/05/13(月) 23:15:09.77

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

**仕様書無しさん** · 2024/05/13(月) 23:15:43.16

キチゲ発散スレなので

**仕様書無しさん** · 2024/05/13(月) 23:17:51.50

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

**仕様書無しさん** · 2024/05/13(月) 23:17:58.67

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

**仕様書無しさん** · 2024/05/13(月) 23:18:36.64

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