AtCoder ARC #058 : F - 文字列大好きいろはちゃん / Iroha Loves Strings

これは手間取った。
http://arc058.contest.atcoder.jp/tasks/arc058_d

問題

N個の文字列S[i]がある。
これらからいくつかを選択し、元の添え字の順で連結してK文字の文字列を作る。
そのような文字列のうち、辞書順最小のものを求めよ。

解法

まずは以下をDPして埋める。f(N,K)=trueから初めて後ろ向きに行えばよい。
f(n,k) := S[0]～S[n-1]までのうちいくつか連結してk文字の文字列が作れるとき、最終的にK文字の文字列を生成可能である。

次に以下を考える。CS(N,K)が求めたい答えである。
CS(n,k) := S[0]～S[n-1]までのうちいくつかを連結して作れるk文字の文字列のうち、辞書順最小のもの。ただしf(n,k)=falseの場合は(以後続けてもK文字にできないので)未定義とする。
この時CS(n,k)が複数のkに対し定義された場合、たとえばCS(n,k)とCS(n,k') (k＜k')があるとき、以下のケースでは片方は不要となる。

• CS(n,k)＜CS(n,k')かつ前者が後者のprefixではない場合、CS(n,k')は不要である。最終的にCS(n,k)に文字列を連結した方が短い文字列のためである。
• CS(n,k)＞CS(n,k')の場合、CS(n,k)は不要である。最終的にCS(n,k')に文字列を連結した方が短い文字列のためである。
• CS(n,k)がCS(n,k')のprefixの場合、どちらも残す

上記処理を複数のCS(n,*)に対して考えると、残すべきは最長のもの(これをCS(n,k)としよう)とそのprefixとして構成されるものである。
よって、以後はCS(n,k)のうち上記条件のもとで最長の文字列を覚えておき、あとはCS(n,k') (k'≦k)がそれぞれ定義されるかどうかだけを覚えておけばよい。
CS(n,*)を求めるには以下の大小判定が必要である。

• CS(n-1,k)の部分文字列
• CS(n-1,k)の部分文字列 + S[n]

上記は先にS[n]+CS(n-1,k)についてZ-Algorithmを適用しておくと上記判定がO(1)で行える。

int N,K;
string S[2020];
string CS[2020];
int can[2020][10101];

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;
}

pair<int,int> getmin(string& t,int a,int b,vector<int>& z,pair<int,int> L,pair<int,int> R) {
	
	//_P("%s : %d %d L:(%d:%d) R:(%d:%d)\n",t.c_str(),a,b,L.first,L.second,R.first,R.second);
	if(L.second==0) {
		int x=z[a+R.first];
		if(x>=a) return L;
		if(a+R.first+x==a+b) return R;
		if(t[x]<t[a+R.first+x]) return R;
		else return L;
	}
	else {
		if(L==R) return L;
		if(L.first>R.first) swap(L,R);
		int x=z[a+L.first];
		if(x>=a) return R;
		if(a+L.first+x==a+b) {
			int d=R.first-L.first;
			int y=z[d];
			if(y>=(a-d)) return R;
			if(t[d+y]<t[y]) return L;
			return R;
		}
		else {
			if(t[x]<t[a+L.first+x]) return L;
			else return R;
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>S[i];
	
	can[N][K]=1;
	for(i=N-1;i>=1;i--) {
		for(j=0;j<=K;j++) {
			can[i][j] |= can[i+1][j];
			if(j>=S[i].size()) can[i][j-S[i].size()] |= can[i+1][j];
		}
	}
	can[0][0]=1;
	
	FOR(i,N) {
		if(i>2) CS[i-2].clear();
		string T=S[i]+CS[i];
		vector<int> Z=Zalgo(T);
		
		pair<int,int> cur={CS[i].size(), 0};
		
		for(j=0;j<=K;j++) if(can[i][j] && j+S[i].size()<=K && can[i+1][j+S[i].size()]) {
			cur=getmin(T,S[i].size(),CS[i].size(),Z,cur,{j,1});
		}
		
		if(cur.second==0) {
			CS[i+1]=CS[i];
			FOR(j,K+1) can[i+1][j] &= can[i][j];
		}
		else {
			CS[i+1]=CS[i].substr(0,cur.first)+S[i];
			FOR(j,K+1) if(can[i+1][j]) {
				if(j>CS[i+1].size()) can[i+1][j]=0;
				if(j<CS[i+1].size()) {
					string tt="{";
					if(can[i][j]) tt=CS[i].substr(0,j);
					if(j>=S[i].size() && can[i][j-S[i].size()]) tt=min(tt,CS[i].substr(0,j-S[i].size())+S[i]);
					if(tt>CS[i+1]) can[i+1][j]=0;
				}
			}
		}
	}
	
	cout<<CS[N]<<endl;
}

まとめ

CS(n,k)とCS(n,k')の間の絞り込みに気づくのが難しい。