けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

難しいという噂を聞いてやってみたのん。な、なるほどなんな...

問題へのリンク

問題概要 (ABC 105 C)

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

 S_{0}×(−2)^{0} + S_{1}×(−2)^{1} + \dots + S_{k}×(−2)^{k} = N

が成り立つような整数  k と 0-1 整数  S_{0}, S_{1}, \dots, S_{k} を求めよ。

制約

  •  -10^{9} \le N \le 10^{9}

考えたこと

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

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

 N = (-2)q + r

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

  •  N が偶数なら  r = 0
  •  N が奇数なら  r = 1

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

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

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

以上で、 N を -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;
}