C++ の動作確認をしてみた（３６３）

C++の練習を兼ねて, AtCoder Beginner Contest 186 の問題C (Unlucky 7) ～問題D (Sum of difference) を解いてみた.

■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できたので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Beginner Contest 186 解説の各リンクをご覧下さい.

■C++版プログラム(問題C／AC版).

// 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 main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 10進法, 8進法のいずれにおいても 7 を含まないような数はいくつあるか？
    int ans = 0;
    repx(i, 1, N + 1){
        // 10進数に含まれる 7 を カウント.
        int cnt7 = 0;
        string s10 = to_string(i);
        rep(j, s10.size()) if(s10[j] == '7') cnt7++;
        
        // 8進数に含まれる 7 を カウント.
        int n8 = i;
        string s8 = "";
        while(n8){
            int r = n8 % 8;
            s8 = s8 + to_string(r);
            n8 -= r;
            n8 /= 8;
        }
        rep(j, s8.size()) if(s8[j] == '7') cnt7++;
        
        // 7が含まれない場合にカウント.
        if(!cnt7) ans++;
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 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 main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 10進法, 8進法のいずれにおいても 7 を含まないような数はいくつあるか？

int ans = 0;

repx(i, 1, N + 1){

// 10進数に含まれる 7 をカウント.

int cnt7 = 0;

string s10 = to_string(i);

rep(j, s10.size()) if(s10[j] == '7') cnt7++;

// 8進数に含まれる 7 をカウント.

int n8 = i;

string s8 = "";

while(n8){

int r = n8 % 8;

s8 = s8 + to_string(r);

n8 -= r;

n8 /= 8;

}

rep(j, s8.size()) if(s8[j] == '7') cnt7++;

// 7が含まれない場合にカウント.

if(!cnt7) ans++;

}

// 3. 出力.

printf("%d\n", ans);

return 0;

}

[入力例]
20

[出力例]
17
※AtCoderテストケースより

[入力例]
100000

[出力例]
30555
※AtCoderテストケースより

[入力例]
202020

[出力例]
61743
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]
10101010

[出力例]
1947390
※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100000

[出力例]

30555

※AtCoderテストケースより

[入力例]

202020

[出力例]

61743

※整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

10101010

[出力例]

1947390

※整数 N が, 問題文の制約条件から範囲外であるケース.

■C++版プログラム(問題D／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc186/editorial/402
// 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--)
LL a[202020], aCum[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. 累積和.
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 4. 数式を計算.
    LL ans = 0;
    rep(i, N - 1) ans += (aCum[N] - aCum[i + 1]) - (LL)(N - 1 - i) * a[i];
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc186/editorial/402

// 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--)

LL a[202020], aCum[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &a[i]);

// 2. sort.

sort(a, a + N);

// 3. 累積和.

rep(i, N) aCum[i + 1] = aCum[i] + a[i];

// 4. 数式を計算.

LL ans = 0;

rep(i, N - 1) ans += (aCum[N] - aCum[i + 1]) - (LL)(N - 1 - i) * a[i];

// 5. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
3
5 1 2

[出力例]
8
※AtCoderテストケースより

[入力例]
5
31 41 59 26 53

[出力例]
176
※AtCoderテストケースより

[入力例]
108
85 49 27 41 72 63 10 11 90 89 12 102 113 3 111 4 109 119 26 33 90 89 54 85 22 74 91 102 44 17 79 59 24 41 8 102 28 46 85 108 100 27 62 89 49 36 95 90 25 3 117 2 6 96 65 70 30 94 99 49 111 9 25 41 23 54 49 25 97 110 107 63 72 100 115 76 39 95 7 84 91 4 66 43 43 106 18 12 66 103 37 111 100 6 42 107 33 31 78 66 92 49 47 16 71 60 2 83

[出力例]
237882

[入力例]
200
3524357 8134394 4103535 2219068 10018269 4531721 5374474 908789 10250809 395081 9165350 2688326 374440 1957442 4952309 5242075 11521902 9435499 3255998 6022086 6160393 5762768 11655855 8494892 10091410 8582569 3605701 494592 551272 1662252 3114124 2033005 10208757 5313239 4805960 12154882 827749 933392 5087432 9247598 933232 748742 8646326 1425859 4535423 9524987 11448216 6806596 9440201 9612648 7940675 5482848 6901602 284056 6093771 5415829 3683972 9138182 512713 2283654 2618351 4843043 167331 8103587 6671007 9954374 9637020 9198793 6620286 11110860 8692388 3487772 899392 8364338 11511552 779670 1606709 3513398 6869982 11490993 7135507 2989059 6857301 3297696 9836880 3311759 70888 7159977 3796541 2299939 5848272 9497059 6507417 8977098 2530832 4854926 9295736 5487619 10679470 8611402 11560240 9361303 7512766 1228902 10586948 3257468 4205839 4419361 5882882 3953152 1352315 9652677 821460 4502126 6447880 8880691 1406215 8099495 3776291 1457242 7404120 5367572 8948860 1054911 1737624 3903594 3319571 4656853 11361677 11324213 4584131 9502822 11916319 10037089 9540881 7011962 7868996 7737398 9131981 10505923 3306631 12160200 10982495 1756298 12183829 2065298 2685281 10364142 9413992 8048846 8551618 7289727 12069919 8175453 6981668 10471294 250164 1041305 8160645 1459769 9073487 484159 9925124 9743374 6096314 3426705 5261003 4064989 4339483 3342096 3838347 4916363 11924766 6015885 9808324 5594189 90647 4515044 3131236 9334340 579173 2127740 10168303 6234472 5133629 11419579 6964610 9677896 5982788 6556159 3779312 11932660 4271348 11144937 9617303 3278339 1399072 7737730 7533242 2083918

[出力例]
81238850695

[入力例]

5 1 2

[出力例]

※AtCoderテストケースより

[入力例]

31 41 59 26 53

[出力例]

176

※AtCoderテストケースより

[入力例]

108

85 49 27 41 72 63 10 11 90 89 12 102 113 3 111 4 109 119 26 33 90 89 54 85 22 74 91 102 44 17 79 59 24 41 8 102 28 46 85 108 100 27 62 89 49 36 95 90 25 3 117 2 6 96 65 70 30 94 99 49 111 9 25 41 23 54 49 25 97 110 107 63 72 100 115 76 39 95 7 84 91 4 66 43 43 106 18 12 66 103 37 111 100 6 42 107 33 31 78 66 92 49 47 16 71 60 2 83

[出力例]

237882

[入力例]

200

3524357 8134394 4103535 2219068 10018269 4531721 5374474 908789 10250809 395081 9165350 2688326 374440 1957442 4952309 5242075 11521902 9435499 3255998 6022086 6160393 5762768 11655855 8494892 10091410 8582569 3605701 494592 551272 1662252 3114124 2033005 10208757 5313239 4805960 12154882 827749 933392 5087432 9247598 933232 748742 8646326 1425859 4535423 9524987 11448216 6806596 9440201 9612648 7940675 5482848 6901602 284056 6093771 5415829 3683972 9138182 512713 2283654 2618351 4843043 167331 8103587 6671007 9954374 9637020 9198793 6620286 11110860 8692388 3487772 899392 8364338 11511552 779670 1606709 3513398 6869982 11490993 7135507 2989059 6857301 3297696 9836880 3311759 70888 7159977 3796541 2299939 5848272 9497059 6507417 8977098 2530832 4854926 9295736 5487619 10679470 8611402 11560240 9361303 7512766 1228902 10586948 3257468 4205839 4419361 5882882 3953152 1352315 9652677 821460 4502126 6447880 8880691 1406215 8099495 3776291 1457242 7404120 5367572 8948860 1054911 1737624 3903594 3319571 4656853 11361677 11324213 4584131 9502822 11916319 10037089 9540881 7011962 7868996 7737398 9131981 10505923 3306631 12160200 10982495 1756298 12183829 2065298 2685281 10364142 9413992 8048846 8551618 7289727 12069919 8175453 6981668 10471294 250164 1041305 8160645 1459769 9073487 484159 9925124 9743374 6096314 3426705 5261003 4064989 4339483 3342096 3838347 4916363 11924766 6015885 9808324 5594189 90647 4515044 3131236 9334340 579173 2127740 10168303 6234472 5133629 11419579 6964610 9677896 5982788 6556159 3779312 11932660 4271348 11144937 9617303 3278339 1399072 7737730 7533242 2083918

[出力例]

81238850695

■参照サイト
パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）

C++の練習を兼ねて, AtCoder Beginner Contest 186 の 問題C (Unlucky 7) ～ 問題D (Sum of difference) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 186 の問題C (Unlucky 7) ～問題D (Sum of difference) を解いてみた.

コメントを残すコメントをキャンセル