読者です 読者をやめる 読者になる 読者になる

yukicoder ★★ No.39 桁の数字を入れ替え

yukicoder 競プロ

問題

No.39 桁の数字を入れ替え - yukicoder

考察

1回しか入れ替えられないので、実際に二重ループを回して入れ替え、大小を比較すれば解けます。
桁は9桁以下なので、ごく僅かなループ数で済みます。

簡単なコード

int main() {
    string N;
    cin >> N;

    string ans = N;

    rep(i, N.size()) {
        REP(j, i+1, N.size()) {
            swap(N[i], N[j]);
            chmax(ans, N);
            swap(N[i], N[j]);
        }
    }

    cout << ans << endl;
    
    return 0;
}

せっかく計算量にゆとりがあるので、とても無駄のある処理も書いてみました。
各桁の並び順を全通り試し( O(D!))、元の数字との違いが2つであるか / 元の数値より大きくなるか / いままでで最大か( O(D))を算出しています。
このコードの存在意義は特に無いです。

無駄な処理のあるコード

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

    int ans = N;

    vi digit;
    while(N > 0) {
        digit.push_back(N % 10);
        N /= 10;
    }
    reverse(all(digit));

    vi orig_digit(digit.size());
    rep(i, digit.size())
        orig_digit[i] = digit[i];

    sort(all(digit));

    do {
        int diff = 0;
        rep(i, digit.size()) {
            if(orig_digit[i] != digit[i])
                diff++;
        }
        if(diff != 2)
            continue;

        bool larger = true;
        rep(i, digit.size()) {
            if(digit[i] > orig_digit[i])
                break;
            if(orig_digit[i] > digit[i]) {
                larger = false;
                break;
            }
        }

        int num = 0;
        rep(i, digit.size()) {
            num *= 10;
            num += digit[i];
        }

        if(larger)
            chmax(ans, num);
    } while(next_permutation(all(digit)));

    cout << ans << endl;
    
    return 0;
}