yukicoder : No.2799 Cut and Eat

うーん、これ実験とかするとわかるのかな。
https://yukicoder.me/problems/no/2799

問題

N個のケーキがあり、それぞれのサイズが与えられる。
また正整数Kが与えられる。

これらを用いて2人のターン制ゲームを行う。
ターンでは、ケーキが残っている限り以下のいずれかを行える。

• サイズK以下のケーキを食べる。
• ケーキを1つ選び、正整数の大きさの2つのケーキに分割する。

両者食べられるケーキの量を最大化しようとするとき、先手が食べる量を答えよ。

解法

相手と自分の食べるケーキの総量は、元のケーキの総量に一致する。
言い換えると、相手の食べた量だけ自分は食べられなくなる。

ケーキのサイズsに対し、食べられる量と相手が食べる量の差v(s)は以下のようにできる。

• s≦Kならそのまま食べればよいのでs
• s＞Kなら
  • sが偶数なら、2等分することで0
  • sが奇数なら、2等分しても最終的に相手が1多く食べてしまうので-1

あとは、ケーキをv(s)の大きい順に並べ、先手から順に交互に食べて行くと考えればよい。

int N,K;
ll A[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll sum=0;
	FOR(i,N) {
		cin>>A[i];
		sum+=A[i];
		if(A[i]>K) {
			A[i]=-(A[i]%2);
		}
	}
	sort(A,A+N);
	reverse(A,A+N);
	ll P=0;
	FOR(i,N) {
		if(i%2==0) P+=A[i];
		else P-=A[i];
	}
	cout<<(P+sum)/2<<endl;
}

まとめ

コードは短い。