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

C++の練習を兼ねて, AtCoder Grand Contest 015 の問題D (A or…or B Problem) を解いてみた.

■感想.
1. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 実装して何とかAC版となった.
2. 但し, 特殊なテストケース(12.txt, 24.txtなど)の考慮も必要で, 実装に非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトAGC 015 解説をご覧下さい.

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

// コメント, ロジック見直して, 再提出.
// 解き直し.
// https://img.atcoder.jp/agc015/editorial.pdf
// 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 MAX = 61;

int main(){
    
    // 1. 入力情報.
    LL A, B;
    scanf("%lld %lld", &A, &B);
    if(A > B) swap(A, B);
    
    // 2. A = B の 場合.
    if(A == B){
        puts("1");
        return 0;
    }
    
    // 3. 2 の 冪乗(61乗未満).
    vector<LL> vPow2(MAX);
    vPow2[0] = 1LL;
    repx(i, 1, MAX) vPow2[i] = vPow2[i - 1] << 1;
    // rep(i, MAX) printf("%lld\n", vPow2[i]);
    
    // 4. 二進数変換(61桁).
    string binA, binB;
    rep(i, MAX){
        if(1 & (A >> i)) binA = "1" + binA;
        else             binA = "0" + binA;
        if(1 & (B >> i)) binB = "1" + binB;
        else             binB = "0" + binB;
    }
    // printf("A=%s\n", binA.c_str());
    // printf("B=%s\n", binB.c_str());
    
    // 5. 操作 BITWISE OR を取って出来る整数をカウント.
    // 5-1. 二進数 A, B が, 最初に異なる桁.
    int r = -1;
    rep(i, MAX){
        if(binA[i] != binB[i]){
            r = MAX - i;
            break;
        }
    }
    assert(r != -1);
    // printf("r=%d\n", r);
    
    // 5-2. r桁より大きい部分(A, B の 共通部分)を計算し, A を 更新.
    LL extra = 0;
    rep(i, MAX - r) if(binA[i] == '1') extra += vPow2[MAX - 1 - i];
    A -= extra;
    
    // 6. 各パターンを集計.
    // 6-1. A ～ 2 の (r - 1)乗未満 の 整数 を カウント(パターン①).
    LL ans = vPow2[r - 1] - A;
    
    // 6-2. 最上位が 1 の 整数のみ使う場合(パターン②).
    // 15.txt, 16.txt, 18.txt, 53.txt で WA版となった(maxP2 = -1 から maxP2 = 0 へ 変更).
    // -> B が 1000 の ような形で, k = -1 となったパターンについて考慮が必要とのこと.
    // -> 但し, 修正後に, 12.txt, 24.txt で, WA版 だったため, そもそも, k = -1 から k = 0 に ロジック変更.
    int k = 0;
    repx(i, MAX - r + 1, MAX){
        if(binB[i] == '1'){
            k = MAX - i;
            break;
        }
    }
    // printf("k=%d\n", k);
    LL minP2 = vPow2[r - 1], maxP2 = vPow2[r - 1] + vPow2[k];
    
    // 6-3. 最上位が 0, 1 の 整数を使う場合(パターン③).
    LL minP3 = vPow2[r - 1] + A;
    LL maxP3 = vPow2[r];
    
    // 6-4. パターン②, ③ を 統合.
    if(maxP2 >= minP3) ans += maxP3 - minP2;
    else               ans += maxP2 - minP2, ans += maxP3 - minP3;
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// コメント, ロジック見直して, 再提出.

// 解き直し.

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

// 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 MAX = 61;

int main(){

// 1. 入力情報.

LL A, B;

scanf("%lld %lld", &A, &B);

if(A > B) swap(A, B);

// 2. A = B の場合.

if(A == B){

puts("1");

return 0;

}

// 3. 2 の冪乗(61乗未満).

vector<LL> vPow2(MAX);

vPow2[0] = 1LL;

repx(i, 1, MAX) vPow2[i] = vPow2[i - 1] << 1;

// rep(i, MAX) printf("%lld\n", vPow2[i]);

// 4. 二進数変換(61桁).

string binA, binB;

rep(i, MAX){

if(1 & (A >> i)) binA = "1" + binA;

else binA = "0" + binA;

if(1 & (B >> i)) binB = "1" + binB;

else binB = "0" + binB;

}

// printf("A=%s\n", binA.c_str());

// printf("B=%s\n", binB.c_str());

// 5. 操作 BITWISE OR を取って出来る整数をカウント.

// 5-1. 二進数 A, B が, 最初に異なる桁.

int r = -1;

rep(i, MAX){

if(binA[i] != binB[i]){

r = MAX - i;

break;

}

assert(r != -1);

// printf("r=%d\n", r);

// 5-2. r桁より大きい部分(A, B の共通部分)を計算し, A を更新.

LL extra = 0;

rep(i, MAX - r) if(binA[i] == '1') extra += vPow2[MAX - 1 - i];

A -= extra;

// 6. 各パターンを集計.

// 6-1. A ～ 2 の (r - 1)乗未満の整数をカウント(パターン①).

LL ans = vPow2[r - 1] - A;

// 6-2. 最上位が 1 の整数のみ使う場合(パターン②).

// 15.txt, 16.txt, 18.txt, 53.txt で WA版となった(maxP2 = -1 から maxP2 = 0 へ変更).

// -> B が 1000 のような形で, k = -1 となったパターンについて考慮が必要とのこと.

// -> 但し, 修正後に, 12.txt, 24.txt で, WA版だったため, そもそも, k = -1 から k = 0 にロジック変更.

int k = 0;

repx(i, MAX - r + 1, MAX){

if(binB[i] == '1'){

k = MAX - i;

break;

}

// printf("k=%d\n", k);

LL minP2 = vPow2[r - 1], maxP2 = vPow2[r - 1] + vPow2[k];

// 6-3. 最上位が 0, 1 の整数を使う場合(パターン③).

LL minP3 = vPow2[r - 1] + A;

LL maxP3 = vPow2[r];

// 6-4. パターン②, ③ を統合.

if(maxP2 >= minP3) ans += maxP3 - minP2;

else ans += maxP2 - minP2, ans += maxP3 - minP3;

// 7. 出力.

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

return 0;

}

[入力例]
7
9

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

[入力例]
65
98

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

[入力例]
271828182845904523
314159265358979323

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

[入力例]
141421356237309504
173205080756887729

[出力例]
41416460696056704

[入力例]
223606797749978969
264575131106459059

[出力例]
64623578401732775

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

271828182845904523

314159265358979323

[出力例]

68833183630578410

※AtCoderテストケースより

[入力例]

141421356237309504

173205080756887729

[出力例]

41416460696056704

[入力例]

223606797749978969

264575131106459059

[出力例]

64623578401732775

■参照サイト
AtCoder Grand Contest 015

C++の練習を兼ねて, AtCoder Grand Contest 015 の 問題D (A or…or B Problem) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 015 の問題D (A or…or B Problem) を解いてみた.

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