TopCoder SRM 385 Div1 Easy UnderscoreJustification

問題

n個の単語を、幅w文字になるよう単語と単語の間に"_"を入れて一行に書きたい。
それぞれの単語と単語の間の"?"の数はなるべく均等になるようにしたい。
（すなわち、最も多い"_"と最も少ない"_"の差が1以下になるようにしたい）

それが複数ある場合、辞書順で最小になるものを選ぶ。
"_"を入れて、単語を幅wになるように並べて書いたものを出力せよ。

先頭の単語の前および、最後の単語の後ろには"_"を入れることはできない。
また、"_"は文字コードで、大文字よりも後に来て、小文字よりも前に来る。

制約条件

n≦10
w≦200

方針

greedy.
入れるべきスペースの数をmとすると、
m/(n-1)個ずつ単語間にスペースを入れるのはきまっていて、
残りのm%(n-1)個をどこに入れるかが問題になる。

これは、なるべく小文字の単語の前で、
次に大文字の単語の前に入れるように貪欲に選べばいい。
小文字の単語は、前にあるものから順に優先的に、大文字の単語は後ろにあるものから優先的に前にスペースを入れる。

ソースコード

class UnderscoreJustification {
  public:
  string justifyLine(vector <string> words, int width) {
    int n=words.size();
    vi sml,big,spc(n-1);
    for(int i=1;i<n;i++)if(islower(words[i][0]))sml.pb(i);
    else big.pb(i);
    reverse(all(big));
    sml.insert(sml.end(),all(big));
    
    rep(i,n)width-=words[i].size();
    rep(i,width%(n-1))spc[sml[i]-1]++;
    stringstream ss;
    ss<<words[0];
    rep(i,n-1){
      rep(j,spc[i]+width/(n-1))ss<<"_";
      ss<<words[i+1];
    }
    return ss.str();
  }
};