この問題の公式解説では厳密な解法を採用しているのですが、実際には単純な貪欲法でも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
ちなみに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