C++の練習を兼ねて, AtCoder Beginner Contest 029 の 問題D (D – 1) を解いてみた.
■感想.
1. 現在見ている桁(cur) と その左側の桁 に含まれる 1の個数(one) を 考慮 し, その加減算を行う条件を抽出するのに, 時間かかってしまった.
※なお, 解法イメージとしては, N = 123456 の 場合,
1 ～ 100000
100001 ～ 110000, 110001 ～ 120000
120001 ～ 121000, 120001 ～ 122000, 122001 ～ 123000
～(略)～
123401 ～ 123410, 123411 ～ 123420, 123421 ～ 123430, 123431 ～ 123440, 123441 ～ 123450
123451 ～ 123456
のように, 区切りを設けて解いていく方針で実装した.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 029解説をご覧下さい.
■C++版プログラム(問題D／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 |
// コメントを修正して, 再提出. #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--) // c[0] … 1 ～ 1: 1回 // c[1] … 1 ～ 10: 2回 // c[2] … 1 ～ 100: 21回 (= (c[1] - 1) * 10 + 10 + 1) // c[3] … 1 ～ 1000: 301回 (= (c[2] - 1) * 10 + 100 + 1) // c[4] … 1 ～ 10000: 4001回 (= (c[3] - 1) * 10 + 1000 + 1) // c[5] … 1 ～ 100000: 50001回 (= (c[4] - 1) * 10 + 10000 + 1) // ... const LL c[] = {1, 2, 21, 301, 4001, 50001, 600001, 7000001, 80000001, 900000001, 10000000001, 200000000001}; const LL p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000}; int main(){ // 1. 入力情報. char a[22]; scanf("%s", a); string N(a); // 2. '1' の 出現回数は？ // -> 0 ～ (l - 1)桁 で 考える. int l = N.size(); LL ans = 0; rep(i, l){ // 2-0. 上限設定. int u = N[i] - '0'; rep(j, u){ // 2-1. 現在確認する桁. char cur = j + '0'; // 2-2. i桁目よりも左側 の '1' の 個数. LL one = 0; rep(k, i) if(N[k] == '1') one++; // 2-3. i桁目よりも左側 の '1' の 個数 を カウント. ans += one * p10[l - 1 - i]; // 2-4. 現在確認する桁が, '1' の 場合, 追加分 を カウント. ans += (p10[l - 1 - i] - 1) * (cur == '1'); // 2-5. i桁目における c[l - 1 - i] を カウント. ans += c[l - 1 - i]; // 2-6. i桁目が, '1' 以上 の 場合, 減算. ans -= (LL)(cur > '0'); } } // 3. 出力. printf("%lld\n", ans); 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 |
[入力例] 12 [出力例] 5 ※AtCoderテストケースより [入力例] 345 [出力例] 175 ※AtCoderテストケースより [入力例] 999999999 [出力例] 900000000 ※AtCoderテストケースより [入力例] 123 [出力例] 57 [入力例] 213145 [出力例] 209127 [入力例] 654321 [出力例] 432373 [入力例] 314159265 [出力例] 354702389 [入力例] 888777666 [出力例] 812291337 [入力例] 301205670 [出力例] 341008408 [入力例] 1234567890 [出力例] 1429355270 |
■参照サイト
AtCoder Beginner Contest 029