kmjp's blog

競技プログラミング参加記です

TopCoder SRM 526.5 Div2 Hard MagicNaming

偶然解けたけど後で説明見てびっくり。
http://community.topcoder.com/stat?c=problem_statement&pm=11674

問題

何匹かのトナカイの名前を連結して魔法の文字列を生成した。
この文字列は、トナカイの名前から生成できる文字列のうち辞書順で最小のものである。

魔法の文字列を構成できる最大のトナカイの数を答えよ。

解法

名前が辞書順であることは、生成できる文字列が辞書順を意味しないことに注意。
例えばpretestにあるとおり、"r" < "ri"であっても"ri+"r"="rir" < "rri" = "r"+"ri" となるため名前順と生成文字列順は異なる。

なお、ここで仮に文字列A+B+C+DがA~Dから生成できる辞書順最小の文字列であるとき、ここにEを加えるとD + E < E + Dであれば、A~Eから生成できる文字列はA+B+C+D+Eが辞書順最小になる。
そこで、魔法の文字列のうち、今まで処理したうち末尾のsubsutringを保持してDPを行い、分割数を最大最大化すればよい。

自分はたまたまD+E

class MagicNaming {
	public:
	string st[52][52];
	int dp[52][52];
	int maxReindeers(string magicName) {
		magicName="@"+magicName;
		int N=magicName.size();
		int x,y,l,z;
		FOR(x,N) for(y=1;x+y<=N;y++) st[x][y]=magicName.substr(x,y);
		
		ZERO(dp);
		dp[0][1]=1;
		for(x=0;x<N;x++) for(y=1;x+y<N;y++) {
			if(dp[x][y]==0) continue;
			z=x+y;
			for(l=1;z+l<=N;l++) {
				if(st[x][y]+st[z][l]<=st[z][l]+st[x][y]) dp[z][l]=max(dp[z][l],dp[x][y]+1);
			}
		}
		
		int ret=0;
		FOR(x,N) ret=max(ret,dp[x][N-x]);
		return ret-1;
		
	}
};

まとめ

<-の推移律の証明、自分で思いつかなかったけどEditorialを見て感動した。
この連結後辞書順最小ならf(x)が最小っていう特性は他でも使えそうだな。
これ有名な特性なのかな。