読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

SRM499 Div2 hard PalindromeGame

SRM

問題概要:
n枚のカードが与えられる (1 <= n <= 50)
n枚のカードにはそれぞれ表に文字列、裏に数字が書いてある(文字列の長さは全て同じ)
このn枚のカードの中から適当にカードを選びつなげた時の文字列が回文となっているものの中でそれらのカードの裏の数字の和が最大になるようにせよ
返す値は数字の和だけで良い


解法;
練習でやってみた時には解けなかったので後々topcoderの解説を読んで解いた

簡単に説明すると、
組み合わせると回文になるカードのペアを数字の和が最大になるようにしてまとめておく
まだペアになっていないもののうち、そのカードだけで回文となっているものの中でもっとも数字が大きいものを選ぶ
これらの手順で選ばれたカードの数字の和が答えとなる

三枚以上のカードをまとめて回文をつくる場合、回文となるカードのペアと(存在するのであれば)そのカードだけで回文となるものを組み合わせて回文をつくる
というかそれ以外では作れない(この問題では文字列のカードの長さがすべて同じなため)
なので、"abc" "def" "cba" "fed" "oo" のような文字列があたえられた時は
"abc"と"cba","def"と"fed","oo"単体というようにわけておくことで

abc def oo fed cba とか、
def abc oo cba fed みたいにして回文を作ることができる


手順としては、
1.pairやら構造体やらでfrontとbackを一緒にしておく(降順にソートするため)
2.降順にソート
3.2重ループで文字列のペアをつくる(降順ソートしてあるので一番最初にみつかった回文となるペアが数字の和を最大にする)
4.再度ループして、まだペアになってない && それ単体で回文になるもののなかで最大の数字をもつものの数字を答えに加える(存在しないならなにもしない)

となる

コード:

struct Pox
{
  string f;
  int b;
  Pox(string f="$",int b=-1):f(f),b(b){}
  bool operator < (const Pox &a)const
  {
    return b > a.b;
  }
};

class PalindromeGame {
	public:


	int getMaximum(vector <string> front, vector <int> back) {
	  int n = front.size();
	  vector<Pox> vec;
	  rep(i,n)vec.push_back(Pox(front[i],back[i]));
	  sort(all(vec));
	  int sum = 0;
	  bool used[n];
	  rep(i,n)used[i] = false;

	  rep(i,n)
	    {
	      if(used[i])continue;
	      REP(j,i+1,n)
		{
		  if(used[j])continue;
		  string rev = string(vec[j].f.rbegin(),vec[j].f.rend());
		  if(rev != vec[i].f)continue;	  
		  used[i] = used[j] = true;
		  sum += vec[i].b + vec[j].b;
		  break;
		}
	    }

	  rep(i,n)
	    {
	      if(used[i])continue;
	      string rev = string(vec[i].f.rbegin(),vec[i].f.rend());
	      if(rev != vec[i].f)continue;
	      sum += vec[i].b;
	      break;
	    }

	  return sum;
	}
};