AtCoderログ：0015 - ABC 209 B

問題：ABC 209 B - Can you buy them all?

問題文

高橋商店では $N$ 個の商品が売られています。$i~(1 \le i \le N)$ 番目の商品の定価は $A_i$ 円です。
今日はセールが行われており、偶数番目の商品は定価の $1$ 円引きの値段で買うことができます。奇数番目の商品は定価で売られています。
あなたの所持金は $X$ 円です。これら $N$ 個の商品を全て買うことができますか？

制約

・$1 \le N \le 100$
・$1 \le X \le 10000$
・$1 \le A_i \le 100$
・入力は全て整数

回答1 (AC)

処理の流れは、各商品の定価を配列 a() で受け取り、値引き後の n 個の売価の合計 sum を算出し、所持金 X がそれより大きければ Yes, そうでなければ No を出力する、となります。コードの添え字は 0 から始まっているので、コードでは奇数番目の商品を値引きすることに注意が必要です。以下のコードでACとなりました。提出コードも同じ方針でした。

abc209b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, x;
  cin >> n >> x;
 
  vector<int> a(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
  }

  int sum = 0;
  for ( int i=0; i<n; i++ ) {
    if ( i%2==1 ) {
      a.at(i) -= 1;
    }
    sum += a.at(i);
  }

  if ( x>=sum ) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

回答2 (AC)

回答1を改良します。この問題では売価の合計がわかれば良いので、各商品の売価を保存する必要がなく、配列 a は不要です。また、割引額の合計は、0 から n-1 までの奇数の個数なので、割引額の合計は n/2 円となり、まとめて割り引くことができます。以上の考察をコードに適用すると以下のようになり、ちょっとだけシンプルになりました。

abc209b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, x;
  cin >> n >> x;
 
  int a, sum = 0;
  for ( int i=0; i<n; i++ ) {
    cin >> a;
    sum += a;
  }
  sum -= n/2;
 
  if ( x>=sum ) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

調べたこと

AtCoder の解説 → 公式解説

回答1と同じ方針でした。max(0,b-a+1) とすると場合分けが不要になるとのこと。なるほど。

リンク

• 前の記事 → AtCoderログ：0014 - ABC 209 A
• 次の記事 → AtCoderログ：0016 - ABC 209 C