AtCoderログ：0008 - ABC 208 B

問題

問題文

高橋王国では $1!$ 円硬貨, $2!$ 円硬貨, $\dots$, $10!$ 円硬貨が流通しています。ここで、$N!=1 \times 2 \times \cdots \times N$ です。
高橋君は全ての種類の硬貨を $100$ 枚ずつ持っており、$P$ 円の商品をお釣りが出ないようにちょうどの金額を支払って買おうとしています。
問題の制約下で条件を満たす支払い方は必ず存在することが証明できます。
最小で何枚の硬貨を使えば支払うことができますか？

制約

・$1 \le P \le 10^7$
・$P$ は整数である。

回答

回答1 (AC)

支払いに使用する硬貨の枚数を最小にするには、大きな硬貨から使用枚数を計算していけば良いでしょう。わかりやすいように $10! \sim 1!$ を全て計算し、配列に保持しました。コードは以下のようになります。私が ABC 208 に参加したときも同じ方針で提出コード](https://atcoder.jp/contests/abc208/submissions/23966193)を作成しました。

abc208b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int p;
  cin >> p;
 
  vector<int> coin = { 3628800, 362880, 40320, 5040, 720,
                           120,     24,     6,    2,   1 };
  int cnumber = 0;
  for ( int i=0; i<10; i++ ) { 
    cnumber += p/coin.at(i); 
    p       -= (p/coin.at(i))*coin.at(i);
  }
  
  cout << cnumber << endl;
}

回答2 (AC)

回答1では $1!,2!,\dots,10!$ を計算した値を使用していましたが、コードからは何のパラメータかわからないので、コードの内部で計算するように変更しました。コードは以下のようになります。

abc208b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int p;
  cin >> p;
 
  int coin = 1;
  for ( int i=1; i<=10; i++ ) {
    coin *= i;
  }

  int cnumber = 0;
  for ( int i=10; i>0; i-- ) { 
    cnumber += p/coin; 
    p       -= (p/coin)*coin;
    coin    /= i;
  }
  
  cout << cnumber << endl;
}

おまけ

高橋君は全ての硬貨を $100$ 枚ずつ持っているので、同じ硬貨を何枚か使うことで一つ大きな硬貨の金額を支払うことができます。このため、高橋君が支払うことができない金額はないことがわかります。

調べたこと

AtCoder の解説 → 公式解説

解答1は小さい方から硬貨の枚数を計算していく方法で、階乗の性質をうまく使っていると思いました。解答2は回答と同じ方針でした。

AtCoder の解説 → ユーザ解説

回答と同じ方針でした。補足説明の部分はちょっとピンときませんでした...

リンク

ABC 208 関連情報

• AtCoderログ：0006 - ABC 208 に参加しました
• AtCoderログ：0007 - ABC 208 A
• AtCoderログ：0009 - ABC 208 C

前後の記事

• 前の記事 → AtCoderログ：0007 - ABC 208 A
• 次の記事 → AtCoderログ：0009 - ABC 208 C