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

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time


# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
# MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    B = sl()
    N = ii()

    ret = []
    for _ in range(N):
        A = iss()
        w = ''
        for a in A:
            for i in range(10):
                if a == B[i]:
                    w += str(i)
                    break
        else:
            ret.append([int(w), A])

    ret.sort()
    for _, a in ret:
        print(a)


if __name__ == '__main__':
    main()

考え方

AtCoder国で用いられる10進数の大小関係を、
我々が普段用いる大小関係に変換してソートします。

例えば、入力例1のような大小関係が与えられた場合について考えてみます。
入力例1の大小関係は0 < 8 < 1 < 3 < 5 < 4 < 9 < 7 < 6 < 2です。
我々が普段用いる大小関係と比較すると、
AtCoder国で用いられる8は我々の1にあたり、
AtCoder国で用いられる1は我々の2にとなります。

AtCoder国の値を我々が用いる値に変換することで、
単純なソートを行うことが出来ます。
例えば、入力例１の大小関係の場合、
AtCoder国の8は我々の1と扱うことができ、
AtCoder国の88は11、2を9、62を89として扱います。