C++の練習を兼ねて, AtCoder Regular Contest 130 の 問題C (Digit Sum Minimization) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 非常に面白い問題に感じた.
3. 学習のために, 解説プログラムを確認後, 実際に桁和を評価するパターンを組み込んだ実装もしてみた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 130 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
// 解き直し. // https://atcoder.jp/contests/arc130/editorial/2976 // 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--) #define pb push_back int aCount[10], bCount[10]; int main(){ // 1. 入力情報. char s1[101010], s2[101010]; scanf("%s %s", s1, s2); string sa(s1), sb(s2); // 2. a, b を 調整. bool aMinB = true; int al = sa.size(), bl = sb.size(); if(al > bl){ swap(sa, sb); aMinB = false; } // 3. 各桁の数字の出現回数. int lMax = max(al, bl), lMin = min(al, bl); rep(i, lMax){ if(i < lMin) aCount[sa[i] - '0']++; bCount[sb[i] - '0']++; } aCount[0] += lMax - lMin; assert(bCount[0] == 0); // rep(i, 10) printf("%d ", aCount[i]); // puts("\n-----"); // rep(i, 10) printf("%d ", bCount[i]); // puts("\n-----"); // 4. 各桁の並び替え. int kMax = 0; string ans[2]; ans[0] = sa; ans[1] = sb; repx(a0, 1, 10){ // 4-1. 変数を準備. int k = 0; string t[2]; t[0] = ""; t[1] = ""; int ca[10], cb[10]; rep(i, 10){ ca[i] = aCount[i]; cb[i] = bCount[i]; } // 4-2. a[0] + b[0] >= 10 となるものを探す. if(ca[a0]){ repx(b0, 10 - a0, 10){ // 見つかった場合は, 保存. if(cb[b0]){ t[0].pb(a0 + '0'); t[1].pb(b0 + '0'); ca[a0]--; cb[b0]--; k++; break; } } } // 4-3. 見つからなかった場合. // printf("a0=%d t0=%s t1=%s\n", a0, t[0].c_str(), t[1].c_str()); if(!k) continue; // 4-4. 見つかった場合. repx(a, 1, 10){ repx(b, 9 - a, 10){ if(ca[a]){ // 各数字の出現回数を更新. int l = min(ca[a], cb[b]); ca[a] -= l; cb[b] -= l; k += l; // 文字列作成. string aStr(l, a + '0'); string bStr(l, b + '0'); // 文字列追加. t[0] = aStr + t[0]; t[1] = bStr + t[1]; } } } // 4-5. 桁数以上(ゼロを考慮)の場合. if(ca[0]){ if(cb[9]){ // 該当する数字の出現回数を更新. int l = min(ca[0], cb[9]); ca[0] -= l; cb[9] -= l; k += l; // 文字列作成. string bStr(l, 9 + '0'); // 文字列追加. t[1] = bStr + t[1]; } } // 4-6. 残り. repx(a, 1, 10){ if(ca[a]){ string aStr(ca[a], a + '0'); t[0] = aStr + t[0]; } } repx(b, 1, 10){ if(cb[b]){ string bStr(cb[b], b + '0'); t[1] = bStr + t[1]; } } // 4-7. 最大値更新. if(k > kMax){ kMax = k; ans[0] = t[0]; ans[1] = t[1]; } } // 5. 入れ替え. if(!aMinB) swap(ans[0], ans[1]); // 6. 出力. printf("%s\n%s\n", ans[0].c_str(), ans[1].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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
[入力例] 253 286 [出力例] 532 268 ※AtCoderのテストケースより [入力例] 345 556 [出力例] 435 565 ※AtCoderのテストケースより [入力例] 123 987987 [出力例] 312 799788 ※AtCoderのテストケースより [入力例] 11111111111111111111 111111111111111111111111111111 [出力例] 11111111111111111111 111111111111111111111111111111 ※AtCoderのテストケースより [入力例] 33231965444 773455566 [出力例] 19233444563 766555437 [入力例] 13785194584316927589 361659282125285 [出力例] 55299111335446887789 988665553222211 [入力例] 64298525857766878472 985733285545756164339168335839 [出力例] 98888777766655544222 888666599955311333233354455778 [入力例] 31415926535897932384626433832795 28841971693993751 [出力例] 66555443333999933221122345678887 99998877654321113 [入力例] 22175444971457187528782565139685443474229549313625352752311829887254616176822621978974878462694157495375954615447899327541617489148111884227358232886286227889645557945726241681611891958772213477437515 551641763747245118646413653235781313233898374817931453544492522426656592511875353264755952631934534191775794555619912773366291621596845688541515236561 [出力例] 88877777777777522222222222222111199999999999999999111111111111111111111222222222222255555533333333333354444444444444444444444444455555555555555555776666666666666666677777777777778888888888888888888888 999999999999888888888777777777777766666666666666666655555555555555555555555555544444444444444444333333333333333333322222222222221111111111111111111112 [入力例] 596566292477225167124797689822712989922218287694224795251699134214547334585329464159544189788918151193737328351346297845156335816156298861219182734638377894728227668331283653624246257276377836811971862752912774484634753467867376249442665576297677263994726859927416957145424679534826171713328616357727 76564588753992977891167538419732544499251298849996481579385543316893495799434283729514832677617324997637168395535682693663371365536697733465595971514825885974222929187611533998246944634996939819275442 [出力例] 888888888888777777777777777777777777777666666666666555554444444433333399999999999999999999999999999932222222222222222222222111111111111111111111111111111122222222222222222222233333333333333333333344444444444444444444444455555555555555555555556666666666666666666666666777777777777777788888888888888888 99999999999999999999999999999999999888888888888888888877777777777777777777766666666666666666666655555555555555555555555544444444444444444444443333333333333333333333333222222222222222211111111111111112 [入力例] 175558784176642428478886852882855583716348823311266168351117565526517246563464474343713186378358445825842875688328468224747862347184328843234558524873384588623418676322736867374751213285481637258731113376141451225431247636868272855271286637444364837212345678899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911648254724172726886576212874999999999999999999999998761513785328536141681424618172454423262172768855338 798712575381827545576737899297923911446969182444192158293357571521113147117194441699283651197668998739383164988824344734982795349365355256562868136216491554917941957124319167153177952521376528156791156976544147951266159411376581323677263132625248786714518936274126888662385854877456875923693193179271447287133625556351996281293848629914671463858318958835174529758272731193423 [出力例] 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999988876543221111111111111111111111111111111111111122222222222222222222222222222222222222222223333333333333333333333333333333333333344444444444444444444444444444444444444444444555555555555555555555555555555555555666666666666666666666666666666666666666777777777777777777777777777777777777778888888888888888888888888888888888888888888888888888889 999999999999999999999999999999999999999999998888888888888888888888888888888888888877777777777777777777777777777777777777777776666666666666666666666666666666666666655555555555555555555555555555555555555555555444444444444444444444444444444444444333333333333333333333333333333333333333222222222222222222222222222222222222221111111111111111111111111111111111111111111111111111111 |
■C++版プログラム(問題C／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 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 |
// 解き直し. // https://atcoder.jp/contests/arc130/editorial/2976 // -> 解説プログラムを参考に, 実際に, 桁和を計算を行い, 計算結果を比較する場合. // 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--) #define pb push_back int aCount[10], bCount[10]; int main(){ // 1. 入力情報. char s1[101010], s2[101010]; scanf("%s %s", s1, s2); string sa(s1), sb(s2); // 2. a, b を 調整. bool aMinB = true; int al = sa.size(), bl = sb.size(); if(al > bl){ swap(sa, sb); aMinB = false; } // 3. 各桁の数字の出現回数. int lMax = max(al, bl), lMin = min(al, bl); rep(i, lMax){ if(i < lMin) aCount[sa[i] - '0']++; bCount[sb[i] - '0']++; } aCount[0] += lMax - lMin; assert(bCount[0] == 0); // rep(i, 10) printf("%d ", aCount[i]); // puts("\n-----"); // rep(i, 10) printf("%d ", bCount[i]); // puts("\n-----"); // 4. 桁和を求める. auto f = [&](string t1, string t2) -> int { // 4-1. 初期化(ゼロ埋めほか). int ret = 0, carry = 0; string aStr = t1, bStr = t2; string zero(lMax - lMin, '0'); bStr = zero + bStr; // 4-2. 桁和. while(aStr.size()){ // 末尾を取得. int a = aStr.back(); int b = bStr.back(); aStr.pop_back(); bStr.pop_back(); // 桁上がりを考慮して, 加算. int x = (a - '0') + (b - '0') + carry; carry = 0; // 10以上か？ if(x >= 10){ x -= 10; carry = 1; } // 追加. ret += x; } // 4-3. 桁上がり. ret += carry; // 4-4. 返却. return ret; }; // 5. 各桁の並び替え. int kMin = 2020202020; string ans[2]; ans[0] = sa; ans[1] = sb; repx(a0, 1, 10){ // 5-1. 変数を準備. string t[2]; t[0] = ""; t[1] = ""; int ca[10], cb[10]; rep(i, 10){ ca[i] = aCount[i]; cb[i] = bCount[i]; } // 5-2. a[0] + b[0] >= 10 となるものを探す. bool ok = false; if(ca[a0]){ repx(b0, 10 - a0, 10){ // 見つかった場合は, 保存. if(cb[b0]){ t[0].pb(a0 + '0'); t[1].pb(b0 + '0'); ca[a0]--; cb[b0]--; ok = true; break; } } } // 5-3. 見つからなかった場合. // printf("a0=%d t0=%s t1=%s\n", a0, t[0].c_str(), t[1].c_str()); if(!ok) continue; // 5-4. 見つかった場合. repx(a, 1, 10){ repx(b, 9 - a, 10){ if(ca[a]){ // 各数字の出現回数を更新. int l = min(ca[a], cb[b]); ca[a] -= l; cb[b] -= l; // 文字列作成. string aStr(l, a + '0'); string bStr(l, b + '0'); // 文字列追加. t[0] = aStr + t[0]; t[1] = bStr + t[1]; } } } // 5-5. 桁数以上(ゼロを考慮)の場合. if(ca[0]){ if(cb[9]){ // 該当する数字の出現回数を更新. int l = min(ca[0], cb[9]); ca[0] -= l; cb[9] -= l; // 文字列作成. string bStr(l, 9 + '0'); // 文字列追加. t[1] = bStr + t[1]; } } // 5-6. 残り. // -> 降順に追加するように修正. repr(a, 9, 1){ if(ca[a]){ string aStr(ca[a], a + '0'); t[0] = aStr + t[0]; } } repr(b, 9, 1){ if(cb[b]){ string bStr(cb[b], b + '0'); t[1] = bStr + t[1]; } } // 5-7. 桁和. int k = f(t[0], t[1]); // printf("k=%d t0=%s t1=%s", k, t[0].c_str(), t[1].c_str()); // puts("-----"); // 5-8. 桁和の最小値を更新. if(k < kMin){ kMin = k; ans[0] = t[0]; ans[1] = t[1]; } } // 6. 入れ替え. if(!aMinB) swap(ans[0], ans[1]); // 7. 出力. printf("%s\n%s\n", ans[0].c_str(), ans[1].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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
[入力例] 253 286 [出力例] 532 268 ※AtCoderのテストケースより [入力例] 345 556 [出力例] 435 565 ※AtCoderのテストケースより [入力例] 123 987987 [出力例] 312 799788 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 213 899787 [入力例] 11111111111111111111 111111111111111111111111111111 [出力例] 11111111111111111111 111111111111111111111111111111 ※AtCoderのテストケースより [入力例] 33231965444 773455566 [出力例] 19233444563 766555437 [入力例] 13785194584316927589 361659282125285 [出力例] 25599111335446887789 988665553222211 [入力例] 64298525857766878472 985733285545756164339168335839 [出力例] 98888777766655544222 566688899955311333233354455778 [入力例] 31415926535897932384626433832795 28841971693993751 [出力例] 33334455567999932221123456678883 99998876543321117 [入力例] 22175444971457187528782565139685443474229549313625352752311829887254616176822621978974878462694157495375954615447899327541617489148111884227358232886286227889645557945726241681611891958772213477437515 551641763747245118646413653235781313233898374817931453544492522426656592511875353264755952631934534191775794555619912773366291621596845688541515236561 [出力例] 11112222222222222257777777777888899999999999999999111111111111111111111222222222222255555533333333333354444444444444444444444444455555555555555555766666666666666666777777777777778888888888888888888887 999999999999888888888777777777777766666666666666666655555555555555555555555555544444444444444444333333333333333333222222222222221111111111111111111113 [入力例] 596566292477225167124797689822712989922218287694224795251699134214547334585329464159544189788918151193737328351346297845156335816156298861219182734638377894728227668331283653624246257276377836811971862752912774484634753467867376249442665576297677263994726859927416957145424679534826171713328616357727 76564588753992977891167538419732544499251298849996481579385543316893495799434283729514832677617324997637168395535682693663371365536697733465595971514825885974222929187611533998246944634996939819275442 [出力例] 333333444444445555566666666666677777777777777777777777777888888888888899999999999999999999999999999922222222222222222222222111111111111111111111111111111122222222222222222222333333333333333333333444444444444444444444444555555555555555555555566666666666666666666666667777777777777777788888888888888883 99999999999999999999999999999999999888888888888888888877777777777777777777666666666666666666666555555555555555555555555444444444444444444444433333333333333333333333332222222222222222211111111111111117 [入力例] 175558784176642428478886852882855583716348823311266168351117565526517246563464474343713186378358445825842875688328468224747862347184328843234558524873384588623418676322736867374751213285481637258731113376141451225431247636868272855271286637444364837212345678899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911648254724172726886576212874999999999999999999999998761513785328536141681424618172454423262172768855338 798712575381827545576737899297923911446969182444192158293357571521113147117194441699283651197668998739383164988824344734982795349365355256562868136216491554917941957124319167153177952521376528156791156976544147951266159411376581323677263132625248786714518936274126888662385854877456875923693193179271447287133625556351996281293848629914671463858318958835174529758272731193423 [出力例] 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999988876543221111111111111111111111111111111111111122222222222222222222222222222222222222222223333333333333333333333333333333333333344444444444444444444444444444444444444444444555555555555555555555555555555555555666666666666666666666666666666666666666777777777777777777777777777777777777778888888888888888888888888888888888888888888888888888889 999999999999999999999999999999999999999999998888888888888888888888888888888888888877777777777777777777777777777777777777777776666666666666666666666666666666666666655555555555555555555555555555555555555555555444444444444444444444444444444444444333333333333333333333333333333333333333222222222222222222222222222222222222221111111111111111111111111111111111111111111111111111111 |
■参照サイト
AtCoder Regular Contest 130
