TopCoderOpen 2014 Round1A Medium EllysScrabble

本番解法を決めるまでは時間がかかったけど、後は実装は簡単。
http://community.topcoder.com/stat?c=problem_statement&pm=12974

問題

文字列Lと最長距離Dが与えられる。

文字列L中の文字列をソートしてできる辞書順最小の文字列を答えよ。
ただし、ソートにおける各文字は元の位置からD文字以下しか移動できない。

解法

答えの文字列を頭から決めていく。
i文字目を決める際は(i-D)～(i+D)文字目のうち最小かつ未使用で一番左にあるものを選べばよい。
ただし(i-D)文字がまだ使われていない場合は、それを優先して使う。

class EllysScrabble {
	public:
	string getMin(string letters, int maxDistance) {
		int L=letters.size();
		int i,j,x,y;
		int vis[51];
		string S;
		ZERO(vis);
		
		FOR(x,L) {
			if(x-maxDistance>=0 && vis[x-maxDistance]==0) {
				S+=letters[x-maxDistance];
				vis[x-maxDistance]++;
				continue;
			}
			int be=-1;
			FOR(y,L) if(abs(y-x)<=maxDistance && vis[y]==0) {
				if(be==-1 || letters[y]<letters[be]) be=y;
			}
			S+=letters[be];
			vis[be]++;
		}
		return S;
	}
};

まとめ

本番最初フローかな？と思って解法決めるのに時間がかかってしまった。