C++の練習を兼ねて, AtCoder Beginner Contest 233 の 問題E (Σ[k=0..10^100]floor(X／10^k)) を解いてみた.
■感想.
1. 問題Eは, 規則性を抽出できたので, AC版に到達できたと思う.
2. 個人的には, 文字列操作で, 数式の値を計算できる点が, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 233 解説 を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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 all(x) x.begin(), x.end() LL xCum[505050]; int main(){ // 1. 入力情報. char X[505050]; scanf("%s", X); int xl = strlen(X); // 2. 累積和. rep(i, xl) xCum[i + 1] = xCum[i] + (X[i] - '0'); // 3. 数式計算. LL cur = 0; string ans, sCur; rep(i, xl){ // cur(一の位) を 連結. cur += xCum[xl - i]; sCur = to_string(cur); ans.pb(sCur.back()); // cur更新. sCur.pop_back(); cur = sCur.empty() ? 0 : stoll(sCur); } // 4. sCur の 残り部分. while(!sCur.empty()){ ans.pb(sCur.back()); sCur.pop_back(); } // 5. 反転. reverse(all(ans)); // 6. 出力. 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 |
[入力例] 1225 [出力例] 1360 ※AtCoderテストケースより [入力例] 99999 [出力例] 111105 ※AtCoderテストケースより [入力例] 314159265358979323846264338327950288419716939937510 [出力例] 349065850398865915384738153697722542688574377708317 ※AtCoderテストケースより [入力例] 2022 [出力例] 2246 [入力例] 20220113 [出力例] 22466791 [入力例] 99999999999999999999999999999999999999999999999999 [出力例] 111111111111111111111111111111111111111111111111060 [入力例] 1414213562373095048801688724209698078569671875376948073176679737990732478462107038850387534327641572 [出力例] 1571348402636772276446320804677442309521857639307720081307421931100813864957896709833763927030712805 [入力例] 9465039690052544287964210336050825544228009679340871984835320413138656028459737281236623910738318475221197599613262364812464866655324755821221092211133037516274251841210630051432736133150976832522422811910498103749718745467191658641434790862939619763285208867362914075814532379135342728574115700744736237670180291229335790961022435254588241322299644479124403665543873560838123902436045250773389704122393280276096137717904710238337845435209435565053211109596812055736852625864819104366036314395508017917284938196552386978929495097296123356714573475388624043832849619380113505044143557656041303934449636641560423687119165574111093463814413079614034373343396851681468981704840409761380396202541959237702953945058736591307184716535752522570421388219253081124048134322102930668723327553258017981593648669365309578446323005570228846649186185670506105605174070813173766429797749090127411781445934740635316646127229912315074634805283767052428230698613659200015308575040330926336887197767402712076391971685069 [出力例] 10516710766725049208849122595612028382475566310378746649817022681265173364955263645818471011931464972467997332903624849791627629617027506468023435790147819462526946490234033390480817925723307591691580902122775670833020828296879620712705323181044021959205787630403237862016147087928158587304573000827484708522422545810373101067802705838431379246999604976804892961715415067597915447151161389748210782358214755862329041908783011375930939372454928405614679010663124506374280695405354560406707015995008908796983264662835985532143883441440137063016192750431804493147610688200126116715715064062268115482721818490622692985687961749012326070904903421793371525937107612979409979672044899734867106891713288041892171050065262879230205240595280580633801542465836756804497927024558811854137030614731131090659609632628121753829247783966920940721317984078340117339082300903526407144219721211252679757162149711817018495696922124794527372005870852280475811887348510222239231750044812140374319108630447457862657746316268 |
■参照サイト
AtCoder Beginner Contest 233