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

■■■問題■■■

最近Cさんにはチワワ成分が不足しています。
そこで文字列からたくさんのチワワを見つけることにしました。
Cさんは "cww" という文字列をチワワとして認識します。

文字列Sが与えられるので、
その部分列(連続でなくとも構わない)の中でチワワとなるものの総数を求めてください。 

■■■入力■■■

S

1行目に文字列S(1 <= |S| <= 10万)が与えられる。
Sは小文字のアルファベットのみで構成される。 

■■■出力■■■

Sの部分列(連続でなくとも構わない)の中でチワワとなるものの総数を整数で出力してください。
最後に改行してください。 

C#のソース

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("chiwachiwachiwawaparadise");
            //10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("yeswecan");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("cwcwcwwwcccccccccccwwwww");
            //219
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];

        long AnswerCnt = 0;
        long CntW = 0;
        for (int I = S.Length - 1; 0 <= I; I--) {
            if (S[I] == 'w') CntW++;
            if (S[I] == 'c') {
                if (CntW >= 2) {
                    AnswerCnt += CntW * (CntW - 1) / 2;
                }
            }
        }
        Console.WriteLine(AnswerCnt);
    }
}

解説

文字列を逆から走査して、cを発見したら、(それまでのwの数)C2 を計上してます。