解説をするにあたり、数列 \(a\) の要素全てを \(x\) 倍する操作を \(a\cdot x\) と、\(2\) 数列 \(a\), \(b\) を連結する操作を \(a+b\) と表すことにします。

\(N=x\) の場合に問題文中の条件を満たす数列を返す関数を \(f(x)\) と定義します。このような \(f(x)\) は以下のように再帰的に構築することができます。

\[ f(x)=\begin{cases} \emptyset\ (x=0)\\ f(\frac{x}{3})\cdot 3\ (x \neq 0,\ x\equiv 0\bmod\ 3)\\ (f(\frac{x-1}{3})\cdot 3)+(1)\ (x\equiv 1\bmod\ 3)\\ (f(\frac{x+1}{3})\cdot 3)+(-1)\ (x\equiv 2\bmod\ 3) \end{cases} \]

これをこのままコードに移し、\(f(N)\) を求めれば良いです。計算量は \(O(\log^2N)\) です。

解答例 (Python)

N = int(input())
def f(x):
    if x == 0:
        return []
    ret = []
    if x%3 == 0:
        ret = [i*3 for i in f(x//3)]
    if x%3 == 1:
        ret = [i*3 for i in f((x-1)//3)]
        ret.append(1)
    elif x%3 == 2:
        ret = [i*3 for i in f((x+1)//3)]
        ret.append(-1)
    return ret
ans = f(N)
print(len(ans))
print(' '.join(map(str,ans)))

なお、非再帰で書くとより簡潔です。この実装の計算量は \(O(\log N)\) です。

解答例 (C++)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ll N; cin >> N;
    ll now = 1;
    vector<ll> ans;
    while(N){
        if(N%3 == 1){
            ans.push_back(now);
            N--;
        }
        else if(N%3 == 2){
            ans.push_back(-now);
            N++;
        }
        now *= 3;
        N /= 3;
    }
    cout << ans.size() << endl;
    for(auto p:ans) cout << p << " ";
    cout << endl;
}

これは余談ですが、答えとなる数列 \(A\) は並び替えを除き一意に定まります。詳しくは「平衡三進法」と検索してみてください。