[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
競技プログラミングにハマるプログラマのスレ 143 http://medaka.5ch.net/test/read.cgi/prog/1703141733/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
266: 仕様書無しさん [sage] 2023/12/22(金) 10:14:11.90 多分頭にあるのは同じアルゴリズムなんだけど、用語の使い方の感覚が違うというだけな気がする 大きい方から小さい方に照会を行うと言われると、大きい方の連想配列のkeyを全部取り出して、小さい方の連想配列内に存在するか否かを判定しているように聞こえた 俺がいいたかった「小さい方から大きい方に照会する」というのは for query_key in small: if query_key in big: process(query_key) # 初めてquery_keyの２頂点が連結したと判定 else: small.add(query_key) かな、ここでマージも一緒にやる Pythonが一番疑似コードっぽいからそれで書いた 別に頂点は保持する必要なくてhashsetでいい http://medaka.5ch.net/test/read.cgi/prog/1703141733/266
267: 仕様書無しさん [sage] 2023/12/22(金) 10:16:14.51 >>266 ５行目はsmall.add(query_key)じゃなくて、big.add(query_key) http://medaka.5ch.net/test/read.cgi/prog/1703141733/267
271: 仕様書無しさん [sage] 2023/12/22(金) 10:36:39.24 >>266 ぜんぜん違うアルゴリズムだった そっちのほうが綺麗だわ 恥晒ししとくと、G[集合A][頂点i] = [クエリx, クエリy, …] みたいな集合と頂点の隣接辞書を考えてた 無駄にO(NlogN)が生えるゴミなので忘れてください http://medaka.5ch.net/test/read.cgi/prog/1703141733/271
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.696s*