ICPC2012 国内予選直前対策会議 TUATなのかTATなのか

ICPC国内予選直前対策会議(http://atnd.org/events/30281)にて、ペアプログラミングのグループ分けに利用した問題です。

簡単な問題ですが、問題文をちょっとわかりにくくしています。
(サンプルを弄るとすぐわかると思います)

問題 TUATかTATなのか

東京農工大学という大学があるらしい、そこではTUATやTATといった略称を用いるそうだ。
そこで我々は、TUATとTATどちらが頻繁に用いられているか調査しようと思う。

a-zA-Zで構成されるn個の文字列が与えられて、その中にTUATおよびTATがそれぞれ何個含まれているか調査する。
ただし、同じ略称が繋がっている場合は何か深い意味があるとして繋がった回数だけ重みを回数の2乗に増やそうと思う。
たとえば、TATATならば5回、TATATATならば14回現れたこととするが、TATTATは繋がっていないとして2回現れたとする。

また、0<=n<1000かつ1つの文字列の長さは1以上10000以下として，大文字小文字は区別しない．

input	output
n S1 S2 … Sn ただし、n=0の時終了	S1のTUATの数 S1のTATの数 S2のTUATの数 S2のTATの数 … … … … SnのTUATの数 SnのTATの数

sample input	sample output
5 tuatTUATtat tatatat tuatATat tuaatHaaatat hatuatuat 0	2 1 0 14 1 5 0 1 5 0

解法

色々な解法があると思いますが、無駄に配列を使った解を紹介します。

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)

typedef long long int ll;

const int MAXN=10012;
int tuat[MAXN],tat[MAXN];

int main()
{
    int n; while(cin>>n&&n) REP(k,n)
    {
        memset(tuat,0,sizeof(tuat));
        memset(tat,0,sizeof(tat));

        string s; cin>>s; rep(s.size()) s[i]=tolower(s[i]);

        ll ans1=0,ans2=0;

        rep(s.size()-2) if(s[i]=='t'&&s[i+1]=='a'&&s[i+2]=='t')
        {
            tat[i+2]=tat[i]+1;
            ans1 += ll(tat[i+2])*ll(tat[i+2]);
        }

        rep(s.size()-3) if(s[i]=='t'&&s[i+1]=='u'&&s[i+2]=='a'&&s[i+3]=='t')
        {
            tuat[i+2]=tuat[i]+1;
            ans2 += ll(tuat[i+2])*ll(tuat[i+2]);
        }


        cout<<ans2<<" "<<ans1<<endl;
    }

    return 0;
}

本当はもっとDP的な問題にしたかったんですけどねえ