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

C++の練習を兼ねて, AtCoder Beginner Contest 193 の問題C (Unexpressed) ～問題D (Poker) を解いてみた.

■感想.
1. 久しぶりに, 解説見る前に, 解法の糸口が見つけることが出来たと思う.
2. 確率・組み合わせ関連は, 全般的に苦手なので, 今後も, 過去問を通して, 少しずつ理解を深めていきたいと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■C++版プログラム(問題C／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--)

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. a, b の 組み合わせをカウント.
    int ans = 0, n = (int)sqrt(N) + 1;
    set<LL> st;
    repx(i, 2, n){
        LL a = (LL)i;
        LL c = a;
        while(1){
            c *= a;
            if(c <= N) st.insert(c);
            else       break;
        }
    }
    
    // 3. 出力.
    printf("%lld\n", N - (LL)(st.size()));
    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--)

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. a, b の組み合わせをカウント.

int ans = 0, n = (int)sqrt(N) + 1;

set<LL> st;

repx(i, 2, n){

LL a = (LL)i;

LL c = a;

while(1){

c *= a;

if(c <= N) st.insert(c);

else break;

}

// 3. 出力.

printf("%lld\n", N - (LL)(st.size()));

return 0;

}

[入力例]
8

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

[入力例]
100000

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

[入力例]
16

[出力例]
12

[入力例]
25

[出力例]
20

[入力例]
2021

[出力例]
1966

[入力例]
20210227

[出力例]
20205442

[入力例]
10000000000

[出力例]
9999897770

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100000

[出力例]

99634

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

2021

[出力例]

1966

[入力例]

20210227

[出力例]

20205442

[入力例]

10000000000

[出力例]

9999897770

■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--)
const int cPow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int cs[10], ct[10];

int main(){
    
    // 1. 入力情報.
    int K;
    char S[11], T[11];
    scanf("%d %s %s", &K, S, T);
    
    // 2. 表向きのカードに関する得点情報.
    rep(i, 4) cs[S[i] - '0']++, ct[T[i] - '0']++;
    
    // 3. 確定している得点情報.
    int sFix = 0, tFix = 0;
    repx(i, 1, 10) sFix += i * cPow10[cs[i]], tFix += i * cPow10[ct[i]];
    
    // 4. 5文字目の組み合わせを全探索.
    auto score = [&](int* c, int i, int base){
        int ret = base;
        ret -= i * cPow10[c[i]];
        ret += i * cPow10[c[i] + 1];
        return ret;
    };
    LL total = 0, win = 0;
    repx(i, 1, 10){
        repx(j, 1, 10){
            // 4-1. 異なる数字の場合.
            if(i != j){
                // 手札のパターンとしてありうるか.
                if(cs[i] + ct[i] >= K) continue;
                if(cs[j] + ct[j] >= K) continue;
                
                // 高橋くんの得点.
                int t = score(cs, i, sFix);
                
                // 青木くんの得点.
                int a = score(ct, j, tFix);
                
                // 評価.
                LL count = (LL)(K - cs[i] - ct[i]) * (LL)(K - cs[j] - ct[j]);
                if(t > a) win += count;
                total += count;
            }
            
            // 4-2. 同じ数字の場合.
            if(i == j){
                // 手札のパターンとしてありうるか.
                if(cs[i] + ct[i] + 1 >= K) continue;
                
                // 高橋くんの得点.
                int t = score(cs, i, sFix);
                
                // 青木くんの得点.
                int a = score(ct, j, tFix);
                
                // 評価.
                LL count = (LL)(K - cs[i] - ct[i]) * (LL)(K - cs[i] - ct[i] - 1);
                if(t > a) win += count;
                total += count;
            }
        }
    }
    
    // 5. 出力.
    printf("%.16lf\n", (double)win / (double)total);
    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--)

const int cPow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000};

int cs[10], ct[10];

int main(){

// 1. 入力情報.

int K;

char S[11], T[11];

scanf("%d %s %s", &K, S, T);

// 2. 表向きのカードに関する得点情報.

rep(i, 4) cs[S[i] - '0']++, ct[T[i] - '0']++;

// 3. 確定している得点情報.

int sFix = 0, tFix = 0;

repx(i, 1, 10) sFix += i * cPow10[cs[i]], tFix += i * cPow10[ct[i]];

// 4. 5文字目の組み合わせを全探索.

auto score = [&](int* c, int i, int base){

int ret = base;

ret -= i * cPow10[c[i]];

ret += i * cPow10[c[i] + 1];

return ret;

};

LL total = 0, win = 0;

repx(i, 1, 10){

repx(j, 1, 10){

// 4-1. 異なる数字の場合.

if(i != j){

// 手札のパターンとしてありうるか.

if(cs[i] + ct[i] >= K) continue;

if(cs[j] + ct[j] >= K) continue;

// 高橋くんの得点.

int t = score(cs, i, sFix);

// 青木くんの得点.

int a = score(ct, j, tFix);

// 評価.

LL count = (LL)(K - cs[i] - ct[i]) * (LL)(K - cs[j] - ct[j]);

if(t > a) win += count;

total += count;

}

// 4-2. 同じ数字の場合.

if(i == j){

// 手札のパターンとしてありうるか.

if(cs[i] + ct[i] + 1 >= K) continue;

// 高橋くんの得点.

int t = score(cs, i, sFix);

// 青木くんの得点.

int a = score(ct, j, tFix);

// 評価.

LL count = (LL)(K - cs[i] - ct[i]) * (LL)(K - cs[i] - ct[i] - 1);

if(t > a) win += count;

total += count;

}

// 5. 出力.

printf("%.16lf\n", (double)win / (double)total);

return 0;

}

[入力例]
2
1144#
2233#

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

[入力例]
2
9988#
1122#

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
1.0000000000000000

[入力例]
6
1122#
2228#

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
0.0019323671497585

[入力例]
100000
3226#
3597#

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
0.6296297942426156

[入力例]
3
1234#
2345#

[出力例]
0.2076023391812865

[入力例]
5
3141#
5926#

[出力例]
0.3048048048048048

[入力例]
98765
6789#
8765#

[出力例]
0.6543216265631461

[入力例]

1144#

2233#

[出力例]

0.4444444444444444

※AtCoderテストケースより

[入力例]

9988#

1122#

[出力例]

1.0

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

1.0000000000000000

[入力例]

1122#

2228#

[出力例]

0.001932367149758454

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

0.0019323671497585

[入力例]

100000

3226#

3597#

[出力例]

0.6296297942426154

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

0.6296297942426156

[入力例]

1234#

2345#

[出力例]

0.2076023391812865

[入力例]

3141#

5926#

[出力例]

0.3048048048048048

[入力例]

98765

6789#

8765#

[出力例]

0.6543216265631461

■参照サイト
キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

C++の練習を兼ねて, AtCoder Beginner Contest 193 の 問題C (Unexpressed) ～ 問題D (Poker) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 193 の問題C (Unexpressed) ～問題D (Poker) を解いてみた.

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