ARC009 B - おとぎの国の高橋君

「なるほど！」と思った問題。わかってしまえば簡単かも。

問題

arc009.contest.atcoder.jp

0～9の数字の、新しい大小関係が与えられる。この大小関係に沿って、与えられるN個の数を昇順にソートせよ。

解法

初めてこの問題を見たときは「比較関数を作って、それをソート関数に渡して……いやソートも自分で実装しなきゃいけないのかな、バブルソートじゃ間に合わないよな……」などと考えていたのですが、そんなことはなかった。

数字の順番が入れ替わっているから悪いのです。ということで、一旦数字を普通の順番に置換し、普通の順番でソートしてから逆置換して戻します。たとえば以下のように。

1. 大小関係「4 < 2」で52と54をソートするなら、
2. 52→54, 54→52と置換
3. 普通の順序(2 < 4)で置換後の数をソート→「52, 54」
4. 置換した文字をもとに戻す(52→54, 54→52)
5. 「54, 52」が答え

こうすれば比較関数とか自分で作る必要はなく、ソートは言語で用意されているものをそのまま使えます。

num = '0123456789'
b = ''.join(input().split())
N = int(input())
a = [input() for i in range(N)]
 
for i in range(N):
    a[i] = int(a[i].translate(str.maketrans(b, num)))
 
a.sort()
 
for i in range(N):
    print(str(a[i]).translate(str.maketrans(num, b)))

こういう文字列処理を使った問題はPythonのありがたみを感じる。