[ABC351 D] Grid and Magnet
解法が難しい上に Ruby で通すのも難しいグリッド問題。
問題を要約する
- 通り道の最大面積は？
- ただし
#の上下左右より先には進めない
何が難しいのか？
# の上下左右のマスをどのグループに含めるのかが難しい。たとえば左から来たときに探索済みの印をつけてしまうと右から来たとき入れない。
コンテスト中はここで早々に詰んだ。
共通の前処理
# の上下左右の . を ! に書き換える。すると、その後の判定がシンプルになり計算時間も少し減らせる。
ただこれ、入力値を直接書き換えるのに葛藤があった。しかし、リファクタリングしていくうちに、問題の攻略だけを目的とするなら躊躇せず書き換えてしまったほうが良い場合もある、という結論にやむなく至った。
それでもまだ抵抗があるなら「自分が書き換えたわけではなく、問題が最初からそうなっていた」と考えれば、少しは心理的なハードルを下げることができるかもしれない。
解法1. 異なるグループでも行く
こちらの解説が端的でわかりやすかった。同じことを書くと (1, 1) は 0 になっていても、
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | # | |||
| 1 | 0 | 0 | 1 | ||
| 2 | 0 | # | # |
1 で突入して、
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 0 | # | |||
| 1 | 0 | 1 | 1 | ||
| 2 | 0 | # | # |
それより先には進まない、とすればよい。
これを実装するには BFS・DFS が適している。
解法2. あとで足す
# のまわりは通れないものとし、
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | # | 0 | 0 | ||
| 1 | 1 | 0 | 0 | ||
| 2 | # | # |
- 0 → 4 個
- 1 → 1 個
の状態を作ったあとで残りを隣接グループの面積に加える。
- 0 → 9 個
- 1 → 4 個
ただし重複に注意する。たとえば (4, 1) で左と上の両方に足してはいけない。それには足す相手をユニークしたあとでまとめて足せばいい。
これを実装するには BFS・DFS または素集合森が適している。
解法1の実装 (AC)
H, W = gets.split.collect(&:to_i)
Field = H.times.collect { gets.strip.chars.collect(&:to_sym) }
AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }
def around_each(x, y)
AROUND.each do |dx, dy|
vx = x + dx
vy = y + dy
if 0 <= vx && vx < W && 0 <= vy && vy < H
yield vx, vy
end
end
end
def all_each
W.times do |x|
H.times do |y|
yield x, y
end
end
end
all_each do |x, y|
if Field[y][x] == :"#"
around_each(x, y) do |x, y|
if Field[y][x] == :"."
Field[y][x] = :"!"
end
end
end
end
############ ここまで同じ ############
visited = Array.new(W) { Array.new(H) }
color = 0
bfs = -> (sx, sy) {
count = 1 # 磁石の置かれていないマスが少なくとも1つ存在するため
if Field[sy][sx] == :"." && !visited[sx][sy]
visited[sx][sy] = color
queue = [[sx, sy]]
while (fx, fy = queue.shift)
around_each(fx, fy) do |tx, ty|
case Field[ty][tx]
when :"."
unless visited[tx][ty]
visited[tx][ty] = color
count += 1
queue << [tx, ty]
end
when :"!"
if visited[tx][ty] != color # 異なる色なら行く！ (ここにすべてがかかっている)
visited[tx][ty] = color
count += 1
end
end
end
end
color += 1
end
count
}
max = 0
all_each do |x, y|
v = bfs[x, y] # => 1, 4, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 1, 1, 1
if v > max
max = v # => 1, 4, 9
end
end
p max # => 9
解法2の実装 (AC)
H, W = gets.split.collect(&:to_i)
Field = H.times.collect { gets.strip.chars.collect(&:to_sym) }
AROUND = (-1..1).to_a.repeated_permutation(2).find_all { |e| e.sum.abs == 1 }
def around_each(x, y)
AROUND.each do |dx, dy|
vx = x + dx
vy = y + dy
if 0 <= vx && vx < W && 0 <= vy && vy < H
yield vx, vy
end
end
end
def all_each
W.times do |x|
H.times do |y|
yield x, y
end
end
end
all_each do |x, y|
if Field[y][x] == :"#"
around_each(x, y) do |x, y|
if Field[y][x] == :"."
Field[y][x] = :"!"
end
end
end
end
############ ここまで同じ ############
def _(x, y)
y * W + x
end
ds = DisjointSet2.new(W * H)
all_each do |x, y|
if Field[y][x] == :"."
around_each(x, y) do |tx, ty|
if Field[ty][tx] == :"."
ds.unite(_(x, y), _(tx, ty))
end
end
end
end
counts = Hash.new(0)
all_each do |x, y|
case Field[y][x]
when :"."
counts[ds.root(_(x, y))] += 1
when :"!"
s = Set.new
around_each(x, y) do |x, y|
if Field[y][x] == :"."
s << ds.root(_(x, y))
end
end
s.each { |e| counts[e] += 1 }
end
end
p counts.values.max || 1 # => 9
TLE 対策
有向グラフを作らない
作ると計測不能なレベルで TLE になる。この問題では一度通ったところは通らないので有効グラフを活かせない。作るコストの方が高くなる。
素集合森の内部は配列で管理する
内部をハッシュで管理する使い勝手の良い実装は、グリッド問題には不向きだった。連結するマスが多すぎると TLE になってしまう。今回の問題では、(競プロでは一般的な)内部を配列で管理するタイプの実装が適している。
文字列をシンボル化する
シンボル同士の比較は整数同士の比較とほぼ変わらない。
_ { "#" == "#" } # => "108.3 ms"
_ { :"#" == :"#" } # => "43.8 ms"
_ { :"####" == :"####" } # => "43.7 ms"
_ { 0 == 0 } # => "43.2 ms"
これで 435 ms 速くなった。
between? を使わない
_ { x.between?(0, W - 1) } # => "97.9 ms"
_ { 0 <= x && x < W } # => "57.9 ms"
これで 383 ms 速くなった。
ブロック引数を配列にしない
def f0; yield [0, 1]; end
def f1; yield 0, 1; end
_ { f0 { |x, y| } } # => "101.2 ms"
_ { f1 { |x, y| } } # => "69.7 ms"
これで 280 ms 速くなった。
max メソッドはどっちでもいい
_ { a = [a, b].max } # => "52.5 ms"
_ { if a < b; a = b; end } # => "50.4 ms"
思ったほど効果はなかった。一応、開くと 5 ms 速くなった。
Discussion