TopCoderOpen 2015 Round2C Easy YetAnotherCardGame

Resubmitのため0ptは回避したけどレート減。
http://community.topcoder.com/stat?c=problem_statement&pm=13912

問題

２人がN枚ずつカードを持っており、各カードの数値は1～100の整数のいずれかである。
同じ数値のカードが複数枚あっても良い。
この２人で、カードを番号昇順に積み上げるゲームを行う。

ゲーム開始時、先手はN枚のうち一部、後手はN枚全部からスタートする。
２人は交互に１枚ずつカードを処理する。
どちらかの手番で、手持ち０枚の状態で番が回ってきたらゲーム終了

自分の手番では、次のいずれかの手を取れる。

• カードの山が０枚の場合、手持ちのカードを１枚場において山を作る。
• カードの山が１枚以上の場合、手持ちのカードのうち山の最上位の数値より大きな数値のカードを山の最上位に置く。
• 任意の１枚を破棄する。

２人が協力して山に積まれたカード枚数を最大化するとき、何枚積めるか。

解法

まず先手がN枚のうち一部から進める理由はない。
先手がx枚の場合後手の手番もx回しか来ないが、このゲームではあえて全体の手番を減らす理由はないので、先手もN枚使い切ると考えて良い。

あとは簡単なDPで、dp[最上位の数] := 最大枚数 という状態をNターン更新するだけ。
両者の手番では、

• 何もしない
• 最上位の数より大きな最小値のカードを山に積む

のどちらかを行えばよい。

class YetAnotherCardGame {
	public:
	int maxCards(vector <int> petr, vector <int> snuke) {
		int N=petr.size(),i,x,y,z;
		sort(petr.begin(),petr.end());
		sort(snuke.begin(),snuke.end());
		
		int dp[101]={};
		FOR(i,N) {
			for(x=100;x>=0;x--) {
				FOR(z,N) if(petr[z]>x) break;
				if(z<N) dp[petr[z]]=max(dp[petr[z]],dp[x]+1);
			}
			for(x=100;x>=0;x--) {
				FOR(z,N) if(snuke[z]>x) break;
				if(z<N) dp[snuke[z]]=max(dp[snuke[z]],dp[x]+1);
			}
		}
		
		return *max_element(dp,dp+101);
	}
}

まとめ

先手がN枚以下でスタートしても良い、という問題文に騙され無駄に考え込んでしまった。