SRM 512 Div2 Hard DoubleRoshambo

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=11289&rd=14537
AとBが両手でじゃんけんをする。

1.Aの右手がBの左手に勝ち、Aの右手もBの右手に勝つときAに2点入る
2.Aの右手がBの左手に勝ち、Aの右手がBの右手と引き分けるときAに1点入る
3.それ以外は0点

このじゃんけんを複数回行うとして、AとBが出す手がそれぞれvector string で与えられる。これらの出す手の順番は変えてもよい。Aの得点を最大化するような順番で出すときのAの得点を求めよ。

やりかた

Editorialを参考にしました。

2点が獲得できるようなAとBの手の組み合わせを貪欲に列挙したのち、1点が獲得できる目を（2点の組み合わせで使用した手以外から）貪欲に列挙していけばいい。2点の組み合わせを貪欲に列挙することが原因で、より良いマッチングの可能性を消してしまうということは起こり得ない。
なんと説明したらいいやら、ある2点の手の組み合わせをひとつ選ぶことで、消えてしまう他のマッチングがあるわけだが、それらのマッチングの最大得点も高々2点なのでどうせどこで取ってもおんなじことになる、というわけ。

以下ソース。

class DoubleRoshambo {
public:
  bool win(char a, char b){
    if(a == 'R') return b == 'S';
    if(a == 'P') return b == 'R';
    if(a == 'S') return b == 'P';
    return false;
  }
  int point(string a, string b){
    if(win(a[1], b[1])){
      if(win(a[0], b[0])) return 2;
      if(a[0] == b[0]) return 1;
    }
    return 0;
  }
  int maxScore(vector <string> A, vector <string> E) {
    int result = 0;
    int N = A.size();

    bool usedA[50], usedB[50];
    fill(usedA, usedA + 50, false);
    fill(usedB, usedB + 50, false);
    
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	if(point(A[i], E[j]) == 2 && !usedA[i] && !usedB[j]) {
	  result += 2;
	  usedA[i] = usedB[j] = true;
	}

    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
	if(point(A[i], E[j]) == 1 && !usedA[i] && !usedB[j]) {
	  result += 1;
	  usedA[i] = usedB[j] = true;
	}
    
    return result;
  }
};

この貪欲は気づいてもよかったなと思う反面、できずにきちんと調べる時間を持てたのでよかったとも思う。類問のありそうな問題だ。

なお、AとBの各手の間で得点が定義されているので２部グラフの最大マッチングとしても解ける。これはとてもわかり易い。