Codeforces Round #491 (Div.2) F. Concise and clear

問題文

http://codeforces.com/contest/991/problem/F

解法

冪乗の形を使っていかに短くできるか，という問題．
まず，n * m （n, m はただの自然数）のような表現は完全に不利．
例えば 99 * 99 を考えてみるとわかりやすいが，そのまま出力したほうが短いからである．
すると，足し算以外で考えるべきは

• p ^ q
• a * p ^ q
• p ^ q * x ^ y

しかない．
p ^ q として使いうる候補は数えてみるとわかるが多くないので，全部作ってしまう．
p ^ q * x ^ y についてだが，それぞれの p ^ q, x ^ y の長さはたかだか4であるとして良い（つまり3文字か4文字の p ^ qだけ考えればよい）．
6文字以上はオーバーするから当然いらない．問題は5文字の p ^ q をなぜ考慮しなくてよいかである．
与えられる入力がたかだか10桁であることに注目する．n = 10^10 の場合は 10 ^ 10 が当然最適なので関係ない．つまり9桁の場合のみ注目すればいい．
すると，p ^ q で5文字使ってしまうと "^" を考慮して x ^ y で使えるのはあと3文字分しかない．
しかし3文字使っていいなら，トータル9文字になるので入力をそのまま出力すればいい．したがって5文字は考えなくて良いことがわかる．

最後に，a * (上で求めた冪の形）+ b を全部ためして一番短いやつを選ぶ．

ソースコード

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

using ll = long long;

int main() {
    ll n; cin >> n;

    const ll ub = n;
    map<ll, string> pw, pw_len3or4;
    for(ll i = 2; i * i <= ub; ++i) {
        ll p = i;
        for(int j = 2; p * i <= ub; ++j) {
            p *= i;
            string s = to_string(i) + "^" + to_string(j);
            if(pw.count(p) == 0 || pw[p].size() > s.size()) {
                pw[p] = s;
            }
        }
    }
    for(auto& p : pw) {
        if(p.second.size() == 3 || p.second.size() == 4u) {
            pw_len3or4.insert(p);
        }
    }
    for(auto& p : pw_len3or4) {
        for(auto& q : pw_len3or4) {
            if(p.first > ub / q.first) continue;
            string s = p.second + "*" + q.second;
            ll val = p.first * q.first;
            if(val <= ub && (pw.count(val) == 0 || pw[val].size() > s.size())) {
                pw[val] = s;
            }
        }
    }

    string ans = to_string(n);
    for(auto& p : pw) {
        ll d = n / p.first;
        if(d == 0) break;
        string s;
        if(d > 1) s += to_string(d) + "*";
        s += p.second;
        ll r = n % p.first;
        if(r > 0) {
            s += "+";
            if(pw.count(r) && to_string(r).size() > pw[r].size()) {
                s += pw[r];
            } else {
                s += to_string(r);
            }
        }
        if(ans.size() > s.size()) {
            ans = s;
        }
    }

    cout << ans << endl;
}

感想

本番ではやばいと思ってほとんど考えず諦めて hack に移行してしまったが，もったいなかった．