AtCoder ARC #077 : F - SS

あと1歩だったのに妙な勘違いで落とした。
http://arc077.contest.atcoder.jp/tasks/arc077_d

問題

偶文字列とは、同じ文字列を2回繰り返した形の文字列を指す。
文字列Sに対するf(S)とは、Sに最低1文字以上加えて生成できる偶文字列のうち最短のものを指す。

Sにfを大量に適用させた後できる文字列Tにおいて、T[L..R]中に各アルファベットが何回出るかを求めよ。

解法

T[1..R]中のアルファベット登場回数からT[1..(L-1)]の値を引けば解が求められるので、正整数Vに対し結局T[1..V]のアルファベット登場回数がわかればよい。

まずはSにfを適用させるとどうなるか2回ほど試してみよう。
これはZalgorithm等でO(|S|)で処理できる。

以後、S(i) = f^i(S)と表現する。
厳密な証明はEditorialに任せるとして、以下の2通りのケースが生じる。

• |S(0)|,|S(1)|,|S(2)|が等差数列になる
  • この場合、S(inf)はS(0)を繰り返した形になるため、周期性からT[1..V]のアルファベット登場回数は容易に求められる。
• |S(0)|,|S(1)|,|S(2)|がフィボナッチ数列を成す
  • この場合、以後|S(i)|はフィボナッチ数列を成す
  • S(i)の具体的な形は求めなくても、S(i)における各アルファベットcの登場回数C(i,c)はフィボナッチ数列を成すので、先にこれらを求めておこう。
  • V=|S(i)|となるiがある
    • この場合前述のC(i,c)を答えればよい。
  • S(i)＜V＜S(i+1)となるiがある
    • S(i+1)は、S(i)のうち前半(|S(i)|+|S(i-1)|)/2 (もしくは|S(i)|-|S(i-2)|/2)を繰り返したものである。
    • よって、まず解にその前半分C(i,c)-C(i-2,c)/2分を加算したうえで、V -= |S(i)|-|S(i-2)|/2と前半分の分長さを減らしていけばよい。

string S[3];
ll L,R;
ll cnt[103][28];
ll dif[103][28];


vector<int> Zalgo(string s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	v.push_back(0);
	return v;
}
string nex(string S) {
	vector<int> V=Zalgo(S);
	
	int l;
	for(l=S.size()/2-1;l>=0;l--) {
		if(V[S.size()-l]>=l) return S.substr(0,S.size()-l)+S.substr(0,S.size()-l);
	}
}
vector<ll> hoge(ll v) {
	vector<ll> ret(26,0);
	int i;
	FOR(i,26) ret[i] = v/S[0].size()*cnt[0][i];
	v%=S[0].size();
	FOR(i,v) ret[S[0][i]-'a']++;
	return ret;
}

vector<ll> hoge2(ll V) {
	vector<ll> ret(26,0);
	int i,j;
	for(i=99;i>=2;i--) {
		if(V>=cnt[i][26]) {
			FOR(j,26) ret[j]+=cnt[i][j]-cnt[i-2][j]/2;
			V-=cnt[i][26]-cnt[i-2][26]/2;
		}
	}
	FOR(i,V) ret[S[2][i]-'a']++;
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S[0]>>L>>R;
	S[1]=nex(S[0]);
	S[2]=nex(S[1]);
	
	FORR(r,S[0]) cnt[0][r-'a']++;
	FORR(r,S[1]) cnt[1][r-'a']++;
	cnt[0][26]=S[0].size();
	cnt[1][26]=S[1].size();
	
	vector<ll> LL,RR;
	if(S[0].size()+S[2].size()==2*S[1].size()) {
		RR=hoge(R);
		LL=hoge(L-1);
	}
	else {
		for(i=2;i<=100;i++) {
			FOR(j,27) {
				cnt[i][j] = min(1LL<<60,cnt[i-1][j]+cnt[i-2][j]);
			}
		}
		RR=hoge2(R);
		LL=hoge2(L-1);
	}
	FOR(i,26) _P("%lld%c",RR[i]-LL[i],(i==25)?'\n':' ');
	
}

まとめ

S(i)とS(i+1)の関係を間違えてしまいACできず。