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

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

AOJ 0306 対称３進数

AOJ PCK 平衡三進法 数学(整数問題) N進法 復元

与えられた整数を平衡三進法展開してくださいという問題！

問題へのリンク

問題概要

正の整数 w が与えられる。たとえば w = 25 のとき

  • w = 1 - 3 + 27

というように、 3^{0}, 3^{1}, 3^{2}, \dots からいくつか選んで足し引きして表すことができる。これを平衡三進法展開と呼ぶ。

w を平衡三進法展開せよ。出力フォーマットは、たとえば上記の場合は "+0-+" のように出力せよ。

考えたこと

平衡三進法展開は以下のような感じ。任意の整数 n (負でもよい) を表すことができて、表す方法は一意である。

1 = 1
2 = -1 + 3
3 = 3
4 = 1 + 3
5 = -1 - 3 + 9
6 = -3 + 9
7 = 1 - 3 + 9
8 = -1 + 9
9 = 9
10 = 1 + 9
11 = -1 + 3 + 9
12 = 3 + 9
13 = 1 + 3 + 9
14 = -1 - 3 - 9 + 27
15 = -3 - 9 + 27
16 = 1 - 3 - 9 + 27
17 = -1 - 9 + 27
18 = -9 + 27
19 = 1 - 9 + 27
20 = -1 + 3 - 9 + 27
21 = 3 - 9 + 27
22 = 1 + 3 - 9 + 27
23 = -1 - 3 + 27
24 = -3 + 27
25 = 1 - 3 + 27
26 = -1 + 27
27 = 27
...

平衡三進法展開の方法

たとえば 25 の場合

  • 25 ÷ 3 = 8 ... 1 なので、答えに 1 を push して、25 から 1 引いて 3 で割る ({1}, 8)
  • 8 ÷ 3 = 2 ... 2 なので、答えに -1 を push して、25 に 1 足して 3 で割る ({-1, 1}, 3}
  • 3 ÷ 3 = 1 なので、答えに 0 を push して、3 を 3 で割る ({0, -1, 1}, 1)
  • 1 ÷ 3 = 0 ... 1 なので、答えに 1 を push して、1 から 1 引いて 3 で割る ({1, 0, -1, 1}, 0)
  • 0 になったので終了

という感じ。通常の三進法展開だったら、あまりが 2 だったら 2 を push して、2 を引いて 3 で割る。これを、-1 を push して、1 を足して 3 で割るように変更するだけ。

github.com

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

vector<int> PowerThree(long long n) {
    vector<int> res;
    while (n > 0) {
        if (n % 3 == 1) res.push_back(1), --n;
        else if (n % 3 == 2) res.push_back(-1), ++n;
        else res.push_back(0);
        n /= 3;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int w; cin >> w;
    auto res = PowerThree(w);
    for (int i = 0; i < res.size(); ++i) {
        if (res[i] == 1) cout << "+";
        else if (res[i] == -1) cout << "-";
        else cout << "0";
    }
    cout << endl;
}