Yukicoder039 桁の数字を入れ替え

問題概要

Nが与えられる。Nの2つの桁を選択し、一回だけ交換することができる。入れ替えないという選択も可能なとき、最終的に最も数を大きくしたときの値は何か。

$10^2\leqq N\lt 10^{10}$

yukicoder039

解法

string to longlong + swap で$O((logN)^2)$
後ろから$a[i]:= [i+1,N)$にある最大値 として、 前から順に$n[i]<a[i]$となった時点で交換すれば $O(logN)$

計算量:$O(logN)$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    #define SZ(a) int((a).size())
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    #define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
    
    LL ans = 0LL;
    
    LL f(string& s) { // O(logN)
        LL ret = stoll(s);
        vector<PLL> a(SZ(s), PII(0, 0));
        PII Max = PII(0, 0);
        FORR(i, SZ(s) - 1, 0 - 1) {
            a[i] = Max;
            Max = max(Max, PII(s[i] - '0', i));
        }
        FOR(i, 0, SZ(s)) {
            if (s[i] - '0' < a[i].first) {
                swap(s[i], s[a[i].second]);
                return stoll(s);
            }
        }
        return ret;
    }
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        string s;
        cin >> s;
        ans = stoll(s);
        FOR(i, 0, SZ(s)) { // O(logN^2)
            FOR(j, i + 1, SZ(s)) {
                swap(s[i], s[j]);
                ans = max(ans, stoll(s));
                swap(s[i], s[j]);
    
            }
        }
        assert(ans == f(s));
        cout << ans << "\n";
    
        return 0;
    }