🐢

[ABC341 C] Takahashi Gets Lost

2024/02/18に公開

Ruby

普通の発想では何やっても (Ruby では) TLE になる問題。

提出したコード (TLE)

3317 ms

H, W, N = gets.split.collect(&:to_i)  # => [6, 7, 5]
T = gets.strip.chars                  # => ["L", "U", "L", "D", "R"]
S = H.times.collect { gets.strip }    # => ["#######", "#...#.#", "##...##", "#.#...#", "#...#.#", "#######"]

V = Data.define(:x, :y) do
  def +(v) = self.class.new(x + v.x, y + v.y)
end

DIRS = { "D" => V[0, 1], "R" => V[1, 0], "U" => V[0, -1], "L" => V[-1, 0] }

starts = []
W.times do |x|
  H.times do |y|
    if S[y][x] == "."
      starts << V[x, y]
    end
  end
end

count = starts.count do |v|
  T.all? do |dir|
    v += DIRS[dir]
    S[v.y][v.x] == "."
  end
end

p count                               # => 2

いつものようにあまり競プロを意識していないコードではあるが、公式の解説では似たようなコードで通っていたので、ベクトルを使わないコードに書き直してみる。が、TLE。開始地点をまとめないようにしても TLE。限界まで展開しても TLE。小手先の最適化ではどうしようもなかった。

模範解答

そこで、あとから掲載されていたこちらの解説および実装を参考にしたのが、

これなのだが、

AC (943 ms)

H, W, N = gets.strip.split.collect(&:to_i)  # => [6, 7, 5]
T = gets.strip                              # => "LULDR"
S = H.times.collect { gets.strip }          # => ["#######", "#...#.#", "##...##", "#.#...#", "#...#.#", "#######"]

bs = 0
H.times do |y|
  W.times do |x|
    if S[y][x] == "."
      bs |= 1 << (y * W + x)
    end
  end
end

dp = bs                                     # => 12470130432

T.each_char do |ch|
  case ch
  when "L" then dp >>= 1
  when "R" then dp <<= 1
  when "U" then dp >>= W
  when "D" then dp <<= W
  end
  dp &= bs
end

p dp.digits(2).count(1)                     # => 2

なんと 3317 ms かかっていたのが 943 ms になった。いったいどういう仕組みなのか？

シミュレーション

入力が、

3 4 2
RL
####
#..#
####

となっているとき RL の移動で生き残れるのは左側の陸だけだとひと目わかる。これがどのように導き出されるのかを確認すると、

変数	値の変化	説明
	00100000	左側の陸1 (1, 1) をビット化
	01000000	右側の陸2 (2, 1) をビット化
bs	01100000	両方を OR したのを元のマップ bs とする
dp	01100000	bs を dp にコピーする
dp	11000000	まず右移動なので左シフトする
bs	01100000	それを元のマップでマスクすると
dp	01000000	元のマップに陸2がめり込んでいるので陸2が消えた(？)
dp	00100000	いったん左移動で戻ってみる (右シフトする)
bs	01100000	それを元のマップでマスクすると
dp	00100000	やっぱり陸2の方が消されていた

となって陸2だけが消されたのがわかる。さらに、同じ列に対しても同じ処理がループなしで適用されるだろうから大幅な最適化に繋がる。

これは、半透明にした実際の地図を二枚用意し、一方を動かして海と重なっている陸を消すイメージに似ている。

提出したコード (TLE)

模範解答

シミュレーション

Discussion