TopCoder SRM 649 Div1 Easy Decipherability

SRM649に参加。
Easy, Medium共に結構早解きができ、2Hackも加えてなかなかの高順位でした。
あとはHardが解ければなぁ。
http://community.topcoder.com/stat?c=problem_statement&pm=13656

問題

L文字の文字列Sがあり、(L-K)文字を取り除きK文字にする。
残したK文字の文字列から、取り除いた(L-K)文字の位置を特定できないような取り除き方は可能か。

解法

DPによる解法と、条件を満たす文字の取り除き方を求める方法がある。
自分は後者で回答。

L==Kの時は全文字取り除くこと確定なので、条件を満たす取り除き方は存在しない。
それ以外の場合、どういう場合に条件を満たす取り除きかたができるか。

２つの同じ文字が間にp文字挟まっている状態を考える。
例えばAとAの間に4文字挟まったA----Aといった部分文字列を仮定する。
この時、A----または----A５文字を取り除くと、残されたAがもともと左右どちらのものか特定できなくなる。

上記推論より、S[i]==S[j]かつj-i≦Kとなるi,jが存在すれば、条件を満たす取り除き方が可能である。

class Decipherability {
	public:
	string check(string s, int K) {
		int L=s.size();
		int x,y;
		FOR(y,L) FOR(x,y) if(s[x]==s[y] && L!=K && y-x<=K) return "Uncertain";
		return "Certain";
	}
}

まとめ

考察が済むとコード自体はあっさり。
本番こんなO(L^2)で良いかちょっと不安で、O(L^3)解があるんじゃないかと思ったけど、通ってよかった。