はじめに

競技プログラミング、AtCoder Beginner Contest 105
C - Base -2 Number
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

整数Nが与えられるので、Nの−2進数表現を求めてください。

ここで、Sが Nの −2進数表現であるとは、以下を全て満たすことです。
・Sは'0'および'1'のみからなる文字列である
・S='0'でなければSの先頭の文字は'1'である
・S=SkSk−1...S0とすると、S0×(−2)^0+S1×(−2)^1+...+Sk×(−2)^k=N が成り立つ

なお、任意の整数 Mに対して Mの−2進数表現が一意に定まることが証明できます。

制約

・入力はすべて整数である
・−10^9≤N≤10^9

入力

入力は以下の形式で標準入力から与えられる。

N

出力

Nの−2進数表現を出力せよ。

解き方

以下を参考にしています。
AtCoder ABC 105 C - Base -2 Number (300 点) - けんちょんの競プロ精進記録
 ARC105-C：Base -2 Number - 数学/競プロメモ
 ABC105 参加記録 - ARMERIA
ARC105-C：Base -2 Number - 数学/競プロメモ

まず、
2進数を求めるときの方法を考えてみます。
以下の記事の考え方を用いています。
betrue12.hateblo.jp
2進数の各桁は以下のように決まります。

2⁶	2⁵	2⁴	2³	2²	2¹	2⁰
2⁷で割った余りの有無	2⁶で割った余りの有無	2⁵で割った余りの有無	2⁴で割った余りの有無	2³で割った余りの有無	2²で割った余りの有無	2¹で割った余りの有無

試しに10進数の9を2進数にしてみます。

割られる数	割る数	余りの有無
9	2¹	1
8	2²	0
8	2³	0
8	2⁴	1

考え方は、余りがもしあれば
桁のbitを立てて
その数ぶんはもう「表示している」ということになるので
9から引いています。

そのため、
動きは以下のようになっています。

9%2^1=1
余りがあるので2^0の桁のbitを立てる
2^0の桁を立てたので9-(2^0)=8になる

8%2^2=0
余りがないので何も起こらない

8%2^3=0
余りがないので何も起こらない

8%2^4=8
余りがあるので2^3の桁のbitを立てる
2^3の桁を立てたので8-(2^3)=0になる

この2進数の考え方は-2進数でも同じように使うことができます。

(-2)⁶	(-2)⁵	(-2)⁴	(-2)³	(-2)^-2	(-2)¹	(-2)⁰
(-2)⁷で割った余りの有無	(-2)⁶で割った余りの有無	(-2)⁵で割った余りの有無	(-2)⁴で割った余りの有無	(-2)³で割った余りの有無	(-2)^-2で割った余りの有無	(-2)¹で割った余りの有無

先ほどの二進数と同じように
入力例1を-2進数に変換してみると以下のようになります。

入力例1

-9

割られる数	割る数	余りの有無
-9	(-2)¹	1
-10	(-2)²	1
-8	(-2)³	0
-8	(-2)⁴	1

動きは以下のようになっています。

(-9)%(-2)^1=1
余りがあるので(-2)^0の桁のbitを立てる
(-2)^0の桁を立てたので(-9)-((-2)^0)=-10になる

(-10)%(-2)^2=2
余りがあるので(-2)^1の桁のbitを立てる
(-2)^1の桁を立てたので(-10)-((-2)^1)=-8になる

(-8)%(-2)^3=0
余りがないので何も起こらない

(-8)%(-2)^4=8
余りがあるので(-2)^3の桁のbitを立てる
(-2)^3の桁を立てたので(-8)-((-2)^3)=0になる

この動きをそのまま実装します。

全体のコード

using System;
using System.Collections.Generic;
using System.Linq;

class Cmondai
{
    static void Main()
    {
        var N = Int64.Parse(Console.ReadLine());
        //割る数にかけるための-2
        const long constant = -2;
        //割る数
        var num = 1L;
        //各桁を格納するためのStackを用意
        var ans = new Stack<char>();
        //Nが0の場合は(-2)進数も0になる
        if (N == 0) ans.Push('0');
        //Nの(-2)進数を求める
        //Nが0になるまで、割って引くことを繰り返す
        while (N != 0)
        {
            //余りがない
            if (N % (num * constant) == 0)
            {
                //1が立たないので0
                //Nに変化なし
                ans.Push('0');
            }
            //余りがある
            else
            {
                //bitに1が立つ
                ans.Push('1');
                //1が立つのでその分Nから数を引く
                N -= num;
            }
            //次の割る数を作成
            num *= (-2);
        }
        long count = ans.Count();
        //保存しておいた各桁を出力
        for (long i = 0; i < count; ++i) Console.Write(ans.Pop());
        Console.WriteLine();
    }
}