数字の神

白駿1422号:数字の神

アイデア

aとbの2つの数字の中でどの数字が前にあるべきか考えてみましょう.まず前列の大きい数字が一番前に出なければなりません.問題は、前の2つの同じ数字(232と23212と21)を比較することです.長い数字がa,短い数字がbの場合,比較aではオーバーラップ部分のsubstirngとbを取り除く.繰り返し続けると、どの数字が前にあるかを決めることができます.232と23に現れるべき数字を直接計算します.
232 vs 23
2 vs 23
2 vs 3
23は前にあるはずです.
また、NがKより大きい場合は、最大の数を複数回使用するだけでよい.前の位置は大きな数字を使うようですが、これは錯覚です.もちろん、同じ数字を連続的に使うべきです.
ex) 9, 80 -> 98080(O) 80980(X)

コード#コード#

import sys
from functools import cmp_to_key
input = sys.stdin.readline

K, N = map(int, input().split())
numlist = [input().rstrip() for _ in range(K)]

def compare(a, b):
    if a == b:
        return 0
    if len(a) >= len(b):
        for i in range(len(b)):
            if a[i] > b[i]:
                return -1
            elif a[i] < b[i]:
                return 1
        return compare(a[len(b):], b)
    else:
        for i in range(len(a)):
            if a[i] > b[i]:
                return -1
            elif a[i] < b[i]:
                return 1
        return compare(a, b[len(a):])

s_list = sorted(numlist, key=cmp_to_key(compare))
m = ''
for i in s_list:
    if len(i) > len(m):
        m = i
    elif int(i) > int(m):
        m = i

cnt = N - K
for i in s_list:
    if i == m:
        while cnt > 0:
            print(i, end='')
            cnt -= 1
    print(i, end='')

説明:

functoolsという見知らぬライブラリを使用しました.
デフォルトでは、Python 3でソート基準を決定するキーには、パラメータを受信する関数が使用されます.

>>> student_tuples = [
...     ('john', 'A', 15),
...     ('jane', 'B', 12),
...     ('dave', 'B', 10),
... ]
>>> sorted(student_tuples, key=lambda student: student[2])   # sort by age
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

このように、keyに書き込まれた関数が返す値に基づいてソートされる.しかしfunctoolsのcmp to keyを用いて旧式比較関数をkey関数に変換することができる.古い比較関数とは何ですか.
関数は2つの要素(a,b)をパラメータとし、関数が負の値を返すとaはbの前に、正の値を返すとbはaの前に並ぶ.JavaでcompareTo overridingをしているような感じ?
Python 2はこの方式を使用しています

sorted(mylist, cmp=lambda item1, item2: fitness(item1) - fitness(item2))

Python 3はこの方式を使用しています.

from functools import cmp_to_key
sorted(mylist, key=cmp_to_key(lambda item1, item2: fitness(item1) - fitness(item2)))

比較関数で返される値に基づいてソートします.

おしゃべり

比較関数を書くとき、aとbの2つの数字をつなぎ合わせて大きさを比較すると、もっと簡単ではないかと考えました.フナです.

リファレンス

Sort a list of lists with a custom compare function
functools