解説 AtCoder Beginner Contest 174 D - Alter Altar

atcoder.jp

この問題の公式解説では厳密な解法を採用しているのですが、実際には単純な貪欲法でもACすることができます。具体的には「N個の石を左から見ていって、見ている石が白色の場合は、見ている石より右側にある赤い石のうち、もっとも右にあるものと交換するということを繰り返し、交換できなくなったら終了」というものです。「見ている石より右側にある赤い石のうち、もっとも右にあるもの」の管理ですが、これはStackのようなデータ構造を利用すると簡単です。

この方針でACしたRubyコードは以下の通り。

n = gets.to_i
s = gets.chomp

stack = []
(0...n).each do |i|
  stack << i if s[i] == "R"
end

ans = 0
(0...n).each do |i|
  if s[i] == "W"
    j = stack.pop
    break if j.nil? || i > j
    ans += 1
  end
end

puts ans

atcoder.jp

ちなみにRubyの特徴であるメソッドチェーンを使って、書き換えたものが以下のコードですが、これはちょっとやりすぎですね(´・ω・｀)

n = gets.to_i
s = gets.chomp

stack = s.chars
         .each_with_index
         .filter_map{|ch, i| i if ch == "R"}
ans = s.chars
       .each_with_index
       .filter_map{|ch, i| i if ch == "W"}
       .take_while{|i| !stack.empty? && i < stack.pop}
       .size
p ans

atcoder.jp