競プロn度目の入門ということで、タイトルの問題を解いてみた。
自分には難しく感じたけど、スコア設定的にたぶん簡単な問題ということなんだろうと思う。
まだ解説が出ていないみたいなので自分なりに解説してみる。
最初に思いついたのは「石をひっくり返すcountを取りつつ実際にstringを作っていく」というものだったけど、
これではConstraintsの2 * 105の長さのSを扱うことができない。
自分の解法を言うと
Sを先頭から順番に見ていき、
対象がWだった場合には
出てきたWのカウントを + 1して、
その時点でのindex + 1から、それまでのWのカウントを引いたものをカウントに加える
というもの。
文字にすると説明が難しいが、
例えば
BBW
の場合、Wが出てくる時点でのindexは2、
Wのカウントは1なので、
3 - 1がcountになるので答えは2となる。
なぜこうなるのかは実際にflipする様子を紙などに書いていくと理解できると思う。
BBW BWB ... flip 1 WBB ... flip 2
Wが左にBの個数分移動している。ここから自分自身（W）の数を引けばflipの回数と一致する。
Wが複数出てくる場合も考え方は同じで
BWBWBW
なら、
Wが出てくるたびに上記の計算結果をcountに足せば良い。
ループ一回で済むので O(n) で解くことができる
s = gets.chomp
count = 0
w_count = 0
s.chars.each.with_index(1) do |char, i|
if char == "W"
w_count += 1
count += i - w_count
end
end
puts count
