Power Expression [第七回 アルゴリズム実技検定 G]

https://atcoder.jp/contests/past202107-open/tasks/past202107_g

解説

https://atcoder.jp/contests/past202107-open/submissions/24465845

何から始めるか

このような構築問題は、慣れないうちは何から始めていいか分からないと思う。
とりあえずいくつか方針を立ててみて、実験してみて、それっぽい方針を実装していくしかない。
…という説明も不親切なので、もう少し説明を試みる。

構築問題のテクの1つとして、ある一定のルールで構築していくという方針がある。
このときに定義するルールはなるべく簡単なルールで、実装しやすいものが望ましい。
この「ルール」というのも結構傾向があり、今回もよく見るようなルールで構築をしていく。

ルール

今回は、1, -1, 3, -3, 9, -9, 27, -27, ...といった数が使える。
この候補からどの数を最初に使うかという場面で「毎回、答えに最も近づくものを選択する」というルールで数を選んでいくことにしよう。
例えば、21を作りたい場合、0から21に最も近づくためには、一旦超えてしまうが、27を選択するのが最も良い。

0 -> 27

次に最も近づくのはどれだろう。

9 : 27 -> 36
-9 : 27 -> 18 差分が3
3 : 27 -> 30
-3 : 27 -> 24 差分が3
1 : 27 -> 28
-1 : 27 -> 26

2つ候補がある。どちらを使うべきだろうか？
条件に選択される数が被ってはいけないという条件がある。
答えとの数の差が狭くなっていくにつれて、絶対値が小さい数が重宝されそうなのは想像がつくので、なるべく大きい方を採用することにする。
今回は-9を使う

0 -> 27 -> 18

あとは、+3を使えば21が、差分が最も小さくなって達成。

0 -> 27 -> 18 -> 21

振り返ると、正確にルールを定義すると以下のようになる。

• 毎回、答えに最も近づくものを選択する
• 同着になった場合は絶対値が大きい方を採用する

これで本当に大丈夫？

自分は証明スキルを持ってないので証明してないのですが、強い人は証明してるらしいので、するのがオススメです。
再帰的帰納法とかで証明できるんじゃないかな？
競プロ的には未証明でも、確度が高ければ突っ込む戦略もありかなと思います（俗にいうACをもってQ.E.D.とする証明AC）

実装時は

実装時には0からNを目指すのではなく、Nから足し引きをして0を目指すように実装している。
なので、答えとして採用するときは逆から計算しているので、正負が逆になって答えとして記録している。

あと、ルールの性質上選択される数は絶対値が単調減少していくので、候補をすべて確認するのではなくて、
候補を絶対値が大きい方から見ていって、使うことで答えに近づくなら使うという方針で実装している。
このような方針と実装は構築問題では、ある種の貪欲法としてよく見られるので、覚えておくといい。

なお…

この問題は平衡3進法として有名ではあり、類題もいくつかあるので、練習してみよう。
競技プログラミングにおける数学的問題まとめ - はまやんはまやんはまやん

ll N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    vector<ll> cand;
    ll x = 1;
    while (x <= 2e15) {
        cand.push_back(x);
        x *= 3;
    }
    reverse(all(cand));

    vector<ll> ans;
    fore(a, cand) {
        if (abs(N + a) < abs(N)) {
            N += a;
            ans.push_back(-a);
        } else if (abs(N - a) < abs(N)) {
            N -= a;
            ans.push_back(a);
        }
    }

    int M = ans.size();
    printf("%d\n", M);
    rep(i, 0, M) {
        if(i) printf(" ");
        printf("%lld", ans[i]);
    }
    printf("\n");
}