これは割とあてずっぽうで行ってしまった。
https://codeforces.com/contest/1168/problem/B
問題
01で構成される文字列が与えられる。
区間[L,R]のうちに、0または1が等間隔で3つ並んでいるようなものは何通りか。
解法
実験してみると、ある程度の長さになると、必ず条件を満たす文字列ができる。
実際には9文字以上だと必ず存在する。
よって、Lに対して条件を満たさない最寄のRは8文字以内に現れるはずなので、適当に探索しても間に合う。
以下では一応50文字程度まで探している。
template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=1LL<<60; V comp(V l,V r){ return min(l,r);}; SegTree_1(){val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y if(r<=x || y<=l) return def; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=comp(v,val[entry]); while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_1<ll,1<<20> st; int N; string S; int R[303030]; void solve() { int i,j,k,l,r,x,y; string s; cin>>S; N=S.size(); FOR(i,N+10) R[i]=N; FOR(i,N) { for(x=1;x<=50;x++) if(i-x>=0 && i+x<N) { if(S[i]==S[i-x]&&S[i]==S[i+x]) R[i-x]=min(R[i-x],i+x); } } FOR(i,N+10) st.update(i,R[i]); ll ret=0; FOR(i,N) { x=st.getval(i,N+1); ret+=N-x; } cout<<ret<<endl; }
まとめ
これもまだ5月分か…。