[AtCoder] ABC 141 D – Powerful Discount Tickets

2019年9月16日

問題

方針

チケットの使い方

チケットを一度に複数枚使うことと一枚ずつ使うことが同じであることを確認します。\( 2 \) の指数を用いて整数を表現することを考えます。例えば、\( 31 \) は、

\[ 31 = 2^4 + 2^3 + 2^2 + 2^1 + 2^0\]

と表現できます。ここで、チケットは最大で \( 5 \) 回使うことができます。一枚使うと、\( 2^0 \) の部分で切り捨てが発生し、さらにもう一枚使うと、\( 2^1 \) の部分で切り捨てが発生することが分かります。また、チケットを二枚一度に使うと、\( 2^0 \) と \( 2^1 \) の部分で切り捨てが発生することが分かります。

以上の考察から、チケットを \( n \) 枚使うとき、チケットの使い方に依らず、切り捨てが発生する箇所は、\( n \) ビット目以下のフラグが立っている箇所です。

値引きされる金額を最大化する

チケットを一枚ずつ使うことを考えます。値引きされる金額が最大となるのは、商品の中で一番価格が高いものであることが分かります。なので、優先度付きキューを用いて、チケットを \( M \) 回一枚ずつ使ってシミュレーションを行えば良いです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int N, M;
  cin >> N >> M;
  int A[N];
  priority_queue<ll> pq;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    pq.push(A[i]);
  }
  
  for (int i = 0; i < M; i++) {
    int t = pq.top();
    pq.pop();
    t /= 2;
    pq.push(t);
  }
  ll ans = 0;
  while(!pq.empty()) {
    ans += pq.top();
    pq.pop();
  }
  cout << ans << "\n";
  return 0;
}