[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 144 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
605: 2023/12/26(火)03:15 AAS
なんかいける気がしてきたな
左上から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)なんだよな
明日詰める
上下前次1-新書関写板覧索設栞歴
あと 397 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.007s