TopCoder Open 2014 Round1A Medium EllysScrabble

問題

文字列Sが与えられる。
文字を並べ替えて文字列Tを作る。
Tのそれぞれの文字は、Sの元の場所から距離i以内の場所になければならない。

できる文字列のうち辞書順で最小のものを求めよ。

制約条件

Sの長さ≦50

方針

一文字ずつ決めうちしたときに残りで文字列を作れるか、
二部グラフのマッチングをして解いた。

本当はただの貪欲で解けて、
使える文字のうち辞書順で最小のものを、
複数あれば一番奥のものから使えばよいだけ。

ソースコード

class EllysScrabble {
	public:
	string getMin(string letters, int maxDistance) {
		
		int n = letters.size();
		string ans;
		
		int s = 2 * n, t = 2 * n + 1;
		
		rep(i, n){
			ans += 'A';
			rep(j, 26){
				
				flowGraph g(2 * n + 2);
				
				rep(k, n){
					g.add(s, k, 1);
					for(int l = 0; l <= i; l++)
						if(ans[l] == letters[k] && abs(k-l) <= maxDistance) g.add(k, l + n, 1);
					
					for(int l = i + 1; l < n; l++)
						if(abs(k - l) <= maxDistance) g.add(k, l + n, 1);
					
					g.add(k + n, t, 1);
				}
				if(g.max_flow(s, t) >= n) break;
				
				ans[i]++;
			}
		}
		return ans;
	}
};