TopCoder SRM 701 Div1 Medium KthStringAgain

このDPは思いつかなかった。
https://community.topcoder.com/stat?c=problem_statement&pm=14414

問題

アルファベット小文字で構成される文字列Sに対し、1～|S|の各整数の部分集合Mがあるとする。
M中の要素を小さい順に取り出すことを考える。
取り出しが要素がaの時、Sの末尾a文字を反転させる。

Mの取り方を2^|S|通り総当たりし、それぞれ上記処理により得られる2^|S|個の文字列を考える。
そのうち辞書順でK番目になる文字列を答えよ。

解法

辞書順で答える問題なので、定番のテクが使える。
解の候補の文字列として、試しにa,b,c...を末尾に加えてみて、その文字をprefixとする文字がK番以内に入るかどうか判定し、K番以内に入る最後の文字を順次加えていくテクが使える。
あとは、文字列Sと解の候補Pに対し、Sに上記処理を適用してPがprefixになる数を数えればよい。

そもそもこの処理が何をやっているかを整理する。
S中の文字を幾つか選択し、それらを取り除く。
そして取り除いた文字を逆順で連結し、(文字を取り除いた後の残った)Sの末尾に加える処理に相当する。
Mの取り方は、実質Sのどの文字を取り除くかに1対1で対応する。

以下の状態を考える。
dp(i,x) := Sの先頭i文字のうち、x文字残してある。またそのx文字はPとprefixが一致する。そのような残し方の組み合わせ。

• i文字目をSに残せるのは、S[i]==P[x]またはx＞|P|の場合。その場合dp(i+1,x+1) += dp(i,x)となる。
• i文字目を取り除けるのは、i文字目を後ろに回した場合、最終的にその文字はr=(|S|-1)-(i-x)文字目に来る。
  • よってS[i]==P[r]またはr＞|P|の場合で、dp(i+1,x) += dp(i,x)となる。

class KthStringAgain {
	public:
	
	ll dpdp(string a,string b) {
		int i,j;
		ll dp[52][52] = {};
		dp[0][0]=1;
		FOR(i,a.size()) {
			FOR(j,i+1) {
				//front
				if(j>=b.size() || (j<b.size() && a[i]==b[j])) dp[i+1][j+1] += dp[i][j];
				//end
				int r=(a.size()-1)-(i-j);
				if(r>=b.size() || (r<b.size() && a[i]==b[r])) dp[i+1][j] += dp[i][j];
			}
		}
		return accumulate(dp[a.size()],dp[a.size()]+a.size()+1,0LL);
	}
	
	string getKth(string s, long long K) {
		string ret;
		int i,j;
		FOR(i,s.size()) {
			FOR(j,26) {
				string tret=ret;
				tret+='a'+j;
				ll t=dpdp(s,tret);
				if(K>t) {
					K-=t;
				}
				else {
					ret=tret;
					break;
				}
			}
		}
		
		return ret;
		
	}
}

まとめ

後ろに回した場合のDPの処理が思いつかなかった。
後ろに回す場合もそういえば位置が確定するんだったな。