AtCoder BC098 C: Attention

問題

C - Attention
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解法

ある人をリーダーに選んだ場合、

西から東に向きを変える人の数 = 選んだ人より西の人の内、西を向いている人の数
東から西に向きを変える人の数 = 選んだ人より東の人の内、東を向いている人の数

となります。

よって、上記を数え上げる配列を最初に作成し、それぞれの和が最小となるものを求めれば解にになります。

例2の場合、上記の配列は以下のようになり、上下の配列の和の最小値は4となります。

実装

n = gets.chomp.to_i
s = gets.chomp.split("")

w, e = [], []
ww, ee = 0, 0
s.each do |c|
    w << ww
    if c == 'W'
        ww += 1
    end
end

s.reverse.each do |c|
    e << ee
    if c == 'E'
        ee += 1
    end
end

e.reverse!

ans = 10 ** 6
for i in 0..(n-1) do
    ans = (w[i] + e[i]) if ans > (w[i] + e[i])
end
puts ans

コメント

タイトルとURLをコピーしました