AtCoder ABC 105 C - Base -2 Number (水色, 300 点)

なるほど...

• 問題へのリンク

問題概要

整数 が与えられる。 を "-2 進法" 展開せよ。すなわち

が成り立つような整数 と 0-1 整数 を求めよ。

制約

• 

考えたこと

2 進法展開や 10 進法展開なら ここ に書いた通りなん。-2 進法になってもそう大差ないん。

基本的には を -2 で割って、割ったあまりを答えに追加していくような感じです。-2 で割るとはどういうことかもう少し掘り下げてみます:

としたときに、 が 0 か 1 になるように を調節するということになります。これ実は、

• が偶数なら
• が奇数なら

とすればよいという感じなので、実は を単に 2 で割るのと変わらないです。ただし、ここに書いた通り、 が負の数のとき

• % 2 の値は 0 か -1 になってしまうので、-1 になるならそれに 2 を足す

という風にする必要があります。

以上で、 を -2 で割っていくというのがどういうことなのかがわかったので、いつもの 10 進法展開と同じノリでコードにして行くと AC がもらえました。

コード

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  int N; cin >> N;
  string str = "";
  while (N != 0) {
    /* N を 2 で割ったあまりを求める */
    int r = N % 2;
    if (r < 0) r += 2; // N がマイナスだと r がマイナスになったりするので 2 を足す

    /* N から余りを取り除いて -2 で割る */
    N = (N - r) / (-2);

    /* 答えに追加 */
    str += (char)('0' + r);
  }
  /* 向きが逆なので反転 */
  reverse(str.begin(), str.end());
  if (str == "") str = "0"; // N = 0 のときは空文字列になってしまうので例外処理
  cout << str << endl;
}