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

C++の練習を兼ねて, AtCoder Grand Contest 029 の問題A (Irreversible operation) ～問題B (Powers of two) を解いてみた.

■感想.
1. 問題B は, 解答方針が見えなかったので, 解説を参考に実装して, AC版まで到達出来たので良かったと思う.
※ multisetを使って実装したものの, TLE版となったので, mapによる実装に差し替えた.
2. 問題A, B ともに, 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Grand Contest 029 解説をご覧下さい.

■C++版プログラム(問題A／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--)
LL oSum[202020];

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    string S(c);
    int N = S.size();
    
    // 2. 操作回数をカウント.
    LL ans = 0;
    rep(i, N){
        oSum[i + 1] += oSum[i];
        if(S[N - 1 - i] == 'W') oSum[i + 1]++;
        else                    ans += oSum[i + 1];
    }
    
    // 3. 出力.
    printf("%lld\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--)

LL oSum[202020];

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

string S(c);

int N = S.size();

// 2. 操作回数をカウント.

LL ans = 0;

rep(i, N){

oSum[i + 1] += oSum[i];

if(S[N - 1 - i] == 'W') oSum[i + 1]++;

else ans += oSum[i + 1];

}

// 3. 出力.

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

return 0;

}

[入力例]
BBW

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

[入力例]
BWBWBW

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

[入力例]
BBBBBBBBBB

[出力例]
0

[入力例]
BBBBWBWBWBBWWBWWWBBBBWWBBBBWWBWBB

[出力例]
136

[入力例]
BWWWWBWWWBWWWBWWBWWWWWBBBWWWBBBWWBBWWWWWBBBWWBBWWWBBBBBBWWBBWBBBBWWBWBBBWBWWBBBWBWWWBBBBWBBBWWWWBWBWBWBBWBBWBBBWWBWBWWWWBWBWBWBWBWBWBWBWBBWBBBBWWBWBBBBBWBWWBBWWWWWWBBWBWBWWBBBWWBWWBWWBWBWBWBWWWBBWWBWWWBWBBBWWWWWBWBBWWWBBBBWWBWWWBBWBBWBBBBWBWBBWWWWWWWWWWBWWBWBWBWWWBBWWBWWWWBBWWBWWBWBWWBBBWWWBBBWBBBWB

[出力例]
11403

[入力例]

BBW

[出力例]

※AtCoderのテストケースより

[入力例]

BWBWBW

[出力例]

※AtCoderのテストケースより

[入力例]

BBBBBBBBBB

[出力例]

[入力例]

BBBBWBWBWBBWWBWWWBBBBWWBBBBWWBWBB

[出力例]

136

[入力例]

BWWWWBWWWBWWWBWWBWWWWWBBBWWWBBBWWBBWWWWWBBBWWBBWWWBBBBBBWWBBWBBBBWWBWBBBWBWWBBBWBWWWBBBBWBBBWWWWBWBWBWBBWBBWBBBWWBWBWWWWBWBWBWBWBWBWBWBWBBWBBBBWWBWBBBBBWBWWBBWWWWWWBBWBWBWWBBBWWBWWBWWBWBWBWBWWWBBWWBWWWBWBBBWWWWWBWBBWWWBBBBWWBWWWBBWBBWBBBBWBWBBWWWWWWWWWWBWWBWBWBWWWBBWWBWWWWBBWWBWWBWBWWBBBWWWBBBWBBBWB

[出力例]

11403

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

// TLE版.
// 10000個 の 1 を用意した場合, 262[ms] かかった.
// C++(GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/agc029/editorial.pdf
// #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;
//     multiset<LL> mst; // in15.txt などで, TLE版になってしまう.
//     scanf("%d", &N);
//     rep(i, N){
//         scanf("%lld", &a[i]);
//         mst.insert(a[i]); // ペアとなるボール探索用.
//     }
//     
//     // 2. sort.
//     sort(a, a + N);
//     
//     // 3. ペアをカウント.
//     int ans = 0;
//     repr(i, N - 1, 0){
//         // 3-1. 対象のボールを取得.
//         LL b1 = a[i];
//         
//         // 3-2. すでに, ペアとなるボールとして使用不可の場合は, 次へ.
//         if(!mst.count(b1)) continue;
//         
//         // 3-3. ペアとなるボールとして消費.
//         auto itr1 = mst.find(b1); // 1個だけ削除したいため.
//         mst.erase(itr1);
//         
//         // 3-4. a[i] < (2 の 冪乗) <= 2 * a[i] となる 2 の 冪乗 を 探索.
//         LL p2 = 1;
//         while(p2 <= 2 * b1) p2 <<= 1;
//         if(p2 > 2 * b1) p2 >>= 1;
//         
//         // 3-5. ペアとなるボールを検索.
//         LL b2 = p2 - b1;
//         
//         // 3-6. ペアとなるボールがあれば, カウント.
//         if(mst.count(b2)){
//             ans++;
//             auto itr2 = mst.find(b2); // 1個だけ削除したいため.
//             mst.erase(itr2);
//         }
//     }
//     
//     // 4. 出力.
//     printf("%lld\n", ans);
//     return 0;
//     
// }
// 
// TLE回避版.
// 200000個 の 1 を用意した場合, 34[ms] かかった.
// C++(GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/agc029/editorial.pdf
#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;
    map<LL, int> m;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld", &a[i]);
        m[a[i]]++;
    }
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. ペアをカウント.
    int ans = 0;
    repr(i, N - 1, 0){
        // 3-1. 対象のボールを取得.
        LL b1 = a[i];
        
        // 3-2. すでに, ペアとなるボールとして使用不可の場合は, 次へ.
        if(m[b1] == 0) continue;
        
        // 3-3. ペアとなるボールとして消費.
        m[b1]--;
        
        // 3-4. a[i] < (2 の 冪乗) <= 2 * a[i] となる 2 の 冪乗 を 探索.
        LL p2 = 1;
        while(p2 <= 2 * b1) p2 <<= 1;
        if(p2 > 2 * b1) p2 >>= 1;
        
        // 3-5. ペアとなるボールを検索.
        LL b2 = p2 - b1;
        
        // 3-6. ペアとなるボールがあれば, カウント.
        if(m.count(b2)){
            if(m[b2] > 0){
                ans++;
                m[b2]--;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

// TLE版.

// 10000個の 1 を用意した場合, 262[ms] かかった.

// C++(GCC 9.2.1)

// 解き直し.

// https://img.atcoder.jp/agc029/editorial.pdf

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

// multiset<LL> mst; // in15.txt などで, TLE版になってしまう.

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

// rep(i, N){

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

// mst.insert(a[i]); // ペアとなるボール探索用.

// }

// // 2. sort.

// sort(a, a + N);

// // 3. ペアをカウント.

// int ans = 0;

// repr(i, N - 1, 0){

// // 3-1. 対象のボールを取得.

// LL b1 = a[i];

// // 3-2. すでに, ペアとなるボールとして使用不可の場合は, 次へ.

// if(!mst.count(b1)) continue;

// // 3-3. ペアとなるボールとして消費.

// auto itr1 = mst.find(b1); // 1個だけ削除したいため.

// mst.erase(itr1);

// // 3-4. a[i] < (2 の冪乗) <= 2 * a[i] となる 2 の冪乗を探索.

// LL p2 = 1;

// while(p2 <= 2 * b1) p2 <<= 1;

// if(p2 > 2 * b1) p2 >>= 1;

// // 3-5. ペアとなるボールを検索.

// LL b2 = p2 - b1;

// // 3-6. ペアとなるボールがあれば, カウント.

// if(mst.count(b2)){

// ans++;

// auto itr2 = mst.find(b2); // 1個だけ削除したいため.

// mst.erase(itr2);

// }

// // 4. 出力.

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

// return 0;

// }

// TLE回避版.

// 200000個の 1 を用意した場合, 34[ms] かかった.

// C++(GCC 9.2.1)

// 解き直し.

// https://img.atcoder.jp/agc029/editorial.pdf

#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;

map<LL, int> m;

scanf("%d", &N);

rep(i, N){

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

m[a[i]]++;

}

// 2. sort.

sort(a, a + N);

// 3. ペアをカウント.

int ans = 0;

repr(i, N - 1, 0){

// 3-1. 対象のボールを取得.

LL b1 = a[i];

// 3-2. すでに, ペアとなるボールとして使用不可の場合は, 次へ.

if(m[b1] == 0) continue;

// 3-3. ペアとなるボールとして消費.

m[b1]--;

// 3-4. a[i] < (2 の冪乗) <= 2 * a[i] となる 2 の冪乗を探索.

LL p2 = 1;

while(p2 <= 2 * b1) p2 <<= 1;

if(p2 > 2 * b1) p2 >>= 1;

// 3-5. ペアとなるボールを検索.

LL b2 = p2 - b1;

// 3-6. ペアとなるボールがあれば, カウント.

if(m.count(b2)){

if(m[b2] > 0){

ans++;

m[b2]--;

}

// 4. 出力.

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

return 0;

}

[入力例]
3
1 2 3

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

[入力例]
5
3 11 14 5 13

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

[入力例]
10
10 2 4 3 5 7 6 8 9 1

[出力例]
3
※ 実際, 16 = 10 + 6, 16 = 9 + 7, 4 = 3 + 1 の 3通り.

[入力例]
10
3 5 4 3 3 7 5 8 5 1

[出力例]
4
※ 実際, 8 = 7 + 1, 8 = 5 + 3, 8 = 5 + 3, 8 = 5 + 3 の 4通り.

[入力例]
33
71 91 14 5 78 16 29 24 11 38 48 4 62 33 103 30 93 100 51 34 56 106 93 88 13 22 101 7 80 47 71 82 49

[出力例]
5
※ 実際, 128 = 106 + 22, 128 = 80 + 48, 64 = 51 + 13, 64 = 34 + 30, 16 = 11 + 5 の 5通り.

[入力例]

1 2 3

[出力例]

※AtCoderのテストケースより

[入力例]

3 11 14 5 13

[出力例]

※AtCoderのテストケースより

[入力例]

10 2 4 3 5 7 6 8 9 1

[出力例]

※ 実際, 16 = 10 + 6, 16 = 9 + 7, 4 = 3 + 1 の 3通り.

[入力例]

3 5 4 3 3 7 5 8 5 1

[出力例]

※ 実際, 8 = 7 + 1, 8 = 5 + 3, 8 = 5 + 3, 8 = 5 + 3 の 4通り.

[入力例]

71 91 14 5 78 16 29 24 11 38 48 4 62 33 103 30 93 100 51 34 56 106 93 88 13 22 101 7 80 47 71 82 49

[出力例]

※ 実際, 128 = 106 + 22, 128 = 80 + 48, 64 = 51 + 13, 64 = 34 + 30, 16 = 11 + 5 の 5通り.

■参照サイト
AtCoder Grand Contest 029

C++の練習を兼ねて, AtCoder Grand Contest 029 の 問題A (Irreversible operation) ～ 問題B (Powers of two) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 029 の問題A (Irreversible operation) ～問題B (Powers of two) を解いてみた.

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