AtCoderログ：0022 - ABC 210 A

問題：ABC 210 A - Cabbages

問題文

高橋君はキャベツ屋さんにやってきました。
キャベツ屋さんでは、 キャベツを $1$ 個 $X$ 円で買うことができます。
ただし、キャベツを $A$ 個よりも多く買う場合、$A+1$ 個目以降に買うキャベツについては $1$ 個 $Y$ 円で買うことができます。（ここで、$Y<X$ が保証されます。）
高橋君がキャベツを $N$ 個買うために必要な金額を出力してください。

制約

・$1 \le N \le 10^5$
・$1 \le A \le 10^5$
・$1 \le Y < X \le 100$
・入力はすべて整数

回答1 (AC)

問題の内容を正しく理解できればそれほど難しくないでしょう。購入するキャベツの個数 n が閾値の a より大きいかどうかを判断し、それぞれの場合の価格を計算していくことになります。n が a より大きい場合、最初の a 個の単価は x 円、残りの n-a 個の単価は y 円になることに注意が必要です。コードは以下のようになりました。私が提出したコードも同じ方針でした。

abc210a-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, a, x, y;
  cin >> n >> a >> x >> y;
 
  if ( n<a ) {
    cout << x*n << endl;
  } else {
    cout << x*a+y*(n-a) << endl;
  }
}

回答2 (AC)

キャベツの購入個数 n を横軸、合計金額 Cost を縦軸にしてグラフを描くと以下のようになります。購入個数が a 個以内ならば、グラフは Cost=xn という(原点を通る)直線になります(左側の太い実線)。購入個数が a 個を越えた場合、グラフは Cost=xa+y*(n-a) という直線(右側の太い実線)になります。それぞれのグラフを延長すると点線部が現れるので、キャベツの購入個数 n に依らず、合計金額は常に xn と xa+y*(n-a) の少ない方になっていることがわかります。この考察を用いると、if 文による場合分けが不要となり、以下のようなシンプルなコードになります。

abc210a-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, a, x, y;
  cin >> n >> a >> x >> y;
 
  cout << min( x*n, x*a+y*(n-a) ) << endl;
}

調べたこと

AtCoder の解説 → 公式解説

回答1と同じ方針でした。なお、n=a の場合はどちらの式を用いても合計金額は同じになりますので、if 文の n<=a は n<a でも問題ありません。

リンク

• 前の記事 → AtCoderログ：0021 - ABC 210 に参加しました
• 次の記事 → AtCoderログ：0023 - ABC 210 B