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

---

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

---

605: 2023/12/26(火)03:15 AA×


[240|320|480|600|100%|JPG|べ|ﾚｽ栞|ﾚｽ消]
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
なんかいける気がしてきたな 左上から順にロールバックしながら期待値計算し計算が終わったマスは確定済の頂点としてを行う 以下緑マスのうち確定済頂点を 待ち頂点をとする 前提としてとは直接で繋がずかわりに待ち側の親に隣接する確定済頂点の代表値一覧リンクを持たせる たぶんリンクは集合じゃなくて辞書でないとだめ ははよしなにはリンクから削除 期待値計算のの連結判定はの代表値はに存在するか？に読み替える 再が面倒で 同士を 小さい集合を即座に経路圧縮のリンクにも経路圧縮の結果を波及 とすれば側の代表値は常に最新のものになってうれしい 頭の中では全部なんだよな 明日詰める

---

上下前次1-新書関写板覧索設栞歴

---

あと 397 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.033s