Codeforces #325 Div1 D(Div2 F): Lizard Era: Beginning

半分全探索から先で悩んだ。

問題

勇者のあなたは3人の仲間を連れてN(<=25)個のクエストをこなす。各クエストでは3人のうちぴったり2人を連れて行く必要がある。各クエストにある仲間が参加した時のあなたへの態度（以下態度値）の変化値（整数）が設定されている。はじめ態度値は3人共0である。N個のクエストを終えた時に3人の態度値が等しくかつ最大になるような仲間の選び方を1つ答えよ。

解法

各クエストで誰を連れて行くか(＝誰を連れて行かないか)を愚直に選んでいくと計算量が3²⁵≒2⁴⁰となり間に合わない。
そこで半分全探索で前半後半に分けて選んでいく。前半後半それぞれで、最終的な3人の態度値をx,y,zとすると(x-y, x-z)をキー、(x, s)を値としたマップを用意する（sは各クエストで誰を連れて行かなかったかを記録した値）。前半側のキー(a, b)に対して後半側にキー(-a, -b)があれば、最終的に3人の態度値を等しくすることができる。あとはそのようなキーのうち、態度値が最大になるようなものを選べば良い。

typedef long long ll;
typedef pair<int, int> pi;
typedef map<pi, pair<int, ll>> MAP;

const int INF = (int)1e9;
int N;
int l[30], m[30], w[30];

void dfs(MAP &comb, int i, int n, int x, int y, int z, ll s) {
  if (i == n) {
    pi ofs = make_pair(x - y, x - z);
    if (HAS(comb, ofs)) comb[ofs] = max(comb[ofs], make_pair(x, s));
    else comb[ofs] = make_pair(x, s);
    return;
  }
  dfs(comb, i + 1, n, x, y + m[i], z + w[i], 3 * s);
  dfs(comb, i + 1, n, x + l[i], y, z + w[i], 3 * s + 1);
  dfs(comb, i + 1, n, x + l[i], y + m[i], z, 3 * s + 2);
}

int main(void) {
  cin >> N;
  rep(i, N) cin >> l[i] >> m[i] >> w[i];

  MAP comb1, comb2;
  dfs(comb1, 0, N / 2, 0, 0, 0, 0);
  dfs(comb2, N / 2, N, 0, 0, 0, 0);

  string ans[25];
  const string C[] = {"MW", "LW", "LM"};
  int mx = -INF;
  ITR(it, comb1) {
    pi ofs = (*it).first;
    int x1 = comb1[ofs].first;
    ll  s1 = comb1[ofs].second;
    pi rofs = make_pair(-ofs.first, -ofs.second);
    if (HAS(comb2, rofs)) {
      int x2 = comb2[rofs].first;
      ll  s2 = comb2[rofs].second;
      if (x1 + x2 < mx) continue;
      mx = x1 + x2;
      REP(i, 0, N / 2) {
        ans[i] = C[s1 % 3];
        s1 /= 3;
      }
      reverse(ans, ans + (N / 2));
      REP(i, N / 2, N) {
        ans[i] = C[s2 % 3];
        s2 /= 3;
      }
      reverse(ans + (N / 2), ans + N);
    }
  }

  if (mx > -INF) {
    rep(i, N) cout << ans[i] << endl;
  } else {
    cout << "Impossible" << endl;
  }

  return 0;
}