C++ の動作確認をしてみた（８４２）

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題C (Circular Addition) ～問題D (Without Carry) を解いてみた.

■感想.
1. 問題C, D は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. なお, 問題D は, dominate と繰り上がりとの関係性が理解しずらかったため, 実装後に, 解説プログラムを確認し, 実装誤り部分を修正して(特に, 重複カウント部分の減算に関する処理と思われる箇所), 提出した版である.
3. 問題D で, 高速ゼータ変換に関する考え方に触れることが出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc136/editorial/3466
// 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];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. M, D を 計算.
    LL M = 0, D = 0;
    rep(i, N){
        M = max(M, a[i]);
        if(i < N - 1) D += abs(a[i] - a[i + 1]);
        else          D += abs(a[0] - a[N - 1]);
    }
    D /= 2;
    
    // 3. 出力.
    printf("%lld\n", max(M, D));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc136/editorial/3466

// 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];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. M, D を計算.

LL M = 0, D = 0;

rep(i, N){

M = max(M, a[i]);

if(i < N - 1) D += abs(a[i] - a[i + 1]);

else D += abs(a[0] - a[N - 1]);

}

D /= 2;

// 3. 出力.

printf("%lld\n", max(M, D));

return 0;

}

[入力例]
4
1 2 1 2

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

[入力例]
5
3 1 4 1 5

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

[入力例]
1
1000000000

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

[入力例]
10
71 102 33 82 29 64 94 56 50 105

[出力例]
200

[入力例]
100
777 778 255 1899 1530 269 1878 1515 963 1701 369 1654 634 1195 911 860 1184 1011 1089 425 1927 1019 1562 1709 1766 1119 820 1878 1972 867 1266 1819 299 305 160 1843 1016 595 27 1226 922 172 1123 867 7 1475 632 739 492 347 493 998 535 898 1241 764 1358 129 189 277 1905 215 841 2000 1206 1431 439 1974 1543 710 517 941 359 1033 564 487 5 1030 320 671 1113 1956 774 54 1424 895 303 771 632 780 363 1890 320 137 656 1320 281 1318 1880 998

[出力例]
33333

[入力例]

1 2 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 1 4 1 5

[出力例]

※AtCoderのテストケースより

[入力例]

1000000000

[出力例]

1000000000

※AtCoderのテストケースより

[入力例]

71 102 33 82 29 64 94 56 50 105

[出力例]

200

[入力例]

100

777 778 255 1899 1530 269 1878 1515 963 1701 369 1654 634 1195 911 860 1184 1011 1089 425 1927 1019 1562 1709 1766 1119 820 1878 1972 867 1266 1819 299 305 160 1843 1016 595 27 1226 922 172 1123 867 7 1475 632 739 492 347 493 998 535 898 1241 764 1358 129 189 277 1905 215 841 2000 1206 1431 439 1974 1543 710 517 941 359 1033 564 487 5 1030 320 671 1113 1956 774 54 1424 895 303 771 632 780 363 1890 320 137 656 1320 281 1318 1880 998

[出力例]

33333

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

// 解き直し.
// https://atcoder.jp/contests/arc136/editorial/3465
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
#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 a[1010101];
LL dp[2020202];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 10 の 冪乗.
    int L = 6;
    vi cPow10;
    cPow10.pb(1);
    while(cPow10.size() <= L) cPow10.pb(10 * cPow10.back());
    
    // 3. dp更新.
    // -> 各a[i] を起点として, dominate に関する情報を, dp更新式で, 集計.
    rep(i, N) ++dp[a[i]];
    rep(j, L){
        rep(i, cPow10[L]){
            int q = i / cPow10[j];
            int r = q % 10;
            if(r < 9) dp[i + cPow10[j]] += dp[i];
        }
    }
    
    // 4. 集計.
    // 以下の解説プログラム参照.
    // https://atcoder.jp/contests/arc136/submissions/29411459
    LL ans = 0;
    rep(i, N){
        // Skip.
        if(!dp[cPow10[L] - 1 - a[i]]) continue;
        
        // 加算(dominate の 集計結果).
        // -> 各a[i] について, dp から 繰り上がりしているかどうかを見る場合は, 
        //    dominate の 考え方に基づいて, cPow10[L] - 1 - a[i] から, 判断する点に注意.
        ans += dp[cPow10[L] - 1 - a[i]];
        
        // 繰り上がりしているか否か.
        int q = a[i];
        bool ok = false;
        rep(j, L){
            int r = q % 10;
            if(r >= 5) ok = true;
            q /= 10;
        }
        
        // 減算(おそらく, 繰り上がりして "いない" ケースは, 重複で数えていると解釈するらしい).
        if(!ok) --ans;
    }
    
    // 5. 出力.
    printf("%lld\n", ans / 2);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc136/editorial/3465

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

#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 a[1010101];

LL dp[2020202];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 10 の冪乗.

int L = 6;

vi cPow10;

cPow10.pb(1);

while(cPow10.size() <= L) cPow10.pb(10 * cPow10.back());

// 3. dp更新.

// -> 各a[i] を起点として, dominate に関する情報を, dp更新式で, 集計.

rep(i, N) ++dp[a[i]];

rep(j, L){

rep(i, cPow10[L]){

int q = i / cPow10[j];

int r = q % 10;

if(r < 9) dp[i + cPow10[j]] += dp[i];

}

// 4. 集計.

// 以下の解説プログラム参照.

// https://atcoder.jp/contests/arc136/submissions/29411459

LL ans = 0;

rep(i, N){

// Skip.

if(!dp[cPow10[L] - 1 - a[i]]) continue;

// 加算(dominate の集計結果).

// -> 各a[i] について, dp から繰り上がりしているかどうかを見る場合は,

// dominate の考え方に基づいて, cPow10[L] - 1 - a[i] から, 判断する点に注意.

ans += dp[cPow10[L] - 1 - a[i]];

// 繰り上がりしているか否か.

int q = a[i];

bool ok = false;

rep(j, L){

int r = q % 10;

if(r >= 5) ok = true;

q /= 10;

}

// 減算(おそらく, 繰り上がりして "いない" ケースは, 重複で数えていると解釈するらしい).

if(!ok) --ans;

}

// 5. 出力.

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

return 0;

}

[入力例]
4
4 8 12 90

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

[入力例]
20
313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908

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

[入力例]
5
1 1 1 1 1

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

[入力例]
10
12 15 28 30 33 47 52 61 72 81

[出力例]
23

[入力例]
50
73 2 99 15 24 117 115 104 104 90 28 36 83 5 35 115 32 49 20 90 80 25 37 95 98 112 93 3 92 8 72 21 90 118 106 17 98 88 40 46 59 83 85 6 25 64 18 54 119 78

[出力例]
334

[入力例]
300
77777 100191 3141 72381 88888 89264 112738 18295 99999 74111 111111 56267 15131 59124 29354 50538 15200 118291 106621 6954 64325 19574 87600 101010 101010 91749 24130 99999 16645 42360 97636 53268 19981 7983 112934 16693 111111 53051 35741 95710 108291 48780 92605 69904 117734 96974 18803 27990 30856 55295 26860 19664 39658 102350 60830 22358 54462 57928 95038 101010 21238 65826 21844 35987 8759 79919 58382 98650 121756 94754 90627 59551 46070 57713 62686 95762 13580 49759 85685 53493 97168 18566 24523 54415 97632 76598 26417 74914 32918 68505 84746 115100 78161 93752 55606 93493 9142 73351 107531 101010 28262 67198 114766 96968 11472 61629 79328 120269 71342 42949 85685 9954 88888 81691 106340 79492 94133 98212 3218 71808 18202 101010 94154 105925 57115 14174 20327 37548 23723 51748 41437 75163 59384 55886 62085 12030 72110 40612 104190 8632 101010 61313 77777 85724 86475 37230 88888 25160 1894 58666 95972 106212 114828 89842 77539 14728 96997 111254 5480 96808 94846 121364 33333 72941 59833 39288 82818 89814 54956 24421 15098 111111 79408 111111 74272 115159 121188 118736 18120 25301 28807 23059 12232 101492 88888 99999 74435 37640 18807 66924 72570 106351 111111 11578 37304 47366 106791 12098 51621 120445 21618 50865 87371 37123 99999 42850 90816 40761 16328 87966 66391 66073 41298 99996 12674 20953 82396 53977 19794 101010 31303 107657 88888 115737 75017 28616 77777 93695 106440 102631 115693 22015 40374 17325 32202 112271 27818 23076 13804 59979 53090 68177 91002 88104 4519 30863 106347 56756 81872 70403 37573 101010 101010 81003 63251 66193 47642 26479 50171 121360 97946 64862 121158 72978 32948 27493 89543 23379 771 112381 105968 113218 37324 15276 39985 2700 34627 94999 47999 19957 119916 99999 118865 68160 50445 77777 13770 11611 71834 77777 88888 95468 20369 46059 105334 101010 70265 22222 101010 82059

[出力例]
5602

[入力例]

4 8 12 90

[出力例]

※AtCoderのテストケースより

[入力例]

313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 1 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

12 15 28 30 33 47 52 61 72 81

[出力例]

[入力例]

73 2 99 15 24 117 115 104 104 90 28 36 83 5 35 115 32 49 20 90 80 25 37 95 98 112 93 3 92 8 72 21 90 118 106 17 98 88 40 46 59 83 85 6 25 64 18 54 119 78

[出力例]

334

[入力例]

300

77777 100191 3141 72381 88888 89264 112738 18295 99999 74111 111111 56267 15131 59124 29354 50538 15200 118291 106621 6954 64325 19574 87600 101010 101010 91749 24130 99999 16645 42360 97636 53268 19981 7983 112934 16693 111111 53051 35741 95710 108291 48780 92605 69904 117734 96974 18803 27990 30856 55295 26860 19664 39658 102350 60830 22358 54462 57928 95038 101010 21238 65826 21844 35987 8759 79919 58382 98650 121756 94754 90627 59551 46070 57713 62686 95762 13580 49759 85685 53493 97168 18566 24523 54415 97632 76598 26417 74914 32918 68505 84746 115100 78161 93752 55606 93493 9142 73351 107531 101010 28262 67198 114766 96968 11472 61629 79328 120269 71342 42949 85685 9954 88888 81691 106340 79492 94133 98212 3218 71808 18202 101010 94154 105925 57115 14174 20327 37548 23723 51748 41437 75163 59384 55886 62085 12030 72110 40612 104190 8632 101010 61313 77777 85724 86475 37230 88888 25160 1894 58666 95972 106212 114828 89842 77539 14728 96997 111254 5480 96808 94846 121364 33333 72941 59833 39288 82818 89814 54956 24421 15098 111111 79408 111111 74272 115159 121188 118736 18120 25301 28807 23059 12232 101492 88888 99999 74435 37640 18807 66924 72570 106351 111111 11578 37304 47366 106791 12098 51621 120445 21618 50865 87371 37123 99999 42850 90816 40761 16328 87966 66391 66073 41298 99996 12674 20953 82396 53977 19794 101010 31303 107657 88888 115737 75017 28616 77777 93695 106440 102631 115693 22015 40374 17325 32202 112271 27818 23076 13804 59979 53090 68177 91002 88104 4519 30863 106347 56756 81872 70403 37573 101010 101010 81003 63251 66193 47642 26479 50171 121360 97946 64862 121158 72978 32948 27493 89543 23379 771 112381 105968 113218 37324 15276 39985 2700 34627 94999 47999 19957 119916 99999 118865 68160 50445 77777 13770 11611 71834 77777 88888 95468 20369 46059 105334 101010 70265 22222 101010 82059

[出力例]

5602

■参照サイト
AtCoder Regular Contest 136

C++の練習を兼ねて, AtCoder Regular Contest 136 の 問題C (Circular Addition) ～ 問題D (Without Carry) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題C (Circular Addition) ～問題D (Without Carry) を解いてみた.

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