C++の練習を兼ねて, AtCoder Beginner Contest 257 の 問題E (Addition and Multiplication 2) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 257 解説 の 各リンク を ご覧下さい.
■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 56 57 58 59 60 61 62 63 64 |
// 解き直し. // https://atcoder.jp/contests/abc257/editorial/4136 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; #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--) #define pb push_back #define a first #define b second int main(){ // 1. 入力情報. int N, cMin = 2020202020, b = 0; scanf("%d", &N); map<int, int> m; rep(i, 9){ int c; scanf("%d", &c); m[c] = i + 1; if(cMin >= c){ cMin = c; b = i + 1; } } // 2. 利用可能な金額. vp o; for(auto &p : m) if(p.a < cMin * 2) o.pb({p.a, p.b}); // 3. 桁数. int n = N / cMin; // 4. 貪欲法. string ans = ""; int bef = 0; rep(i, n){ // i 桁目(候補). // -> なるべく大きな i 桁目 の 候補は? int d = 0, cur; for(auto &p : o){ if(p.b > d && bef + p.a + cMin * (n - i - 1) <= N){ d = p.b; cur = bef + p.a; } } // i 桁目. ans.pb(d + '0'); // 前回分更新. bef = cur; } // 5. 出力. printf("%s\n", ans.c_str()); 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 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
[入力例] 5 5 4 3 3 2 5 3 5 3 [出力例] 95 ※AtCoderテストケースより [入力例] 20 1 1 1 1 1 1 1 1 1 [出力例] 99999999999999999999 ※AtCoderテストケースより [入力例] 13 12 5 6 9 10 2 3 7 5 [出力例] 766666 [入力例] 256 31 41 5 9 26 53 5 8 9 [出力例] 777777777777777777777777777777777777777777777777777 [入力例] 2022 13 33 18 27 32 31 14 15 31 [出力例] 88871111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 [入力例] 2022 13 33 18 27 32 31 14 15 16 [出力例] 99711111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 [入力例] 12345 896 789 776 1327 735 743 770 836 1270 [出力例] 9765555555555555 [入力例] 20220625 68650 68661 68727 95533 93697 69078 70325 85841 129387 [出力例] 887666332211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ※ 整数 N が, 問題文の制約条件から範囲外であるケース. |
■参照サイト
日鉄ソリューションズプログラミングコンテスト2022(AtCoder Beginner Contest 257)