AtCoder ABC #240 : Ex - Sequence of Substrings

うーん、最初の一手が思いつかず。
https://atcoder.jp/contests/abc240/tasks/abc240_h

問題

01で構成されたN文字の文字列Sが与えられる。
ここから、互いに抜き出し位置が重複しないよういくつかの部分文字列を抜き出したい。
これらの部分文字列を、元のSにおける登場位置の順に並べたときに、各部分文字列が昇順となるようにしたい。

最大何個の部分文字列を抜き出せるか。

解法

無駄に長い部分文字列をとっても得しないので、n個目の部分文字列の長さは、高々(n-1)個目の文字列の長さ+1であり、結局その長さはnである。
つまり、O(√N)より長い部分文字列を取る必要はない。
そこで、O(√N)以下の部分文字列を列挙し、ソートしよう。
これはTrie木をDFSするような感じでソートできる。

あとは、以下の配列を更新していく。
f(n) := Sのn文字目までのうち、最大で抜き出せる部分文字列数の最大

上記の部分文字列を小さい順にみて行き、今S[L...R]を見ているとするならば、f(R)はmax(f(0)....f(L-1))+1で更新できる。

int N;
string S;

vector<pair<int,int>> cand;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(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<int,1<<18> st;

void dfs(vector<int> V,int len) {
	if(len>730||V.empty()) return;
	FORR(v,V) {
		cand.push_back({v-len+1,v});
	}
	
	vector<int> W[2];
	FORR(v,V) if(v+1<N) W[S[v+1]-'0'].push_back(v+1);
	int i;
	FOR(i,2) dfs(W[i],len+1);
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	vector<int> V[2];
	for(i=N-1;i>=0;i--) V[S[i]-'0'].push_back(i);
	FOR(i,2) dfs(V[i],1);
	
	int ma=0;
	FORR2(L,R,cand) {
		x=st.getval(0,L)+1;
		ma=max(ma,x);
		st.update(R,x);
	}
	cout<<ma<<endl;
	
}

まとめ

長さO(√N)まで考えればいいことに至らなかったのが敗因。