PalindromeGame srm 499 div2 hard

問題

http://www.topcoder.com/stat?c=problem_statement&pm=11331

方針

最大の得点を達成するカードの組み合わせの中には、与えられたカードの中で最大の得点を持つカードと、そのカードの文字列を逆にした文字列を持つカードの中で最大の得点を持つカードが必ず含まれる。何故なら、これを満たさない組み合わせがあった時、これを満たすように変更すれば、得点が上がるから。この方針を、素直に実装。

答案

但し、システムテスト通らず。。。

front = { "abc", "cba", "def", "abc", "fed" }
back = { 24, 7, 63, 222, 190 }

のケースでこけた。手元の環境では正しい答えなんだけどなぁ。原因は不明。誰か分かったら教えてください。
2011-03-20 追記 : バグ修正。edgeの初期化時に、falseで埋めるのを忘れていた。

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>



using namespace std;

string reverse(const string& s){
  string ret = s;
  int n = (int)s.size();
  for(int i = 0; i < n; i++){
    ret[i] = s[n - 1 - i];
  }
  return ret;
}

class PalindromeGame{
public:
  int n;
  vector<string> rev;
  vector<vector<bool> > edge;
  vector<bool> used;

  int getMaximum(vector <string> front, vector <int> back){
    n = (int)front.size();
    rev.resize(n);
    for(int i = 0; i < n; i++){
      rev[i] = reverse(front[i]);
    }

    edge.resize(n);
    for(int i = 0; i < n; i++){
      edge[i].resize(n);
      fill(edge[i].begin(), edge[i].end(), false);
    }

    for(int i = 0; i < n; i++){
      for(int j = i + 1; j < n; j++){
	edge[j][i] = edge[i][j] = front[i] == rev[j];
      }
    }

    used.resize(n);
    fill(used.begin(), used.end(), false);

    long long ret = 0;
    while(true){
      printEdge();
      int ii, imax = 0;
      for(int i = 0; i < n; i++){
	if(hasEdge(i) && imax < back[i]){
	  imax = back[i];
	  ii = i;
	}
      }

      if(imax == 0) break;

      int jj, jmax = 0;
      for(int j = 0; j < n; j++){
	if(edge[ii][j] && jmax < back[j]){
	  jmax = back[j];
	  jj = j;
	}
      }

      ret += imax;
      ret += jmax;
      remove(ii);
      remove(jj);
      used[ii] = used[jj] = true;
    }

    int ii, imax = 0;
    for(int i = 0; i < n; i++){
      if(!used[i] && front[i] == rev[i]){
	ii = i;
	imax = max(imax, back[i]);
      }
    }
    if(imax > 0){
      used[ii] = true;
      ret += imax;
    }

    return ret;
  }

  void printEdge(){
    cout << "----" << endl;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
	cout << edge[i][j] << " ";
      }
      cout << endl;
    }
    cout << "----" << endl;
  }

  bool hasEdge(int i){
    for(int j = 0; j < n; j++){ 
      if(edge[i][j]) return true;
    }
    return false;
  }

  void remove(int i){
    fill(edge[i].begin(), edge[i].end(), false);
    for(int j = 0; j < n; j++){
      edge[j][i] = false;
    }
  }


};