C++の練習を兼ねて, AtCoder Beginner Contest 231 の 問題E (Minimal payments) を解いてみた.
■感想.
1. 問題Eは, 解説を参考に, 実装を試行錯誤してみたものの, 実装方針が確定できず, 解説プログラムベースで, AC版としている.
2. メモ化再帰の復習が出来たので, 非常に良かったと思う.
但し, メモ化再帰の本質が理解出来てないので, 今後の課題だと思われる.
3. 方針が見えなかった原因として, 現在見ている硬貨だけでなく, 次回分の硬貨も見る必要がある部分, および, 現在見ている硬貨で割った余りがゼロの場合は, 再帰処理が, 一本化される部分が, 該当すると思われる.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 231 解説 を ご覧下さい.
■C++版プログラム(問題E／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// 解答不能. // https://atcoder.jp/contests/abc231/submissions/27854173 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int main(){ // 1. 入力情報. int N; LL X; scanf("%d %lld", &N, &X); vl a(N); rep(i, N) scanf("%lld", &a[i]); // 2. dfs(解説通り). // https://ja.wikipedia.org/wiki/深さ優先探索 // -> 正しく動作しないので, 解説プログラムを参考に, 以下のロジックに修正. map<LL, LL> m; auto dfs = [&](auto self, LL curX, int d) -> LL{ // 2-1. 終了条件. if(m.count(curX)) return m[curX]; if(d == N - 1) return curX / a[N - 1]; // 2-2. 端数処理. // -> 現在分, 次回分 の 数列 A の要素を考える必要があるらしい. LL curA = a[d]; LL nexA = a[d + 1]; LL rL = curX % nexA / curA; LL rR = nexA / curA - rL; // 2-3. 次回の支払い対象金額. LL nexXL = curX / nexA * nexA; LL nexXR = nexXL; if(curX % nexA) nexXR += nexA; // 2-4. 次へ. LL ret = rL + self(self, nexXL, d + 1); if(rL) ret = min(ret, rR + self(self, nexXR, d + 1)); // 2-5. 返却. return m[curX] = ret; }; // 3. 出力. printf("%lld\n", dfs(dfs, X, 0)); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
[入力例] 3 87 1 10 100 [出力例] 5 ※AtCoderテストケースより [入力例] 2 49 1 7 [出力例] 7 ※AtCoderテストケースより [入力例] 10 123456789012345678 1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000 [出力例] 233 ※AtCoderテストケースより [入力例] 4 234 1 5 50 250 [出力例] 5 [入力例] 11 3141592653 1 3 27 405 1215 8505 144585 1012095 17205615 326906685 3595973535 [出力例] 29 [入力例] 16 202112112100 1 3 15 45 225 1575 7875 23625 259875 5197500 36382500 254677500 2801452500 47624692500 142874077500 1571614852500 [出力例] 30 |