TCO12 R2B 550pt : HeavyBooks

問題概要

N(<50)冊本があり、各本には重さが設定されている。最初にAが何冊か本を選び、以後AとBが本を自分の負担する重さが最小になるように押し付け合う。ふたりが最適な戦略をとったときに最終的に重さの和がどうなっているか求める問題。

解法

押し付け合うフェーズでは、どちらも重いものから貪欲に押し付けるのが最適になる。とすれば、k番目に軽いものがどちらの負担になるかは分かるので、後はAが自分の負担が最小になるように最初に選ぶだけになる。これはとても簡単なDPで計算できる。

acceptされたコード

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int,int> foo;
const int MAX_N = 50;
const int INF = 1<<29;

int owner[MAX_N];
foo dp[MAX_N + 1][MAX_N + 1];

struct HeavyBooks {

	vector <int> findWeight(vector <int> books, vector <int> moves) {
		const int N = books.size();
		const int L = moves.size();
		const int K = moves[0];
		priority_queue<int> ts, ws;
		for(int i=0; i<K; ++i){
			ws.push(i);
		}

		for(int i=1; i<L; ++i){
			if(i&1){
				for(int j=0; j<moves[i] && !ws.empty(); ++j){
					int a = ws.top(); ws.pop();
					ts.push(a);
				}
			}
			else{
				for(int j=0; j<moves[i] && !ts.empty(); ++j){
					int a = ts.top(); ts.pop();
					ws.push(a);
				}
			}
		}

		for(;!ws.empty();ws.pop()){
			owner[ws.top()] = 1;
		}

		for(int i=0; i<=MAX_N; ++i){
			for(int j=0; j<=MAX_N; ++j){
				dp[i][j] = foo(-INF, -INF);
			}
		}

		sort(books.begin(), books.end());

		dp[0][0] = foo(0, 0);
		for(int i=0; i<N; ++i){
			for(int j=0; j<=K; ++j){
				dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
				if(j < K){
					foo nxt = dp[i][j];
					nxt.second += books[i];
					nxt.first += books[i] * (owner[j] ? 1 : -1);
					dp[i+1][j+1] = max(dp[i+1][j+1], nxt);
				}
			}
		}

		int wMt = dp[N][K].first, wPt = dp[N][K].second;

		vector<int> ret(2);
		ret[0] = (wPt - wMt) / 2;
		ret[1] = (wPt + wMt) / 2;
		return ret;
	}

};