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

C++の練習を兼ねて, AtCoder Beginner Contest 105 の問題C（C – Base -2 Number）を解いてみた.

① 制限時間内に, 解答できず終了.
② 公開されている解答を見たものの, 理解不能.
③ 結局, 試行錯誤して, ロジックを積み上げたところ, どうやらテストケースは, 全通過した模様(汗).
④ おそらく, もっと簡単なロジックがあると想定されるので, 後日, 他の方の解答を拝見しようと思う.

本家のサイトABC 105 解説をご覧下さい。

■C++版プログラム

// 解き直し.
// ABC 105 解説.
// https://img.atcoder.jp/abc105/editorial.pdf
#include <iostream>
#include <string>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define abs(x) ((x > 0) ? x : (-(x)))

typedef long long LL;

// 整数a の b乗 を返却.
// @param a: べき乗したい整数.
// @param b: 指数.
// @return: 整数a の b乗.
LL power(int a, int b) {
    LL ret = 1;
    FOR(i, 0, b) ret *= a;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    cin >> N;
    
    // 2. 指数の最大値を, 32 と仮定.
    // -9 ÷ 2 = -5 余り 1 のような計算を繰り返す.

    // 2-1. N == 0 の場合は, 0 を出力して, 終了.
    if(N == 0) {
        cout << 0 << endl;
        return 0;
    }

    // 2-2. N != 0 の場合.
    LL nCopy = N;  // 2で割り続けるため, コピーを取得.
    LL nComp = 0;  // N と比較し, 終了条件に使用.
    string b2 = "";
    FOR(i, 0, 32) {
        LL q = abs(nCopy % 2);  // 余り.
        LL r = nCopy / -2;       // 商.
        if(nCopy == (r - 1) * -2 + q) r -= 1;  // nCopy < 0 の場合を想定.
        if(nCopy == (r + 1) * -2 + q) r += 1;  // nCopy > 0 の場合を想定.
        b2.insert(0, to_string(q));
        nCopy = r;    // N に r を 代入して, 繰り返し計算.
        nComp += q * power(-2, i);
        if(N == nComp) break;    // 元の整数と一致したら, 処理を終了.
    }
    
    // 3. 出力 ～ 後処理.
    cout << b2 << endl;
    return 0;
    
}

// 解き直し.

// ABC 105 解説.

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

#include <iostream>

#include <string>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)

#define abs(x) ((x > 0) ? x : (-(x)))

typedef long long LL;

// 整数a の b乗を返却.

// @param a: べき乗したい整数.

// @param b: 指数.

// @return: 整数a の b乗.

LL power(int a, int b) {

LL ret = 1;

FOR(i, 0, b) ret *= a;

return ret;

}

int main() {

// 1. 入力情報取得.

LL N;

cin >> N;

// 2. 指数の最大値を, 32 と仮定.

// -9 ÷ 2 = -5 余り 1 のような計算を繰り返す.

// 2-1. N == 0 の場合は, 0 を出力して, 終了.

if(N == 0) {

cout << 0 << endl;

return 0;

}

// 2-2. N != 0 の場合.

LL nCopy = N; // 2で割り続けるため, コピーを取得.

LL nComp = 0; // N と比較し, 終了条件に使用.

string b2 = "";

FOR(i, 0, 32) {

LL q = abs(nCopy % 2); // 余り.

LL r = nCopy / -2; // 商.

if(nCopy == (r - 1) * -2 + q) r -= 1; // nCopy < 0 の場合を想定.

if(nCopy == (r + 1) * -2 + q) r += 1; // nCopy > 0 の場合を想定.

b2.insert(0, to_string(q));

nCopy = r; // N に r を代入して, 繰り返し計算.

nComp += q * power(-2, i);

if(N == nComp) break; // 元の整数と一致したら, 処理を終了.

}

// 3. 出力～後処理.

cout << b2 << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 105

C++の練習を兼ねて, AtCoder Beginner Contest 105 の 問題C（C – Base -2 Number）を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 105 の問題C（C – Base -2 Number）を解いてみた.

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