2022.02.07

競プロ典型90問 012:Red Paintingをやってみた

競プロ典型90問の『Red Painting』をやってみた。とても学びがあったものの解説を理解するのにだいぶ時間がかかってしまったので、覚書きをしておこうと思う。

問題

問題文は公式↓に書いてあるのだけど、KaTeXを導入したばかりなので使い方を覚える目的で引用写経する。

問題文

$H$ 行 $W$ 列のマス目があり、上から $i(1 \le i \le H)$ 行目、左から $j(1 \le j \le W)$ 列目のマスを $(i,j)$ と表します。

最初すべてのマスは白いです。ここで、 $Q$ 個のクエリが以下の形式で与えられます。

$i(1 \le i \le Q)$ 番目のクエリについて：

$t_i = 1$ のとき
- 整数 $r_i,c_i$ が与えられる。
- 白いマス $(r_i,c_i)$ が赤色で塗られる。
$t_i = 2$ のとき
- 整数 $ra_i,ca_i,rb_i,cb_i$ が与えられる。
- 次の 2 つの条件両方を満たすときYes、そうでければNoと出力する。
  - マス $(ra_i,ca_i)$ とマス $(rb_i,cb_i)$ が赤色で塗られている。
  - マス $(ra_i,ca_i)$ からマス $(rb_i,cb_i)$ まで、赤色マス上を上下左右に移動することで辿り着ける。

以上の $Q$ 個のクエリを順に処理してください。

制約

$1 \le H,W \le 2000$
$1 \le Q \le 100000$
$1 \le t_i \le 2$
$t_i = 1$ のとき、 $1 \le r_i \le H$ 、 $1 \le c_i \le W$
$t_i = 2$ のとき、 $1 \le ra_i,rb_i \le H$ 、 $1 \le ca_i,cb_i \le W$
$t_i = 1$ かつ $t_j = 1 (1 \le i \lt j \le Q)$ のとき、 $(r_i,c_i) \ne (r_j,c_j)$
与えられる入力は全て整数

考え方

クエリ1で指示される、言われたマスを赤く塗るのはまあ真偽値配列を使えば良いとして、問題なのは、ある赤マス $(ra_i,ca_i)$ からある赤マス $(rb_i,cb_i)$ まで、赤マスだけを通ってたどりつけるかどうかの判定。

幅優先探索で求めるには制約が大きすぎる。

こういう問題には、グループ分けを木構造で表現する Union-Find というデータ構造がもってこいらしい。(Union-Findについて詳しくはこちら)

上下左右で連結された赤マス同士をグループ化して保持しておいて、あるマスAとマスBがクエリで与えられた時にマスA,Bが同じグループに属しているかを木に聞けば教えてくれる。というわけ。

実装

例によって Ruby で実装した。頭が全然追いつかなかったので過剰なぐらいにコメントを書いている。長いのでアコーディオンで隠す。

UnionFind は今後再利用できそうだったのでクラスにした。

Ruby で Red Painting

class UnionFind
  def initialize(n)
    # par[i]: iの親要素番号を表す
    # par[i] = i の時、par[i]は根
    @par = []
    n.times { |i| @par[i] = i }
  end

  # データxが属する木の根を返す
  def root(x)
    # x自身が根の場合
    return x if @par[x] == x
    # 自身が根でない場合は再起で親を辿る
    return root(@par[x])
  end

  # xとyの木を併合する
  def unite(x, y)
    # xとyの根を取得する
    rx = root(x)
    ry = root(y)
    return if rx == ry # もともと同じ木の場合は何もしない
    @par[rx] = ry # xの親をyにする = yが根になる
  end

  # xとyが同じ木に属しているかを調べる
  def same?(x, y)
    rx = root(x)
    ry = root(y)
    return rx == ry
  end
end

# 2値を整数型のハッシュで返す
def h(x,y)
  2002 * x + y
end

def query1(r,c,red,uf)
  # 赤色で塗る
  # redは1オリジンで使う
  red[r][c] = true

  # 赤同士で隣接してるマスのグループ化処理
  dx = [-1,0,1,0]
  dy = [0,1,0,-1]
  4.times do |i|
    # 赤で塗ったマスの隣接4マスが赤で塗られているかチェック
    sx = r + dx[i]
    sy = c + dy[i]
    next unless red[sx][sy] # 赤くない
    # UFにはハッシュ値で格納する
    h1 = h(r,c)
    h2 = h(sx,sy)
    uf.unite(h1,h2)
  end
end

def query2(px,py,qx,qy,red,uf)
  # 両マスが赤でなければ処理しない
  return false unless red[px][py] && red[qx][qy]
  h1 = h(px,py)
  h2 = h(qx,qy)
  # 両マスが隣接していればtrueが返る
  uf.same?(h1,h2)
end

# 入力と初期化
def darray(n1,n2,ini=nil); Array.new(n1) { Array.new(n2) { ini } } end
H,W = gets.split.map(&:to_i)
Q = gets.to_i
q = Q.times.map { gets.split.map(&:to_i) }

# UnionFind木を初期化
# ハッシュ値が大きな値を取るので大きめに確保
uf = UnionFind.new(2002 * 2002)
# 赤塗り配列
# 4方向を調べるので、領域外アクセスを防ぐ為に外壁分のサイズを確保して(1,1)オリジンで使う
red = darray(H+2,W+2,false)

Q.times do |i|
  qi = q[i]
  if qi[0] == 1
    query1(qi[1],qi[2],red,uf)
  else
    puts query2(qi[1],qi[2],qi[3],qi[4],red,uf) ? "Yes" : "No"
  end
end

Union-Find木

1次元配列parで以下のイメージでデータを保持する。値は自分の親の要素番号。

par[5] = 10,par[10] = 20, par[20] = 20 だとすると、要素5と10と20は同じグループ。要素番号と値が同じであればそれがグループの根。

この問題を解くために必要なUnion-Find木のメソッドは3つ。シンプル。

root(x)
- 引数xの要素の根を返す
same?(x,y)
- 引数x,yが同じグループかどうかを返す
  - 親を辿っていって根が一致すれば同じグループと言える
unite(x,y)
- 引数x,yを同じグループにする
  - xの根rxとyの根ryを取得し、ryをrxの根にする
  - 根が同じになれば同じグループ

クエリ1でマスを赤く塗る際に上下左右のマスの色を調べて、赤いマスがあればuniteでグループに加える。
クエリ2ではsame?で赤マス同士が同じグループに属しているかを見れば良い。

所感

今回も初見ではまったくわからずに安定の解説ACだったけど、Union-Find木の実装を含めて人に説明できるくらいには理解できたと思う。

意外と一番難しいと感じたのが、座標をハッシュ化するところだった。 $(i,j)$ で表現されている座標を、1次元配列に整数で格納するということを初めてやったので面食らった。最初、整数にした後に可逆にしないといけないのかと思いこんで頭を抱えたけど、2マスが同じグループかどうかの判定するだけだから衝突さえしなければ問題なかった。

今回は列の最大値と $x$ を掛けて $y$ を足したが、Webを検索するとシフト演算を使っている人もいて興味深かった。

参考文献

https://yukituna.com/3268/

http://nare-kuri.jp/kb/knowledge/452

身に付けないといけないアルゴリズムがまだたくさんあるので、今後も引き続き典型90問を解答ACし続けていくとする。今日は眠いからもう寝る