AGC019: A - Ice Tea Store

問題

A - Ice Tea Store

普通の解法

0.25L のものを奇数個購入することはあり得ない。よって、0.25L は偶数個購入する必要があるが、これは0.5Lのものと値段と比較して小さい方を用いれば良い。同様のことが0.5Lと1Lの関係も言える。1Lと2Lの関係について、1Lの方が安くなるとき、答えはN \times Sである。また、2Lのもののほうが1Lの最小価格と比較して単価が安いとき、偶数奇数で場合分けして買えるだけ2Lを買い、余ったら1Lを1つ買うことになる。

int main() {
  int64_t Q, H, S, D, N;
  cin >> Q >> H >> S >> D >> N;
  auto precost = min(2 * Q, H);
  auto cost = min(2 * precost, S);
  cout << min(N * cost, N / 2 * D + (N % 2 == 1 ? cost : 0)) << "\n";
}

頭がない解法

貪欲法 + 全探索 で解いてしまった。

大抵は1Lあたりの単価が安いものを優先的に買うのが都合が良いため、 N - 2 (L) 分に貪欲法を適用する。 残りの 2L は全探索をすれば良い。この計算は 4 ^ 4 の計算量で抑えられるため、十分間に合う。

int64_t Q, H, S, D, N;
int64_t const Alpha = 2;

pair<int64_t, double> greedy(int64_t M) {
  vector<pair<int64_t, int64_t>> vs{{Q, 1}, {H, 2}, {S, 4}, {D, 8}};
  sort(vs.begin(), vs.end(), [](auto const &l, auto const &r) {
    return l.first * r.second < r.first * l.second;
  });
  int64_t cost, perL; tie(cost, perL) = vs[0];
  auto buynum = (4 * M + perL - 1) / perL;
  return {buynum * cost, M + Alpha - (buynum * perL / 4.0)};
}

int64_t bf(double r) {
  auto constexpr MAX = std::numeric_limits<int64_t>::max();
  if (r == 0) return 0;
  if (r < 0) return MAX;
  auto a = bf(r - 0.25); if (a < MAX) a += Q;
  auto b = bf(r - 0.5);  if (b < MAX) b += H;
  auto c = bf(r - 1.0);  if (c < MAX) c += S;
  auto d = bf(r - 2.0);  if (d < MAX) d += D;
  return min({a, b, c, d});
}

int main() {
  cin >> Q >> H >> S >> D >> N;

  if (N <= Alpha) {
    cout << bf(N) << endl;
    exit(0);
  }

  int M = N - Alpha;
  auto x = greedy(M);
  auto y = bf(x.second);
  cout << x.first + y << "\n";
}