SRM 385 250pt: UnderscoreJustification

問題概要

単語が複数与えられる。単語の間にアンダースコアを入れて連結した長さをある値ぴったりにしたい。各単語間にはさまれるアンダースコアの長さの差が高々1になるようにするとき、辞書順最小のものを求める問題。

考えたこと

• 辞書順最小と言えばgreedy。
• アンダースコアの総数はすぐに計算できて、最低何文字いれないといけないかはすぐに分かる。
• 後は余ったものをどこに付けるか考えれば良い。
• 選択の余地がある時に、辞書順でgreedyに選んでやる。

practiceで通ったコード

#include <cctype>
#include <vector>
#include <string>
using namespace std;

struct UnderscoreJustification {

	string justifyLine(vector <string> words, int width) {

		int total = 0, N = words.size();
		for(int i=0; i<N; i++){
			total += words[i].length();
		}

		//余分に使える数と最小数
		int must = (width - total)/(N-1);
		int res = (width - total)%(N-1);

		//解を構成する
		string ret = words[0];
		for(int i=1; i<N; i++){
			int add = 0;
			if(res > (N - 1) - i || (res > 0 && islower(words[i][0])) ){
				add++;
				res--;
			}
			ret += string(must + add, '_') + words[i];
		}
		return ret;
	}

};