問題一覧 > 通常問題

No.3000 Optimal Run Length Encoding

レベル : / AI推定難易度 : 3000 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 4
作問者 : NyaanNyaan / テスター : akakimidori
お気に入りにしたユーザー ProblemId : 10348 / 自分の提出
問題文最終更新日: 2024-12-22 20:54:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2024 (順位表) の他の問題:

Problem Statement

Summary: You are given a string $S$. Apply run-length encoding to it so that the compressed string is as short as possible.
For a string $A$ of lowercase English letters and a string $B$ consisting of lowercase English letters and digits, $B$ is called a "run-length encoded string of $A$" if the following condition is satisfied.

  • The string generated from $B$ by the following procedure matches $A$.
    1. Take an integer $k$, $k$ non-empty strings of English letters $u_1, u_2, \dots, u_k$, and $k$ non-empty strings of digits $v_1, v_2, \dots, v_k$ such that $u_1 v_1 u_2 v_2 \dots u_k v_k$ matches $B$.
      (It can be proved that such $k, u_1, \dots, u_k, v_1, \dots, v_k$ are uniquely determined if they exist.)
      If no $k, u_1, \dots, u_k, v_1, \dots, v_k$ satisfying the condition exist, terminate the procedure without generating a string.
    2. Let $C$ be the empty string. For $i = 1, 2, \dots, k$ in this order, perform the following operation.
      • Let $x$ be the value of $v_i$ regarded as a number in decimal notation. Perform the operation of appending $u_i$ to the end of $C$ $x$ times.
    3. The string generated by the procedure is $C$ after the operations of step 2. are finished.
You are given a string $S$. Find one shortest string among the run-length encoded strings of $S$.
$T$ test cases are given, so find the answer for each of them.

Constraints

  • $1 \leq T \leq 5 \times 10^5$
  • $S$ is a string of lowercase English letters with length at most $5 \times 10^5$
  • The sum of $|S|$ over all inputs does not exceed $5 \times 10^5$.

Input

The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ denotes the $i$-th test case.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each test case is given in the following format.
$S$

Output

Print $T$ lines. The $i$-th line should contain the answer to the $i$-th test case. Also, print a newline at the end.
If there are multiple answers, you may print any of them.

Sample

Sample 1
Input
7
aabababc
abcdef
abaababaabaab
aaaaaaaaa
aaaaaaaaaa
baaaaaaaaa
baaaaaaaaaa
Output
a1ab3c1
abcdef1
abaab2aab1
a9
a10
b1a9
ba1a9

For the $1$st test case, for example, a2ba2bc1 and a1ab3c1 are run-length encoded strings of aabababc.
Among the run-length encoded strings of aabababc, a1ab3c1 is a shortest one, so print it.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。