さくBは折り紙を折っている

saku B is folding origami.

10進数から-2進数(マイナス2進数)への変換

さっくです。 友人に誘われてAtCoderの過去問を解いています。

結構悩んだ問題があったので紹介したいと思います。

-2進数を2進数と同じように定義します。

すなわち、あるn桁の-2進数SS_{n-1} ... S_2 S_1 S_0で表されるとき Sを10進数に直すと


  S_{n-1}\times(-2)^{n-1}+...+S_2\times(-2)^2+S_1\times(-2)^1+S_0\times(-2)^0

となります。ここで、Sの各桁は0か1です。

具体的な例を上げてみましょう。 例えば-2進数11001は


[11001]_{-2}=(-2)^4+(-2)^3+(-2)^0=16+(-8)+1=9

です。

さてここからが問題で、 与えられた10進数の整数Nを -2進数に変換する方法を考えてください という内容でした。

以下、僕が解説を見てやんわり理解できた部分について説明しますので ネタバレが嫌な方はそっ閉じしてください

13(10進数)を例にとって考えてみましょう。 まず、13を2で割ったあまりは1です。13 \equiv 1 \pmod{2} ですから、ここでS_0=1としないといけません。 なぜなら、


\begin{eqnarray*}
  (-2)^1 & = & -2 \\
  (-2)^2 & = & 4\\
(-2)^3&=&-8\\
(-2)^4&=&16\\
(-2)^5&=&32
\end{eqnarray*}

と、S_1以降どれを1にしても2の倍数しか加算されません。

さて、S_0の時点で1がわかったので、 S_1以降で残りの12 (=13-1)を作らなければなりません。

では次に、S_1について考えてみましょう。 12を4で割ったあまりは0です。12 \equiv 0 \pmod{4} ですから、ここでS_1=0です。 なぜなら、以後S_2,S_3, ...はどれを1にしても4の倍数が加算され、S_1を1とすると4の倍数ではないものが加算されるからです。 S_1=1としてしまうと、S_2,S_3, ...をどう作っても4の倍数にはなり得ません。

さて、S_1=0が決まったので、S_2以降で残りの12を作らなければなりません。

S_2について考えてみましょう。 12を8で割ったあまりは4です。12 \equiv 4 \pmod{8} ですから、ここでS_2=1です。 なぜなら、以後S_3,S_4, ...はどれを1にしても8の倍数が加算されるからです。

S_2=1が決まったので[tex:(-2)2=4]は使われることがわかりました。 残りの8(=12-4)をS_3以降で作らなければなりません。

S_3について考えてみましょう。 8を16で割ったあまりは8です。8 \equiv 8 \pmod{16} ですから、ここでS_3=1です。 なぜなら、以後S_3,S_4, ...はどれを1にしても16の倍数が加算されるからです。

S_3=1が決まったので、-8は使われることになります。 残りの16(=8-(-8))をS_4以降で作らなければなりません。

S_4について考えてみましょう。 16を32で割ったあまりは16です。16 \equiv 16 \pmod{32} ですから、ここでS_4=1です。 なぜなら、以後S_4,S_5, ...はどれを1にしても32の倍数が加算されるからです。

S_4=1が決まったので、16は使われることになります。 これで、残りがなくなりました。 計算終了です。


13 = [11101]_{-2}=(-2)^4+(-2)^3+(-2)^2+(-2)^1=16+(-8)+4+1=13

という結果が得られました。

もっとスマートなアルゴリズムもあるかと思いますが、 僕がやんわりと理解できた部分でできたのがこれでした。

実際、他の方のソースを見たらもっと単純なやり方があって感心しました。