読者です 読者をやめる 読者になる 読者になる

/home/cympfh/

数式を $$ で囲んで書いてますが面倒くさいので、いちいち、はてな書式にしたりしません

チワワ文字列 - yukicoder

プロコン

チワワ文字列 - yukicoder

No.345 最小チワワ問題 - yukicoder

文字列の長さが 100 以下であるので、両端を全通り試した部分文字列全てについて、 チワワ列であるか判定して、最短のものを見つければ良い

s=gets.chomp.chars
a=1e9
(0...s.size).each{|i|
  (i...s.size).each{|j|
    k=['w','w','c']
    s[i..j].each{|c| k.pop if k[-1]==c }
    a=[a,s[i..j].size].min if k.empty?
  }
}
p a>1e8?-1:a

チワワ列の判定が若干、技巧的で、正規表現使えば一発じゃん、と気付いて

s=gets.chomp
a=(0..n=s.size).map{|i|
  (0..n).map{|j|
    s[i...i+j].match(/c.*w.*w/)?j:1e5
  }.min
}.min
p a>1e4?-1:a

angel_p_57 さんの解答を見るともっと鮮やかで (#79137 No.345 最小チワワ問題 - yukicoder) gets.scan(/(?=(c.*?w.*?w))/) で、マッチする部分文字列全てを列挙してしまってる (知らない文法だ).

No.346 チワワ数え上げ問題 - yukicoder

文字 c を見つけたら、それより右方を見て、w を2つ選べば良い. 1つ以下しかなかったら、チワワ列は作れないし、2つ以上あったら、そこから2つ選べるので、  \binom{n}{2} 通りのチワワ列が作れる. 毎回 w の数を数えていると、今回は文字列の長さが { 10^{5} } 程度あって間に合わないので、 初めに全ての w の数を数え上げて、 文字列を舐めながら w の数を更新していけばよい.

すなわち、w の数の総計を W とするとき、 左から文字列をナメていって、 w が出現したら、W をデクリメントし、 c が出現したら、そのときの W を用いて、 \binom{W}{2} を計算して加算すればよい.

s=gets.chomp.chars
w=s.count{|c|c=='w'}
a=0
s.map{|c|
  w-=1 if c=='w'
  a+=w*(w-1)/2 if c=='c'
}
p a