AtCoderログ：0033 - ABC 095 B

問題

問題文

パティシエの赤木さんは、「お菓子の素」という粉のみを材料として $N$ 種類のドーナツを作ることができます。これらのドーナツはドーナツ $1$、ドーナツ $2$、$\dots$、ドーナツ $N$ と呼ばれます。ドーナツ $i~(1 \le i \le N)$ を $1$ 個作るには、お菓子の素 $m_i$ グラムを消費する必要があります。なお、$0.5$ 個など整数でない個数のドーナツを作ることはできません。
いま、赤木さんはお菓子の素を $X$ グラム持っています。これを使って、今夜のパーティーに向けて可能な限りたくさんのドーナツを作ることにしました。ただし、来客の味の好みは様々なので、次の条件を守ることにしました。
・$N$ 種類のドーナツそれぞれを少なくとも $1$ 個は作る。
このとき、最大で何個のドーナツを作ることができるでしょうか？お菓子の素を使い切る必要はありません。また、この問題の制約のもとでは、条件を守ることは必ず可能です。

制約

・$2 \le N \le 100$
・$1 \le m_i \le 1000$
・$m_1+m_2+\ldots+m_N \le X \le 10^5$
・入力中のすべての値は整数である。

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

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

回答

回答1 (AC)

ドーナツの個数の個数を最大にするには、n 個のドーナツを 1 個ずつ作った後、ドーナツの素の消費量が最も少ないドーナツだけを作れば良いです。処理としては、ドーナツの種類 n とドーナツの素の量 x と各ドーナツを作るのに必要なドーナツの素の量を受け取り、各ドーナツを1個ずつ作るのに必要なドーナツの素の合計 sum と、ドーナツの素の消費量の最小値 dmin を求め、最後に合計で作ることのできるドーナツの個数 donut を計算します。コードは以下のようになりました。

abc095b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, x;
  cin >> n >> x;
 
  vector<int> m(n);
  for ( int i=0; i<n; i++ ) {
    cin >> m.at(i);
  }
 
  int sum = 0, dmin = m.at(0);
  for ( int i=0; i<n; i++ ) {
    sum += m.at(i);
    dmin = min( dmin, m.at(i) );
  }
  
  int donut = n + (x-sum)/dmin;
 
  cout << donut << endl;
}

回答2 (AC)

回答1の無駄な処理を削っていきます。まず、各ドーナツは1個ずつは作るので、各ドーナツを作るのに必要なドーナツの素 m を受け取るたびに、所持しているドーナツの素の総量 x から m を引けば、変数 sum は不要です。また、m を受け取るたびに dmin を更新していくことで、各ドーナツを作るのに必要なドーナツの素を配列として所持する必要がなくなります。これらの改良を用いたコードは次のようになりました。回答1のコードに比べ、かなりコンパクトになっています。

abc095b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, x;
  cin >> n >> x;
 
  int m, dmin = INT_MAX;
  for ( int i=0; i<n; i++ ) {
    cin >> m;
    x    -= m;
    dmin =  min( dmin, m );
  }
 
  cout << n + x/dmin << endl;
}

調べたこと

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

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

リンク

• 前の記事 → AtCoderログ：0032 - 「AtCoder に登録したら次にやること」のまとめ
• 次の記事 → AtCoderログ：0034 - ABC 211 に参加しました