AtCoderログ：0079 - ARC 096 C/ABC 095 C

問題

問題文

ファーストフードチェーン「ピザアット」のメニューは「A ピザ」「B ピザ」「AB ピザ」の $3$ 種類です。A ピザと B ピザは全く異なるピザで、これらをそれぞれ半分に切って組み合わせたものが AB ピザです。A ピザ、B ピザ、AB ピザ $1$ 枚あたりの値段はそれぞれ $A$ 円、$B$ 円、$C$ 円です。
中橋くんは、今夜のパーティーのために A ピザ $X$ 枚と B ピザ $Y$ 枚を用意する必要があります。これらのピザを入手する方法は、A ピザや B ピザを直接買うか、AB ピザ $2$ 枚を買って A ピザ $1$ 枚と B ピザ $1$ 枚に組み替える以外にはありません。このためには最小で何円が必要でしょうか？なお、ピザの組み替えにより、必要な量を超えたピザが発生しても構いません。

制約

・$1 \le A,B,C \le 5000$
・$1 \le X,Y \le 10^5$
・入力中のすべての値は整数である。

収録されている問題セット

• AtCoder に登録したら次にやること (第08問類題)

回答

回答1 (AC)

この問題の難しいところは、ピザを余って購入しても良いという点です。A ピザを入手するには「A ピザ」を購入する場合と「AB ピザ」を購入する場合がありますが、余るのは「AB ピザ」を購入した場合だけです。例えば A ピザの入手枚数が x 枚を越えた場合、越えた分は「AB ピザ」に由来します。というのも、越えた分が「A ピザ」ならば、越えた分の「A ピザ」を買わない方が代金が安くなるからです。

この問題はピザを購入する枚数に関して全検索するのが良いのですが、「A ピザ」を i 枚購入したとすると、A ピザを x 枚揃えるにはあと x-i 枚必要なので、残りは「AB ピザ」を購入することになります。しかし最終的にピザは余ってもよいため、「AB ピザ」を購入する枚数は定まらず、この枚数も全検索する必要が生じてしまいます。「B ピザ」の購入枚数を i 枚として考えても同様です。

これに対し「AB ピザ」の購入枚数を i 枚とすると、「A ピザ」や「B ピザ」はわざわざ余らせて購入することはないので、「A ピザ」はあと x-i/2 枚、「B ピザ」はあと y-i/2 枚を購入することになり、全体の処理がすっきりします。コードは以下のようになりました。

arc096c-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, ab, x, y;
  cin >> a >> b >> ab >> x >> y;
 
  int price = 0, pmin = INT_MAX;
  for ( int i=0; i<=2*max(x,y); i+=2 ) {
    price = max(0,x-i/2)*a + max(0,y-i/2)*b + i*ab;
    pmin  = min(pmin,price);
  }

  cout << pmin << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。$O(1)$ の解答もあるのだそうです。

リンク

前後の記事

• 前の記事 → AtCoderログ：0078 - ABC 214 A