AtCoder ABC #433 : G - Substring Game

参加が遅れたので間に合わないのはまぁしょうがないか…。
https://atcoder.jp/contests/abc433/tasks/abc433_g

問題

文字列Sが与えられる。
ここで2人のターン制ゲームを行う。
文字列Tがあり、初期状態で空である。
各自のターンではTに任意の文字を1文字末尾に加える。ただしその後TはSの部分文字列でなければならない。
手が打てない側は負けである。

両者最適手を打つとき、勝者はどちらか。

解法

win(L,R,n) := すでにTをn文字まで定めたとき、そのn文字は、SのSuffixArrayにおいて[L...R)に相当する開始位置からn文字に等しいとき、勝てるかどうか
とする。これを再帰的に求めよう。
n+1文字目を選んだ時、win(*,*,n+1)がFalseになるような選び方ができれば勝ちとなる。
これは、LCPに対するRMQ+二分探索で、n+1文字目の選び方を定めよう。
なお、SuffixArrayにおいて[L..R)に対応するLCPがnより大きい場合、例えばmである場合、nを1ずつインクリメントすると間に合わないので一気にmまで進めよう。

template<typename ST=string>
struct SuffixArray {
	int N; vector<int> rank,lcp,sa,rsa; ST S;

	void build(ST S){
		this->S=S;
		int i,h=0; vector<int> tmp;
		N=S.size(); rank.resize(N+1); sa.resize(N+1); tmp.resize(N+1);
		FOR(i,N+1) sa[i]=i, rank[i]=i==N?-1:S[i];
		
		for(int k=1; k<=N; k<<=1) {
			auto pred2 = [k,this](int& a,int &b)->bool{ return (((a+k<=N)?rank[a+k]:-1)<((b+k<=N)?rank[b+k]:-1));};
			auto pred = [pred2,k,this](int& a,int &b)->bool{ return (rank[a]!=rank[b])?(rank[a]<rank[b]):pred2(a,b);};
			int x=0;
			if(k!=1) for(i=1;i<N+1;i++) if(rank[sa[i]]!=rank[sa[x]]) sort(sa.begin()+x,sa.begin()+i,pred2), x=i;
			sort(sa.begin()+x,sa.end(),pred);
			FOR(i,N+1) tmp[sa[i]]=(i==0)?0:tmp[sa[i-1]]+pred(sa[i-1],sa[i]);
			swap(rank,tmp);
		}
		lcp.resize(N+1); rsa.resize(N+1);
		FOR(i,N+1) rsa[sa[i]]=i;
		FOR(i,N) {
			int j=sa[rsa[i]-1];
			for(h=max(h-1,0);i+h<N && j+h<N; h++) if(S[j+h]!=S[i+h]) break;
			lcp[rsa[i]-1]=h;
		}
	}
	
};

template<class V,int NV> class RMQ {
private:
	V table[NV+1][1<<NV];
	int LG[1<<NV];
	int NV2;
public:
	static V const def=0;
	V comp(V l,V r){ return min(l,r);};
	RMQ() {
		int i,x;
		NV2=1<<NV;
		LG[1]=0;
		for(i=2;i<NV2;i++) LG[i]=LG[i/2]+1;
		FOR(i,NV) FOR(x,NV2) table[i][x]=def;
	}
	void set(int x,V v){ table[0][x]=v;}
	void build(int MV=-1) { //MVはサイズ指定
		if(MV==-1) MV=NV2;
		int i,j,x,y;
		FOR(i,NV) FOR(x,MV) table[i+1][x]=comp(table[i][x],(x+(1<<i)<MV)?table[i][x+(1<<i)]:def);
	}
	V query(int L,int R) { //[L,R),
		L=max(0,L), R=min(R,NV2);
		if(R<=L) return def;
		int WL=LG[R-L];
		return comp(table[WL][L],table[WL][R-(1<<WL)]);
	}
	
};

RMQ<int,18> rmq;


int T,N;
string S;
SuffixArray<string> sa;
int pat=0;
int win(int L,int R,int len) {
	if(L>=R) return 0;
	if(L+1==R) {
		return (N-(sa.sa[L]+len))%2;
	}
	if(sa.sa[L]+len==N) return win(L+1,R,len);
	
	if(rmq.query(L,R-1)>=len+1) {
		int x=rmq.query(L,R-1);
		return win(L,R,x)^((x-len)%2);
	}
	int TR=L;
	int i;
	for(i=18;i>=0;i--) if(TR+(1<<i)<R-1&&rmq.query(L,TR+(1<<i))>=len+1) TR+=1<<i;
	if(win(L,TR+1,len+1)==0) return 1;
	return win(TR+1,R,len);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>S;
		N=S.size();
		sa.build(S);

		FOR(i,N+1) rmq.set(i,sa.lcp[i]);
		rmq.build(N+1);
		if(win(1,N+1,0)) {
			cout<<"Alice"<<endl;
		}
		else {
			cout<<"Bob"<<endl;
		}
	}
}

まとめ

Suffix Automaton組んだことないんだよな。