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

C++の練習を兼ねて, AtCoder Beginner Contest 192 の問題C (Kaprekar Number) ～問題D (Base n) を解いてみた.

■感想.
1. 久しぶりに解説見る前に, AC版に到達できたので, 良かったと思う
2. とはいえ, 正しく実装するために, 非常に苦労したように思う.
3. 二分探索の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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--)
#define all(x) x.begin(), x.end()
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. a[K] を 出力.
    // -> random_01.txt などで, WA版となったため, 修正.
    // -> 降順ソートの場合は, 末尾のゼロが並ぶことが許容される(仮定を追加).
    auto f = [&](int n){
        string sg1 = to_string(n);
        sort(all(sg1));
        reverse(all(sg1));
        string sg2 = "";
        repr(i, sg1.size() - 1, 0) if(sg1[i] != '0') sg2.pb(sg1[i]);
        sort(all(sg2));
        int g1 = (sg1.size() == 0) ? 0 : stoi(sg1);
        int g2 = (sg2.size() == 0) ? 0 : stoi(sg2);
        return g1 - g2;
    };
    int ans = N;
    rep(i, K) ans = f(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--)

#define all(x) x.begin(), x.end()

#define pb push_back

int main(){

// 1. 入力情報.

int N, K;

scanf("%d %d", &N, &K);

// 2. a[K] を出力.

// -> random_01.txt などで, WA版となったため, 修正.

// -> 降順ソートの場合は, 末尾のゼロが並ぶことが許容される(仮定を追加).

auto f = [&](int n){

string sg1 = to_string(n);

sort(all(sg1));

reverse(all(sg1));

string sg2 = "";

repr(i, sg1.size() - 1, 0) if(sg1[i] != '0') sg2.pb(sg1[i]);

sort(all(sg2));

int g1 = (sg1.size() == 0) ? 0 : stoi(sg1);

int g2 = (sg2.size() == 0) ? 0 : stoi(sg2);

return g1 - g2;

};

int ans = N;

rep(i, K) ans = f(ans);

// 3. 出力.

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

return 0;

}

[入力例]
314 2

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

[入力例]
1000000000 100

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

[入力例]
6174 100000

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

[入力例]
100 1

[出力例]
99

[入力例]
100 2

[出力例]
0

[入力例]
2021 220

[出力例]
6174

[入力例]
20210220 1

[出力例]
22208778

[入力例]
20210220 2

[出力例]
86544432

[入力例]
20210220 22

[出力例]
43208766

[入力例]

314 2

[出力例]

693

※AtCoderテストケースより

[入力例]

1000000000 100

[出力例]

※AtCoderテストケースより

[入力例]

6174 100000

[出力例]

6174

※AtCoderテストケースより

[入力例]

100 1

[出力例]

[入力例]

100 2

[出力例]

[入力例]

2021 220

[出力例]

6174

[入力例]

20210220 1

[出力例]

22208778

[入力例]

20210220 2

[出力例]

86544432

[入力例]

20210220 22

[出力例]

43208766

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

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

int main(){
    
    // 1. 入力情報.
    char x[111];
    LL M;
    scanf("%s %lld", x, &M);
    string X(x);
    int sx = X.size();
    
    // 2. X に 含まれる最大の数字は？
    int d = 0;
    rep(i, sx) d = max(d, X[i] - '0');
    
    // 3. X が 一桁 の 場合.
    if(sx == 1){
        // -> one_digit_01.txt などで, WA版となったため, 修正.
        // printf("%lld\n", max(0LL, M - (X[0] - '0')));
        // -> X が 一桁 の 場合は, (d + 1)以上の整数を選べない？(仮定 -> 誤り).
        // puts("0");
        // -> X が 一桁 の 場合は, M が, (d + 1)以上の場合は, 1通り？(仮定 -> 誤り, one_digit_01.txtなど).
        // printf("%d\n", (M > (LL)d) ? 1 : 0);
        // -> X が 一桁 の 場合は, M が, d以上の場合は, 1通り？(仮定).
        printf("%d\n", (M >= (LL)d) ? 1 : 0);
        return 0;
    }
    
    // 4. X が 二桁 の 場合.
    if(sx == 2){
        LL s = (LL)max(X[0] - '0', X[1] - '0');
        LL e = (M - (X[1] - '0')) / (X[0] - '0');
        printf("%lld\n", max(0LL, e - s));
        return 0;
    }
    
    // 5. X が 三桁 の 場合.
    if(sx == 3){
        LL x0 = X[0] - '0', x1 = X[1] - '0', x2 = X[2] - '0';
        LL s = max({x0, x1, x2});
        // 二分探索で確認してみる.
        LL l = s, h = 1e9 + 1, m;
        while(l + 1 < h){
            m = (h + l) >> 1;
            if(m * m * x0 + m * x1 + x2 > M) h = m;
            else                             l = m;
            // printf("h=%lld l=%lld m=%lld\n", h, l, m);
        }
        LL e = l;
        printf("%lld\n", max(0LL, e - s));
        return 0;
    }
    
    // 6. M以下をカウントする.
    int ans = 0;
    auto f = [&](int l){
        // 6-1. l の 冪乗 を 計算.
        vector<LL> mPow;
        mPow.pb(1);
        repx(i, 1, sx){
            LL p = (LL)l * mPow[i - 1];
            if(p > M) return false;
            mPow.pb(p);
        }
        
        // 6-2. X を l進数 で, 表記.
        LL lx = 0;
        repr(i, sx - 1, 0){
            lx += (LL)(X[i] - '0') * mPow[sx - 1 - i];
            if(lx > M) return false;
        }
        return true;
    };
    repx(i, d + 1, 1010101){
        if(f(i)) ans++;
        else     break;
    }
    
    // 7. 出力.
    printf("%d\n", ans);
    return 0;
    
}

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

int main(){

// 1. 入力情報.

char x[111];

LL M;

scanf("%s %lld", x, &M);

string X(x);

int sx = X.size();

// 2. X に含まれる最大の数字は？

int d = 0;

rep(i, sx) d = max(d, X[i] - '0');

// 3. X が一桁の場合.

if(sx == 1){

// -> one_digit_01.txt などで, WA版となったため, 修正.

// printf("%lld\n", max(0LL, M - (X[0] - '0')));

// -> X が一桁の場合は, (d + 1)以上の整数を選べない？(仮定 -> 誤り).

// puts("0");

// -> X が一桁の場合は, M が, (d + 1)以上の場合は, 1通り？(仮定 -> 誤り, one_digit_01.txtなど).

// printf("%d\n", (M > (LL)d) ? 1 : 0);

// -> X が一桁の場合は, M が, d以上の場合は, 1通り？(仮定).

printf("%d\n", (M >= (LL)d) ? 1 : 0);

return 0;

}

// 4. X が二桁の場合.

if(sx == 2){

LL s = (LL)max(X[0] - '0', X[1] - '0');

LL e = (M - (X[1] - '0')) / (X[0] - '0');

printf("%lld\n", max(0LL, e - s));

return 0;

}

// 5. X が三桁の場合.

if(sx == 3){

LL x0 = X[0] - '0', x1 = X[1] - '0', x2 = X[2] - '0';

LL s = max({x0, x1, x2});

// 二分探索で確認してみる.

LL l = s, h = 1e9 + 1, m;

while(l + 1 < h){

m = (h + l) >> 1;

if(m * m * x0 + m * x1 + x2 > M) h = m;

else l = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

LL e = l;

printf("%lld\n", max(0LL, e - s));

return 0;

}

// 6. M以下をカウントする.

int ans = 0;

auto f = [&](int l){

// 6-1. l の冪乗を計算.

vector<LL> mPow;

mPow.pb(1);

repx(i, 1, sx){

LL p = (LL)l * mPow[i - 1];

if(p > M) return false;

mPow.pb(p);

}

// 6-2. X を l進数で, 表記.

LL lx = 0;

repr(i, sx - 1, 0){

lx += (LL)(X[i] - '0') * mPow[sx - 1 - i];

if(lx > M) return false;

}

return true;

};

repx(i, d + 1, 1010101){

if(f(i)) ans++;

else break;

}

// 7. 出力.

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

return 0;

}

[入力例]
22
10

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

[入力例]
999
1500

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

[入力例]
100000000000000000000000000000000000000000000000000000000000
1000000000000000000

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

[入力例]
1
1

[出力例]
1

[入力例]
2
1

[出力例]
0

[入力例]
7
10

[出力例]
1

[入力例]
12
15

[出力例]
11

[入力例]
99
15

[出力例]
0

[入力例]
123
1000000000000000000

[出力例]
999999995

[入力例]
234
1000000000000000000

[出力例]
707106776

[入力例]
567
1000000000000000000

[出力例]
447213587

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

999

1500

[出力例]

※AtCoderテストケースより

[入力例]

100000000000000000000000000000000000000000000000000000000000

1000000000000000000

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

123

1000000000000000000

[出力例]

999999995

[入力例]

234

1000000000000000000

[出力例]

707106776

[入力例]

567

1000000000000000000

[出力例]

447213587

■参照サイト
SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)

C++の練習を兼ねて, AtCoder Beginner Contest 192 の 問題C (Kaprekar Number) ～ 問題D (Base n) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 192 の問題C (Kaprekar Number) ～問題D (Base n) を解いてみた.

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