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

[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 162 (1002ﾚｽ)
上下前次 1-新

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

928: 2024/03/08(金)19:00 AAS
>>926
トンクス

929: 2024/03/08(金)19:01 AAS
〇〇DPと名前を付けているのが競プロだけなので

930(1): 2024/03/08(金)19:06 AAS
そもそもDPって配列を埋めていくだけじゃないしね

931(1): 2024/03/08(金)19:08 AAS
配列を埋めていくっていう認識を持たないだろべつに

932: 2024/03/08(金)19:08 AAS
「けた」を下からやるから竹dp

きっしょ

933: 2024/03/08(金)19:09 AAS
インコは竹からすら落ちる

934: 2024/03/08(金)19:10 AAS
DPテーブルとDPケーブルの編集距離が1で困る
後者はdisplay port

935(2): 2024/03/08(金)19:11 AAS
>>931
競プロやるDPは全部DPテーブル作ってそれを埋めてくだけじゃん

936: 2024/03/08(金)19:11 AAS
結果を配列に格納してるだけだし、そういう認識の仕方してる人はあんまりいなさそう

937: 2024/03/08(金)19:12 AAS
mapで状態管理するDPも茶-緑diffくらいですが

938: 2024/03/08(金)19:13 AAS
DPはメモ化再帰派の生き残りだな
forループで埋まるbitDPの台頭で絶滅したと思っていたが

939: 2024/03/08(金)19:14 AAS
インコは本質を捉えられないがち

940: 2024/03/08(金)19:16 AAS
テーブルは配列とは限りません

941: 2024/03/08(金)19:16 AAS
デアでも変なのが絡んでくるな

942: 2024/03/08(金)19:17 AAS
drknならわかりやすく説明してくれるのになぁ

943: 2024/03/08(金)19:17 AAS
まあこの程度はデアですらないかもしれんが

944: 2024/03/08(金)19:18 AAS
ぜんぜんインコ大王以下の議論だとおもった

945: 2024/03/08(金)19:20 AAS
drknならわかりやすく診断してくれるのになぁ

946: 2024/03/08(金)19:20 AAS
嫌なら得意のプログラミングでレート制限がある掲示板を作ってもいいんやぞ

947: 2024/03/08(金)19:22 AAS
そのレートはどう証明するんですかインコさん

948: 2024/03/08(金)19:23 AAS
公式解説レスバトルとcodeforcesレスバトルのどっちがいい

949: 2024/03/08(金)19:23 AAS
公式解説じゃなくてユーザ解説だった

950(1): 2024/03/08(金)19:26 AAS
部分問題最適性みたいなやつが本質でしょ
というかDPって普通に学部レベルの授業でも取り扱う内容だから色々インコとエアプが透けすぎてて無理しなくていいぞという気持ちになる

951: 2024/03/08(金)19:27 AAS
>>935
その認識はインコ透けすぎ

952: 2024/03/08(金)19:33 AAS
つまり変数に何かを保持した時点でDPだよ

953: 2024/03/08(金)19:36 AAS
部分問題の解からより大きな部分問題の解を求めてるだけだし
じゃあプログラム上で部分問題の解をどう保持するか？って言ったらテーブルですよねになりませんか？
DPテーブル埋めてくだけじゃん←そりゃそう

954: 2024/03/08(金)19:37 AAS
めんどくさDPオタクに言わせると328Eのbit集合列挙はDPではないらしい

955: 2024/03/08(金)19:39 AAS
1次元でもDPだし1変数でもDP

956: 2024/03/08(金)19:40 AAS
ユーザ解説の著者が黄色だと^^となり青色だと^^;;;;;

957: 2024/03/08(金)19:40 AAS
木dp