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

411 ：仕様書無しさん：2024/05/13(月) 22:08:09.44 .net

インコ人狼始まってるやん

412 ：仕様書無しさん：2024/05/13(月) 22:08:52.41 .net

昨日のCが知識問題とか言ってるのインコすぎる
相変わらず書き込みからレートと学歴が透けることよ

413 ：仕様書無しさん：2024/05/13(月) 22:10:51.78 .net

そんな低レベルなことにまでマウント取るな

414 ：仕様書無しさん：2024/05/13(月) 22:10:54.60 .net

>>412
知識問題じゃなきゃなんなんだ？

415 ：仕様書無しさん：2024/05/13(月) 22:12:35.05 .net

緑上位だった頃はお前らのこと尊敬してた(ミラーラビンやロリハの衝突について教えてくれたり、知らないアルゴリズムについて話ていたため)けどいざ黄色間近になると普通に俺より弱くてがっかりだよ
いや、単純に俺がB1だった頃にアドバイスくれたB3-M2たちが2年ちょい経って皆スレから卒業しただけか？

416 ：仕様書無しさん：2024/05/13(月) 22:13:36.53 .net

>>410
は？マジで俺は全部解いてるし暖色だぞ
お前が要求してきたからわざわざ探してやってるのにお前みたいな低レートと一緒にすんなよ

直近10回くらいでも

括弧列の必要条件を要求する典型知識問題
arc175_b

ABC-Eレベルの確率DP
arc174_c

grundy数要求する典型知識問題
arc168_b

とかがある

417 ：仕様書無しさん：2024/05/13(月) 22:13:47.95 .net

考察問題でしょ
お互いに影響しないことだけ考察できれば後は最短経路

418 ：仕様書無しさん：2024/05/13(月) 22:14:02.35 .net

今度はお前が教える番になったんだよ

419 ：仕様書無しさん：2024/05/13(月) 22:14:32.78 .net

誕生日憎い

420 ：仕様書無しさん：2024/05/13(月) 22:14:38.59 .net

マジで明らかに俺よりも問題解いてない＆レート低いインコが喧嘩売ってくるの不快すぎる　身の程をしれ

421 ：仕様書無しさん：2024/05/13(月) 22:15:50.70 .net

arc173aも桁dporN進法だから知識寄りだし

422 ：仕様書無しさん：2024/05/13(月) 22:17:31.74 .net

>>416
あったわすまんな
そのへんARCで出たのが不愉快過ぎて記憶から消してた
あと173ABも混ぜていいぞ

423 ：仕様書無しさん：2024/05/13(月) 22:17:53.50 .net

てかARC-BCくらいにはちょい捻りDPをベースにした問題があげきれないくらい出題されてるから明らかに最短距離を求めるアルゴリズム程度の茶色レベルの知識よりはその時点で知識の要求度が高い

424 ：仕様書無しさん：2024/05/13(月) 22:18:33.97 .net

>>422
お前はそんな鳥頭だから一生インコなんだよ

425 ：仕様書無しさん：2024/05/13(月) 22:19:18.39 .net

君たちはどうイキるか

426 ：仕様書無しさん：2024/05/13(月) 22:20:13.57 .net

>>424
高度アルゴの線引きが甘かったのはそう
セグ木遅延セグ木フローロリハみたいなのを想定してた

427 ：仕様書無しさん：2024/05/13(月) 22:20:58.61 .net

>>426
01BFSなんて茶色緑色diff程度でABCに何回も出題されてるのにそれらと同率な訳がない

428 ：仕様書無しさん：2024/05/13(月) 22:21:41.92 .net

ロリハとセグ木は高度デアではない(鉄則本にも載ってるレベル)し本当適当すぎる

429 ：仕様書無しさん：2024/05/13(月) 22:21:58.75 .net

>>427
いや何の話だよ

430 ：仕様書無しさん：2024/05/13(月) 22:22:45.88 .net

やはりスレ二分木を採用したほうがいいな

431 ：仕様書無しさん：2024/05/13(月) 22:22:59.90 .net

流石に昨日のCを知識問題として片付けるのは抽象化が下手すぎる

432 ：仕様書無しさん：2024/05/13(月) 22:23:17.09 .net

>>428
寒色アルゴを高度アルゴ認定する文脈なのでこれはセーフ

433 ：仕様書無しさん：2024/05/13(月) 22:23:28.63 .net

>>429
知識問題認定するラインの話をそっちが始めたんでしょうが

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

高度デアって、nim、grundy、LISとかその辺か？

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問制で質の高かった頃の安倍晋三忖度コンテストに帰りたい