TopCoder SRM 345 Div1 Medium StoneGame

TopCoder ゲーム

問題

n個の宝箱があり、それぞれの価値はtreasure[i]である。
i番目の宝箱の上には石がstones[i]個乗っており、二人が次のようなゲームをする。

  • 交互に手番を取る。
  • 石を一つだけ選び、それを取り去る。
  • その石が、その宝箱の上の最後の石ならば、プレイヤーはその宝箱を得られる


お互いが最善を尽くすとき、先手は最大でいくつの価値の宝を得られるか、求めよ。

制約条件

n≦50
treasure[i]≦10^6
stones[i]≦10^6

方針

石が2つ以上しか乗っていない宝箱しかない場合を考える。
このとき、石の数の合計が奇数なら先手が全ての宝を得られ、
偶数なら後手が全ての宝を得られる。


石が1つの宝箱がだけだったら、
石が1つの宝箱の価値の高い順に先手、後手、先手、後手と取ることになる。


石が二つ以上の宝箱と一つの宝箱が両方あった場合は、
石が一つの宝箱と二つ以上の宝箱に分けて考えれば、それぞれ上のようになることがわかる。

ソースコード

class StoneGame {
	public:
	int getScore(vector <int> treasure, vector <int> stones) 
	{
		int n=stones.size(), sum=0, ans=0;
		vi one;
		rep(i,n)if(stones[i]==1)one.pb(treasure[i]);
		else sum+=stones[i];
		
		sort(all(one),greater<int>());
		for(int i=0;i<one.size();i+=2)ans+=one[i];
		
		if((sum+one.size())%2)rep(i,n)if(stones[i]!=1)
			ans+=treasure[i];
		return ans;
	}
};