TopCoder SRM 634 Div2 Hard SpecialStrings

なかなか面白い問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13233

問題

文字列が以下の条件を満たすときspecialであるという。

• '0'と'1'で構成される。
• Sを前半後半の空でない２つの部分文字列に分けたとき、分割位置に依らず前半の方が辞書順で前に来る。

specialな文字列Sが与えられる。
辞書順でSの次に来るspecialな文字列Tを答えよ。

解法

先に面倒なのでSをインクリメントしておく。
すると「Sの次に来るspecialな文字列T」ではなく「S以上で辞書順最小なspecial文字列T」を答える問題となる。

辞書順最小を目指すので、前から順に決めていく。
T=xxxxyyyyでxxxxまでの部分はspecialである、すなわちx < xxxyyyy、xx < xxyyyy、xxx < xyyyy、xxxx < yyyyを満たしているなら、T=xxxx1111は必ずspecialであることを利用する。

例えば上の数文字が確定してT=xxxx????とする。

出来れば辞書順最小にしたいので、T=xxxx0111と仮置きする。
この時、

• 先頭部分のxxxx0は、同じ長さのSのprefixと等しいか、辞書順で後である。
• T=xxxx0111はspecialである

の両方を満たすなら、Tの5文字目は0で確定し、T=xxxx0????として残りの桁を決める。
条件を満たさないなら、Tの5文字目は1を取るしかなく、T=xxxx0????として残りの桁を決める。

class SpecialStrings {
	public:
	string S,goal;
	string next(string s) {
		int i;
		for(i=s.size()-1;i>=0;i--) {
			s[i]++;
			if(s[i]<='1') break;
			s[i]='0';
		}
		return s;
	}
	bool issp(string s) {
		int i,L=s.size();
		for(i=1;i<L;i++) if(s.substr(0,i)>=s.substr(i)) return false;
		return true;
	}
	void dfs(string cur) {
		if(cur.size()==S.size()) {
			if(goal>cur && issp(cur)) goal=cur;
			return;
		}
		
		string n=cur+"01111111111111111111111111111111111111111111111111111111";
		n=n.substr(0,S.size());
		if(n.substr(0,cur.size()+1)>=S.substr(0,cur.size()+1)) {
			if(issp(n)) {
				dfs(cur+"0");
				return;
			}
		}
		dfs(cur+"1");
	}
	
	string findNext(string s) {
		if(s=="1") return "";
		S=next(s);
		goal="11111111111111111111111111111111111111111111111111111";
		dfs("");
		if(goal.size()>50) return "";
		return goal;
	}
}

まとめ

辞書順最小では「とりあえずこの桁に小さい文字を選べば、後ろは最悪のケースでもなんとかなるなら、その文字を選んでしまう」という手法はしばしば利用できるね。
B: 辞書式順序 - AtCoder Beginner Contest #007 | AtCoder
これとかね。