結果

問題 No.205 マージして辞書順最小
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:48:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,128 bytes
コンパイル時間 304 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 85,168 KB
最終ジャッジ日時 2025-03-20 20:48:53
合計ジャッジ時間 7,933 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 3 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from functools import cmp_to_key

def compare(a, b):
    if a + b < b + a:
        return -1
    else:
        return 1

def main():
    n = int(sys.stdin.readline())
    strings = [sys.stdin.readline().strip() for _ in range(n)]
    
    current = [s for s in strings if s]
    result = []
    
    while current:
        # Determine the minimum current character
        min_char = min(s[0] for s in current)
        # Collect all candidates with the minimum character
        candidates = [s for s in current if s[0] == min_char]
        
        best_next = None
        best_combined = None
        
        for candidate in candidates:
            # Generate the new list after choosing this candidate
            new_list = []
            removed = False
            for s in current:
                if s == candidate and not removed:
                    # Take the rest of the string after removing the first character
                    rest = s[1:]
                    if rest:
                        new_list.append(rest)
                    removed = True
                else:
                    new_list.append(s)
            
            # Sort the new list using the custom comparator
            sorted_list = sorted(new_list, key=cmp_to_key(compare))
            combined = ''.join(sorted_list)
            
            current_combined = min_char + combined
            if best_combined is None or current_combined < best_combined:
                best_combined = current_combined
                best_next = candidate
        
        # Update current by removing the chosen character from best_next
        new_current = []
        removed = False
        for s in current:
            if s == best_next and not removed:
                rest = s[1:]
                if rest:
                    new_current.append(rest)
                removed = True
            else:
                new_current.append(s)
        # Remove any empty strings
        current = [s for s in new_current if s]
        result.append(min_char)
    
    print(''.join(result))

if __name__ == "__main__":
    main()
0