No.3000 Optimal Run Length Encoding
レベル :
/ AI推定難易度 : 3000
/ 実行時間制限 : 1ケース 10.000秒 / メモリ制限
: 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 4
作問者 :
NyaanNyaan
/ テスター :
akakimidori
タグ : / 解いたユーザー数 4
作問者 :
akakimidori
問題文最終更新日: 2024-12-22 20:54:49
English (AI translation)
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$.
- 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. -
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.
- The string generated by the procedure is $C$ after the operations of step 2. are finished.
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。