Codeforces 137 E. Last Chance
問題
文字列が与えられる。
この文字列の連続する部分文字列で、母音の数が子音の数の2倍以下であるようなものを、goodなsubstringという。
goodなsubstringで、長さ最長のものの長さおよび、その長さのgoodなsubstringが現れる回数を求めよ。
制約条件
文字列の長さ≦2*10^5
方針
尺取法。
a[i]をi文字目が母音のとき-1,子音のとき+2とする。
s[i]をa[i]の累積和とする。
すると、s[i]-s[j]≧0となることが、文字列のj文字目からi文字目がgoodなsubstringになることに対応する。
各jに対してs[i]-s[j]≧0になるような最も大きいiを求められればよい。
これは、(s[i],i),(-s[j],j)をあらかじめソートしておくことによりできる。
-s[j]は小さい順に、s[i]は大きい順に見て、
-s[j]+s[i]≧0の間iを小さくしつづけて、その中でのiのインデックスの最大値を取る。
これを繰り返して、goodなsubstringの長さの最大値およびその個数を求めればよい。
ソースコード
int n,a[200001],s[200001]; string in; void run() { cin>>in; n=in.size(); rep(i,n){ char c=tolower(in[i]); if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')a[i]=-1; else a[i]=2; } s[0]=0; rep(i,n)s[i+1]=s[i]+a[i]; vector<pi> M,P; rep(i,n+1){ M.pb(mp(-s[i],i)); P.pb(mp(s[i],i)); } sort(all(M)); sort(all(P)); int i=0,j=n,len=0,ans=0; set<int> s; for(;i<=n;i++){ while(j>=0&&P[j].first+M[i].first>=0)s.insert(-P[j--].second); if(-*s.begin()-M[i].second>len)len=-*s.begin()-M[i].second,ans=0; if(-*s.begin()-M[i].second==len)ans++; } if(len==0)cout<<"No solution"<<endl; else cout<<len<<" "<<ans<<endl; }