POJ 2062 Card Game Cheater

問題

二人のプレイヤーがk枚のカードを一列に向かい合うようにして並べる。
向かい合ったそれぞれのカードについて、大きいほうに1点が入る。

相手のカードとその並べ方がわかっているとき、獲得できる点数の最大値を求めよ。

制約条件

k≦26

方針

貪欲法による。
相手のカードの大きいほうから見ていき、
それに勝つようなカードがあれば、その中で最もランクの小さいものを使い、
なければ、最も弱いカードを捨石にする。

[追記]
別解がたくさんあるみたいです。
相手のカードを弱いほうから見ていく貪欲法や、
二部グラフの最大マッチングを使う方法（勝てるカードの関係に辺を貼る）、
ソートして二分探索や尺取法を使うなど。

• http://togetter.com/li/215083

ソースコード

vi parse(int n){
	char buf[10];
	vi res;
	while(n--){
		scanf("%s",buf);
		int pt=0;
		switch(buf[0]){
		case 'A': pt=14; break;
		case 'T': pt=10; break;
		case 'J': pt=11; break;
		case 'Q': pt=12; break;
		case 'K': pt=13; break;
		default: pt=buf[0]-'0';
		}
		pt*=4;
		switch(buf[1]){
		case 'H': pt+=3; break;
		case 'S': pt+=2; break;
		case 'D': pt++; break;
		}
		res.pb(pt);
	}
	sort(all(res));
	return res;
}
int main()
{
	int cs; scanf("%d",&cs);
	while(cs--){
		int n; scanf("%d",&n);
		vi a=parse(n),b=parse(n);
		int ans=0;
		bool use[26]={};
		for(int i=n-1;i>=0;i--){
			int mn=-1,mn2=-1;
			rep(j,n){
				if(!use[j]&&b[j]>a[i]&&(mn==-1||b[mn]>b[j]))mn=j;
				else if(!use[j]&&b[j]<=a[i]&&(mn2==-1||b[mn2]>b[j]))mn2=j;
			}
			if(mn==-1)use[mn2]=1;
			else use[mn]=1, ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}