Codeforces Round #325 (Div. 1) D. Lizard Era: Beginning
解法
半分全列挙するだけです。
覚えておく量は, 「L と M の差」, 「L と W の差」だけで十分です。
const int MAXN = 30; const int INF = 1e9; int Q[MAXN][3]; int n, N; struct quests { vector<int> select; int L, M, W; }; map<pii, quests> qs; void print(const vector<int>& v) { for (int el : v) cout << el << " "; cout << endl; } void dfs(int i, vector<int> qq, vector<int>& v) { if (i == N) { pii p(qq[0]-qq[1], qq[0]-qq[2]); if (qs.find(p) == qs.end() || qs[p].L < qq[0]) { quests q; q.select = v; q.L = qq[0]; q.M = qq[1]; q.W = qq[2]; qs[p] = q; } return; } for (int j = 0; j < 3; j++) { v.push_back(j); for (int k = 0; k < 3; k++) if (k != j) qq[k] += Q[i][k]; dfs(i+1, qq, v); for (int k = 0; k < 3; k++) if (k != j) qq[k] -= Q[i][k]; v.pop_back(); } } int ans = -INF; vector<int> best; void dfs2(int i, vector<int> qq, vector<int>& v) { if (i == n) { pii p(qq[1]-qq[0], qq[2]-qq[0]); if (qs.find(p) != qs.end()) { quests q = qs[p]; int l = q.L + qq[0]; if (ans < l) { ans = l; for (int j = 0; j < N; j++) { best[j] = q.select[j]; } for (int j = N; j < n; j++) { best[j] = v[j-N]; } } } return; } for (int j = 0; j < 3; j++) { v.push_back(j); for (int k = 0; k < 3; k++) if (k != j) qq[k] += Q[i][k]; dfs2(i+1, qq, v); for (int k = 0; k < 3; k++) if (k != j) qq[k] -= Q[i][k]; v.pop_back(); } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for (int i = 0; i < n; i++) { cin >> Q[i][0] >> Q[i][1] >> Q[i][2]; } N = n/2; vector<int> v; dfs(0, vi(3), v); best.resize(n); dfs2(N, vi(3), v); if (ans == -INF) { cout << "Impossible" << endl; return 0; } for (int i = 0; i < n; i++) { switch(best[i]) { case 0: cout << "MW" << endl; break; case 1: cout << "LW" << endl; break; case 2: cout << "LM" << endl; break; } } return 0; }