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

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

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

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

609(2): 2023/12/26(火)04:26 AAS
>>608
undo済側と未undo側の境界にあるW-1個の辺について、pair(上マスの代表値, 下マスの代表値)をキーとしたmapで辺の個数をカウントしておけばよさそう

610(2): 2023/12/26(火)04:43 AAS
>>609
連結判定1クエリあたりO(W)かからない？
つまり　上→下・下→上の接続判定をO(1)で行うんだろ
M型の縦方向にジグザグとした配置のとき、接続判定がW/2回発生すると思う

611: 2023/12/26(火)04:43 AAS
>>609
代表値が変わる瞬間については、map[(新しい代表値, 新しい代表値)] += map[(古い代表値, 古い代表値)] というふうに移して、古い方はもちろん0にする