TopCoder SRM 689 Easy: ColorfulGarden

考慮漏れがあったせいで落とした悔しい問題。こいつのせいで青コーダーに落とされた記念すべき問題。修行し直します。

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14243
2行n列のセルにa～zのアルファベットが並べられている。これらを並べ替えることで隣接セルが同じアルファベットとならないようにせよ。
もしそのような並べ方ができない場合は要素数0のベクトルを返せ

考えたこと (若干の間違いあり)

隣接セルが同頑張っても同じアルファベットになってしまうケースってどんなとき？と考えた。
例えば2*3セルの場合、aが3つまでは
a?a
?a?
みたいな起き方をすれば隣接しない(つまり、何らかのアルファベットが列数よりも多く存在する場合は詰む)。
よって、アルファベットをソートして後、大体以下の様な順番で埋めていけば良さそうである。
1638
5274

間違っていた点

よくよく見ていたらレッドコーダーの人がresubmitしているし嫌な予感……とおもいつつ時間内に穴が見つからず。
チャレンジフェーズで落とされた。
もっとよくよく考えると、列数と同じ個数存在するアルファベットは真っ先に処理しないといけない点が抜けていた。
例えば、2*3のセルで、アルファベットがabbbccだとすると、並べ替えた結果は以下のようになる。
acb
bbc

つまり、アルファベットの個数が多い順に埋めてやる必要があった（本当は上にも書いたとおり、最大のやつだけ気を配れば良いのだけども)

コード

vector <string> rearrange(vector <string> garden) {
   vector<string> invalid;
   int size = garden[0].size();
   int cnt[30];
   memset(cnt,0,sizeof(cnt));
   for( int i = 0 ; i < 2; i++ ){
      for( int j =0 ; j < size; j++ ){
         cnt[garden[i][j]-'a']++;
         if( cnt[garden[i][j]-'a'] > size ){
            return invalid;
         }
      }
   }
   vector<pair<int,char> > vec;
   for( char c= 'a'; c <='z' ; c++ ){
      vec.push_back( make_pair(cnt[c-'a'],c));
   }
   sort(vec.begin(),vec.end());
   string s = "";
   for( int i= 0; i < (int)vec.size(); i++ ){
      s+=string(vec[i].first,vec[i].second);
   }
   vector<string> ret(2,garden[0]);
   for( int i = 0 ; i < size*2; i++ ){
      if( i<size ) ret[i%2][i]=s[i];
      else ret[(i-size+1)%2][i-size]=s[i];
   }
   return ret;
}