[過去ﾛｸﾞ]
競技プログラミングにハマるプログラマのスレ 144 (1002ﾚｽ)
競技プログラミングにハマるプログラマのスレ 144 http://medaka.5ch.net/test/read.cgi/prog/1703346239/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索
歴削→次ｽﾚ
栞削→次ｽﾚ
過去ﾛｸﾞﾒﾆｭｰ
605: 仕様書無しさん [sage] 2023/12/26(火) 03:15:17.84 なんかいける気がしてきたな 左上からZ順にロールバックしながら期待値計算し、計算が終わったマスは「確定済」の頂点としてUFを行う 以下、緑マスのうち確定済頂点をo undo待ち頂点をuとする 前提としてuとoは直接UFで繋がず、かわりにundo待ち側の親に、隣接する確定済頂点の代表値一覧（リンク）を持たせる たぶんリンクは集合じゃなくて辞書でないとだめ undoはu-uはよしなに、u-oはリンクから削除 期待値計算のu-oの連結判定は、「oの代表値はuに存在するか？」に読み替える 再uniteが面倒で o-o同士をUnion by size→小さい集合を即座に経路圧縮→o-uのリンクにも経路圧縮の結果を波及 とすれば、u側の代表値は常に最新のものになってうれしい 頭の中では全部O(logN)なんだよな 明日詰める http://medaka.5ch.net/test/read.cgi/prog/1703346239/605
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 397 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.007s