Problem B - World Cup 2010

問題

2^P チームによって行われるトーナメント戦において，「チーム i が出る試合は最大でも M_i 回見逃していい」という条件を定めている．試合の進行がどのようになっても条件を満たすために必要なチケットを買う場合，その最少額はいくらか？

考え方

DP 的に1回戦ずつ考えるといい．
観客側から見て可能なのは観るか観ないかだけの選択であり，制限のキツさを考慮すると，見逃し制限が少ない側が勝った想定でいく必要がある．その際，勝利チームのメタ情報としては観た場合，観なかった場合の両方の(制限数，金額)をストックしておくことで必要なパターンは網羅できる．
2回戦以上ではそのメタ・チーム同士が全組み合わせで対戦する必要があるが，メタ情報の制限数が ≦P で収まっている(複数の組み合わせで制限数が重複した場合，金額が安い方を残す)ので最大でも P+1 パターンしか残らない．つまり計算量も１試合当たり O(P²)，全体でも O(2^P P²) に収まる．

コード

制限数の重複チェックは配列を上手く使えばスッキリ書けるんでしょうけど，私のイメージのままでは<map>使うのが限界．

#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef map<int,int> Cost;

inline void add(Cost& cost, int m, int c)
{
  if( m < 0 ) return;
  if( cost.find(m) == cost.end() ) {
    cost.insert(pair<int,int>(m, c));
  } else {
    cost[m] = min(cost[m], c);
  }
}

int solve(void)
{
  int P, N;
  cin >> P;
  N = 1 << P;
  vector<Cost> cost(N);
  for( int i = 0 ; i < N ; ++i ) {
    int M;
    cin >> M;
    cost[i].insert(pair<int,int>(M, 0));
  }

  for( N /= 2 ; N ; N /= 2 ) {
    vector<Cost> win(N);
    for( int j = 0 ; j < N ; ++j ) {
      Cost &c0 = cost[2*j], &c1 = cost[2*j+1];
      int price;
      cin >> price;
      for( Cost::iterator p0 = c0.begin() ; p0 != c0.end() ; ++p0 ) {
        for( Cost::iterator p1 = c1.begin() ; p1 != c1.end() ; ++p1 ) {
          int m = min(p0->first, p1->first);
          int c = p0->second + p1->second;
          add(win[j], m - 1, c        );
          add(win[j], m    , c + price);
        }
      }
    }
    cost = win;
  }

  int pay = cost[0].begin()->second;
  for( Cost::iterator it = cost[0].begin() ; it != cost[0].end() ; ++it ) {
    pay = min(pay, it->second);
  }
  return pay;
}

int main(void)
{
  int T;
  cin >> T;
  for( int t = 1 ; t <= T ; ++t ) {
    cerr << "Case #" << t << "\n";
    cout << "Case #" << t << ": " << solve() << "\n";
  }
  return 0;
}