C++の練習を兼ねて, AtCoder Beginner Contest 155 の 問題E (Payment) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 苦手な動的計画法(応用版, 桁DP) の訓練が積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 155 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc155/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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 dp[1010101][2]; // 第一成分: ビッタリ払う, 第二成分: 1 余分払う. int main(){ // 1. 入力情報. char c[1010101]; scanf("%s", c); string N(c); // 2. 先頭桁調整. // -> 最上位を, 0 として, 1 余分に払うパターンを考慮できるようにする. N = "0" + N; // 3. 初期化. int n = N.size(); dp[0][0] = N[0] - '0'; dp[0][1] = N[0] - '0' + 1; // 4. dp更新. repx(i, 1, n){ // 4-1. i桁目. int d = N[i] - '0'; // 4-2. ビッタリ払う. dp[i][0] = min(dp[i - 1][0] + d, dp[i - 1][1] + (10 - d)); // 4-3. 最終桁調整(最後の桁は, 1 余分に払うパターンを除外). int one = 1 * (i != n - 1); // 4-4. 1 余分払う. dp[i][1] = min(dp[i - 1][1] + (10 - d - one), dp[i - 1][0] + d + one); } // 5. 出力. printf("%d\n", min(dp[n - 1][0], dp[n - 1][1])); 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 |
[入力例] 36 [出力例] 8 ※AtCoderテストケースより [入力例] 91 [出力例] 3 ※AtCoderテストケースより [入力例] 314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170 [出力例] 243 ※AtCoderテストケースより [入力例] 55 [出力例] 10 [入力例] 2022 [出力例] 6 [入力例] 20220604 [出力例] 15 [入力例] 865 [出力例] 10 [入力例] 7303757170859110488253090166330591255584950648690495237568073417200248460609313772306159454783496207 [出力例] 250 [入力例] 70724236466682625983016007650618881977929720811339637123932889561587123865534594622908595022197867223711960026404451240970288911416387630615546871416353142099273847546794603912894032648233372930248274810021639656516270709975272305731817534338372670653812535382705418865350491561024438040752395240366745848586089405483319432991636452524649751165371256967896598248596768697535534954072556144874581365149044725352118618897521264905211964582621496071657993373871053636780385438537020885511873338571352435 [出力例] 1296 |
■参照サイト
AtCoder Beginner Contest 155