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

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

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

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

612(1): 2023/12/26(火)04:50 AAS
>>610
map[(左/上の代表値, 右/下の代表値)]が正かどうか、つまりその2グループの境目になっている辺があるかどうかでO(1)で判定できると考えているが

615: 2023/12/26(火)05:08 AAS
>>610
（簡単のため下図は緑マスだけの状態）
12223
12?bc
abbbc
例えば"?"マスの上下左右について判定したいときは、
{(1, a): 1, (2, b): 2, (3, c): 1}
省1