結果

問題 No.3036 Nauclhlt型文字列
ユーザー nhtloc
提出日時 2025-04-06 09:43:49
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,466 bytes
コンパイル時間 480 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 88,916 KB
最終ジャッジ日時 2025-04-06 09:43:55
合計ジャッジ時間 6,054 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 11 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import List
import sys

def compress(s: str) -> str:
    n = len(s)
    dp = [float('inf')] * (n + 1)
    backtrack = [(-1, "")] * (n + 1)
    dp[0] = 0  # empty string

    for i in range(1, n + 1):
        # try all possible block sizes that end at i
        for l in range(1, i + 1):
            substr = s[i - l:i]
            max_repeat = 1
            # check how many times substr repeats ending at position i
            while i - l * max_repeat >= 0 and s[i - l * max_repeat:i - l * (max_repeat - 1)] == substr:
                max_repeat += 1
            max_repeat -= 1
            if max_repeat == 0:
                continue
            start_pos = i - l * max_repeat
            cost = dp[start_pos] + len(substr) + len(str(max_repeat))
            if cost < dp[i]:
                dp[i] = cost
                backtrack[i] = (start_pos, substr + str(max_repeat))

    # Reconstruct compressed string
    result = []
    i = n
    while i > 0:
        prev, part = backtrack[i]
        result.append(part)
        i = prev

    return ''.join(reversed(result))

def solve_all(strings: List[str]) -> List[str]:
    return [compress(s) for s in strings]  # process each string independently

if __name__ == "__main__":
    import sys
    input_lines = [line.strip() for line in sys.stdin if line.strip()]
    T = int(input_lines[0])
    strings = input_lines[1:T+1]
    results = solve_all(strings)
    for res in results:
        print(res)
0