TCO2012 1B

参加記録。通過したけど、残念な結果。

250 :
やるだけ。やるだけにも関わらずFailedSystemTest。

500 :
メモ化した。memo[区間の先端][区間の終端][今何匹か]
貪欲とか2分探索みたいな解法の人もいた。

1000 :
読んでない。

---

250
本番後に通したヤツ。

class FoxAndKgram {
public:
  int maxK(vector <int> L)
  {
    int ret = 0;

    map<int, int> cnt;
    for (int i = 0; i < (int)L.size(); ++i) {
      ++cnt[L[i]];
    }

    const map<int, int> tmp = cnt;
    for (int k = 1; k <= 50; ++k) {
      cnt = tmp;
      int n = cnt[k];
      for (int i = 1; i < (int)k; ++i) {
        if (i == k - i - 1) {
          n += cnt[i] / 2;
          cnt[i] /= 2;
        } else {
          int mn = min(cnt[i], cnt[k - i - 1]);
          n += mn;
          cnt[i] -= mn;
          cnt[k - i - 1] -= mn;
        }
      }
      if (k <= n) ret = max(ret, k);
    }
    return ret;
  }
};

---

500
本番中に通したヤツ。

const int N = 50 + 5;
lli memo[N][N][N];

vector<int> W;
int S;

lli rec(int A, int B, int n)
{
  lli &ret = memo[A][B][n];
  if (ret != -1) return ret;
  if (A + 1 == B) return ret = W[A];

  lli mn = 1LL << 60;    
  if (n < B - A) {
    mn = min(mn, rec(A, B, min(B - A, n * 2)) + S);
  }
  
  if (1 < n) {
    for (int i = A + 1; i < (int)B; ++i) {
      lli mx = 0;
      for (int j = 1; j < (int)n; ++j) {
        lli a = rec(A, i, n - j);
        lli b = rec(i, B, j);
        mx = max(mx, max(a, b));
      }
      mn = min(mn, mx);
    } 
  }
  
  return ret = mn;
}

class FoxAndDoraemon {
public:
  int minTime(vector <int> workCost, int splitCost) 
  {
    W = workCost;
    S = splitCost;

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

    fill(&memo[0][0][0], &memo[N - 1][N - 1][N], -1);    
    return rec(0, W.size(), 1);
  }
};