Aoki's Trick [第七回 アルゴリズム実技検定 E]

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

解説

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

この問題は勘がいい人だと3進数を利用したような問題だなと感じるかもしれない。
それが見えてれば比較的見通しのいい問題になったかもしれない。
だが、3進数が分からなくても操作を逆から行えることに気が付けば、問題を同様に解くことができる。

操作を逆から行う

足し算も掛け算も逆操作が行えるので、以下のように操作を逆に見ていくことにしよう。

Nという値に対して30回3で割るという操作を行う。
操作前に1度だけ1で引くということが行えるとしたときに、適切に1で引いて最終的に1にできるか確認する。

これをやっていこう。

3で割る操作を行うときは、切り捨てを行ってしまうと逆計算として成立しないので、3の倍数のときに3で割る必要がある。
よって、操作を行うときに数を3で割った余りで見て、0なら何もせずに3で割って、1なら1を引く操作をして、2なら不正な状態と判定づけることができる。
これを判定しながら割りながら引きながらやっていけばいい。

ただ、1で引く操作は1回しかできないので複数回出てきたら-1と応答すべきだし、最終的に数が1にならなければ何かがおかしいので-1と応答する。
queryは最初が30回目となるので、30から1まで減らしていくようなループでやっていくと、そのまま回数を答えることができる。

ll N;
//---------------------------------------------------------------------------------------------------
int solve() {
    int ans = -1;
    rrep(query, 30, 1) {
        if (N % 3 == 0) N /= 3;
        else if (N % 3 == 1) {
            N /= 3;
            if (ans < 0) ans = query;
            else return -1;
        }
        else { // N % 3 == 2
            return -1;
        }
    }
    
    if (N != 1) return -1;
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    cout << solve() << endl;
}