SOMPO HD コンテスト(ABC192 C - Kaprekar Number)【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

3完だったSOMPO HD プログラミングコンテスト(ABC192)のC問題解答例を記事にしていきます。
atcoder.jp

AtCoder Beginner Contest192 C - Kaprekar Number

問題文

0 以上の整数 x に対して、g1(x),g2(x),f(x) を次のように定めます。
・g1(x)= x を十進法で表したときの各桁の数字を大きい順に並び替えてできる整数
・g2(x)= x を十進法で表したときの各桁の数字を小さい順に並び替えてできる整数
・f(x)=g1(x)−g2(x)
例えば g1(314)=431, g2(3021)=123, f(271)=721−127=594 です。先頭の余分な 0 は無視されることに注意してください。
整数 N,K が与えられるので、a0=N, ai+1=f(ai) (i≥0) で定まる数列の aK を求めてください。

制約

・0≤N≤10^9
・0≤K≤10^5
・入力は全て整数

解答例

n, k = map(int,input().split())

a = n
for i in range(k):
    g1_a = int(''.join(sorted(str(a), reverse = True)))
    g2_a = int(''.join(sorted(str(a))))
    a = g1_a - g2_a
else:
    print(a)

解説

問題文に記載がある方法で求まるg1(x),g2(x),f(x)があり、ai = f(x-1)となる数列のK番目の値を解答する問題です。

問題文の通りg1(x),g2(x),f(x)を計算していき、akを求めました。

g1(x)はg1_a、g2(x)はg2_aと表記しました。
それぞれ問題文のように各桁の数字をg1_aは大きい順に、g2_aは小さい順に並び変えています。
f(x) = g1(x) - g2(x)なので a = g1_a - g2_aとして数列を更新していきます。

ループを抜けたあとにaを出力すればACでした。

ACできたC問題まで記事にしました。
次回はコンテストで解けなかったD問題を復習していきたいと思います。

ABC192の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com