Kaprekar Number [SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192) C]

https://atcoder.jp/contests/abc192/tasks/abc192_c

解説

https://atcoder.jp/contests/abc192/submissions/20344221

なかなか複雑な問題に見えるが、問題文に書かれていることをシミュレートすれば通る。
この辺のどこから深く考えるかというのはスピードを上げるには重要なことであるが、
過去に見覚えが薄いものは特に、愚直解から考え始めるのがいいだろう。

関数fの実装はC++だと比較的簡単にかける。
to_stringで数を文字列に変換して、ソートしてからstoi関数に書けるとg1,g2が得られるので、あとは引いて答えるだけ。
leading-zeroもstoiはいい感じにしてくれる。
計算量としては、桁数は多くても10桁くらいなので、定数ぐらいに考えておく。
あとは、K回これを実行するので、計算量的にも間に合う。

int N, K;
//---------------------------------------------------------------------------------------------------
int f(int x) {
    string s = to_string(x);
    sort(all(s));

    int g2 = stoi(s);

    sort(all(s), greater<char>());

    int g1 = stoi(s);

    return g1 - g2;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    int a = N;
    rep(i, 0, K) a = f(a);
    cout << a << endl;
}