SRM 499 Div2 Hard PalindromeGame

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11331&rd=14428

vector string が与えられる。各文字列の長さは等しい。各文字列には点数が割り当てられており、この文字列から複数を取り出してそれらを任意の順で結合した文字列がもし回文となるなら、取り出した文字列の点数の合計が得点となる。得点を最大化せよ。

やりかた

貪欲。
すべての文字列が同じ長さというのがミソ。同じ長さでないと abc + bbcb + a のような３つ以上の文字列を結合しないと回文にならないというケースが考えられるが、同じ長さであればそういったことは起きない。つまり、回文になるならabb + bba のようにかならず線対称な２つの（もしくは１つの）文字列で回文の最小要素が作れ、その他の回文もこれらの組み合わせで作れる。

なので、ある文字列に対して与えられた文字列中で、１．同じ文字列なもの、２．くっつけると回文になるもののリストを持っておく。２．については下図参照。

こんなかんじで組み合わせて、点数の高い順から一ペアずつ回文を作っていく。

特殊なのは、１．その文字列のみで回文になる時で、ある文字列に対してそれが複数種類あるとする。（たとえばaaaという文字列が複数あるとする。）もしその文字列が偶数あるなら、...aaa......aaa...という感じで中心から等距離に文字列を配置できる。ただし、奇数あるものについては得点の高い順に２つずつくっつけていって、のこった単体回文文字列中最も得点の高い文字列を中心に据えるという形にすればいい。

以下ソース。

class PalindromeGame {
public:
  bool isPal(string s){
    string ss = s;
    reverse(ALL(ss));
    return ss == s;
  }
  int getMaximum(vector <string> front, vector <int> back) {
    int N = front.size();
    map<string, vector<int> > m;
    for(int i = 0; i < N; i++) m[front[i]].push_back(back[i]);
    for(int i = 0; i < N; i++) sort(ALL(m[front[i]]), greater<int>());

    map<string, vector<int> >::iterator it = m.end(), i = m.end(), j = m.end(), k = m.end();
    int maxv = 0;

    int res = 0;
    for(j = m.begin(); j != m.end(); j++){
      for(k = j; k != m.end(); k++){
	if(j == k) continue;
	string s = j->first;
	reverse(ALL(s));
	if(s == k->first){
	  int cnt = min((j->second).size(), (k->second).size());
	  for(int a = 0; a < cnt; a++)
	    res += (j->second)[a] + (k->second)[a];
	}
      }
    }

    for(j = m.begin(); j != m.end(); j++)
      if(isPal(j->first)){
	for(int a = 0; a < (int)(j->second).size() / 2 * 2; a++)
	  res += (j->second)[a];
      }


    for(it = m.begin(); it != m.end(); it++) {
      if(isPal(it->first) && (it->second).size() % 2){
	int cnt = (it->second).size();
	if(maxv < (it->second)[cnt - 1]){
	  maxv = (it->second)[cnt - 1];
	  i = it;
	}
      }
    }
    if(i != m.end()){
      int cnt = (i->second).size();
      res += (i->second)[cnt - 1];
    }

    return res;
  }
};

以前書いたソース。↓

class PalindromeGame {
public:
  string inv(string s){
    reverse(ALL(s));
    return s;
  }
  int getMaximum(vector <string> front, vector <int> back) {
    int N = front.size();
    bool used[50];
    fill(used, used + 50, false);
    vector<int> pairs[100];
    map<string, vector<int> > single;
    
    int cnt = 0;
    //２つあわせて回文という文字列をピックアップ
    for(int i = 0; i < N; i++){
      if(used[i]) continue;
      //単体で回分という文字列は除外
      if(front[i] == inv(front[i])){
	single[front[i]].push_back(back[i]);
	continue;
      }
      
      used[i] = true;
      pairs[cnt].push_back(back[i]);
      for(int j = i + 1; j < N; j++){
	if(used[j]) continue;
	cout << front[i] << " " << front[j] << endl;
	if(front[i] == front[j]){
	  pairs[cnt].push_back(back[j]);
	  used[j] = true;
	}else if(front[i] == inv(front[j])){
	  pairs[cnt + 1].push_back(back[j]);
	  used[j]  = true;
	}
      }
      cnt += 2;
    }
    //２つあわせて回文というもので、得点が高い順にペアにしていく
    int ans = 0;
    for(int i = 0; i < 100; i++)
      sort(ALL(pairs[i]), greater<int>());
    for(int i = 0; i < 100; i += 2){
      int n = min(pairs[i].size(), pairs[i + 1].size());      
      for(int j = 0; j < n; j++) ans += (pairs[i][j] + pairs[i + 1][j]);
    }
    //単体で回文なもの
    int center = 0;
    for(map<string, vector<int> >::iterator it = single.begin(); it != single.end(); it++){
      sort(ALL((*it).second));
      ans += accumulate(ALL((*it).second), 0);
      if((*it).second.size() % 2 == 1){
	ans -= (*it).second[0];
	center = max(center, (*it).second[0]);
      }
    }
    return ans + center;
  }
};

多少実装が面倒。
vector int pairs の配列数を少なく見積もっていて、WAをもらった。直したらACだった。少しずつDiv2Hardにも慣れていると信じたい。