問題

atcoder.jp

考えたこと

-2を底にするので、-2の倍数を計算してみて引いたりする？とか考えてた。実際に作ってみたらうまくいくケースとうまく行かないケースが有って、コーナーケースが面倒な解法になっていたのかな？

解答

-2で順番に割ってそのあまりを随時出していくと良いらしい。確かに、１０進数の桁の数って10で１回、２回、３回……と割ったときのあまりになってる。負数で割ったときのあまりを理解しないといけない。

下の桁（言い方あってる？）から求まっていくので反転するのどうしようかな？と迷ってdequeにするというアクロバットしたけど普通にstringをreverseすればいいだけだった。

ソースを開く

#include <bits/stdc++.h>

using namespace std;

#define rep(i,n)      for(long long(i)=0;(i)<(n);(i)++)

int main(){

    long long n;
    cin >> n;

    if(n == 0){
        cout << n << endl;
        return 0;
    }

    deque<long> s;

    while(n){
        long buf;
        buf = n % 2;
        if(buf < 0){
            buf += 2;
            buf %= 2;
        }
        
        s.push_front( buf ? 1 : 0 );
        n = (n - buf) / -2;
    }

    while(s.size() > 0){
        cout << s.front();
        s.pop_front();
    }

    cout << endl;
    return 0;
}

学んだこと

・基数を変えた場合の表記の求め方は、基数で割りつつあまりを書いていく。・stringはreverseでひっくり返せる。（そうじゃなくてもstr = (char)(0+ cur ) str)とかできたよね‥。）・markdownでソースとかを閉じて隠す方法。

qiita.com

感想

割とスムーズに（間違っている）解法が思いついたから時間とかしちゃった。早めに解説ACした方が良かったかもしれない。時間的な意味で。

mutax no blog

ABC105 C - Base -2 Number

問題

考えたこと

解答

学んだこと

感想