AtCoderBeginnerContest231 E問題500点 「Minimal payments」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ 1 \leq N \leq 60
$ A_1 < A_2 < \dots < A_N = 10^{18}
$ A_i | A_{i + 1}
気持ち
解法
公式解説のように 小さなコイン$ A_1から考えていきます。
$ i枚目のコインを何枚使うか考えるとします。
このとき、$ i枚目を使うべきコインは$ A_{i+1} / A_i枚以下であるべきです。
たとえば、$ A_1 = 1, A_2 = 8のとき、8枚以上使ってしまうと無駄になってしまいます。($ A_2 を+1枚すればいいため。)
よって、$ A_{i+1} / A_i枚が、$ i枚目の使うコインの最大数です。
(ここで指す使うとは、支払うだけでなく、お釣りとしての「使う」も含みます。つまり、上記の例ではお釣りとして1円が4枚帰ってくるということを、 4 枚使うとして指しています。)
また、ここで$ A_iを何枚使うのか?(払うもしくはお釣りとして)を考えてみます。
まず、先程の考察から、$ A_iのコインを使って払う金額は $ k = X \% A_{i+1}円になります。
($ A_{i+1}円で割り切れるぶんのお金は$ A_{i+1}円を使うべきであるため)
ここから$ A_iで直接$ k円を支払う場合と、お釣りとして間接的に支払う場合の2パターンを考えます。
直接支払う場合
$ r = k / A_i枚のコインを使って払います。
払っていない残りの金額は$ \frac{X}{A_{i+1}}A_{i+1} 円です。
別の書き方をすると、$ X - (X \% A_{i+1}) 円です。
よって、この払っていない残りの金額を$ i + 1以降のコインでお支払いすればいいです。
間接的にお釣りとして払う場合
$ i+1枚目のコインを+1枚多く払うことによって、$ i枚目のコインをお釣りとしてもらいます。
これは、$ \frac{A_{i+1}}{A_i} - r枚のコインをお釣りとしてもらうということです。
たとえば、$ X = 10で、$ A_1 = 1, A_2 = 8の場合を考えます。
$ X \% A_2 = 2円を支払う必要があり、直接払うなら 2 円ですが、
$ A_2=8を+1枚使うのであれば、$ 8/1 - 2 = 6枚のお釣りをもらいます。
このとき、払っていない金額は$ \lceil \frac{X}{A_{i+1}} \rceil A_{i+1}円となります。($ i+1枚目を +1 枚使うので少し高くなります)
この金額を$ i + 1以降のコインでお支払いすればいいです。
この議論を最後までメモ化再帰で実行すればいいです。 計算量
$ O(N)
新たな学び
$ A_Nからや$ A_1からなど、どちらかから考えて議論をし、その議論を再帰させる
$ A_i | A_{i+1}のコインを使う場合、$ \frac{A_{i+1}}{A_i}枚未満しか$ iのコインは使わない
反省点
コード
code: c++
LL f(int N, LL X, LL i, vector<LL> &A, map<LL, LL> &mp) {
if (mp.count(X)) return mpX; if (i == N - 1) return X / A.back();
if (X == 0) return 0;
LL ret = f(N, X / nxt * nxt, i + 1, A, mp) + r;
if (r) chmin(ret, f(N, CE(X, nxt) * nxt, i + 1, A, mp) + (nxt / crr - r));
}
int main() {
int N;
LL X;
cin >> N >> X;
vector<LL> A(N);
cin >> A;
map<LL, LL> mp;
cout << f(N, X, 0, A, mp) << endl;
return 0;
}