naoya_t@topcoder

SRM385 Div1 Easy: UnderscoreJustification

過去問, 練習 | 23:10 |

これは速解き系なんだろうな。

最近、慣れてきたのかコードが汚くなってきた。（スペースの数が減ったりとか）

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())

class UnderscoreJustification {
 public:
  string justifyLine(vector<string> words, int width) {
    int n=words.size(), gaps=n-1, len=0;
    tr(words,it)len+=it->length();
    int minspaces=len+gaps, ds=width-minspaces, dsall=1+ds/gaps,dsr=ds%gaps;
    int cn=1<<gaps;
    vector<string> candidates(cn,"");
    rep(i,cn) {
      if(__builtin_popcount(i)!=dsr) continue;
      stringstream ss;
      ss << words[0];
      for(int j=1,b=1;j<=gaps;j++,b<<=1){
        string s_(dsall+((i&b)?1:0), '_'); // dsall+ の後の括弧がなくて結果が短くなるのでおかしいなと暫く悩んだ
        ss << s_ << words[j];
      }
      candidates[i] = ss.str();
    }
    remove_(candidates,"");
    sort(all(candidates));
    return candidates[0];
  }
};