Run Length Encoding
(Sequence/Run_Length_Encoding.py)

• View this file on GitHub
• Last update: 2025-07-27 21:16:37+09:00

Outline

$\mathcal{A}$ をアルファベットする. 長さ $N$ の $\mathcal{A}$ の列 $S=(S_i)_{i=1}^N$ に対して, 以下を満たすような列 $T=((\alpha_j, k_j))_{j=1}^M$ を求める.

• $\forall j=1,2, \dots, M;~\alpha \in \mathcal{A}, k_j \geq 0$.
• $\forall j=1,2, \dots, M-1;~\alpha_j \neq \alpha_{j+1}$
• $S=(\underbrace{\alpha_1, \dots, \alpha_1}_{k_1}, \dots, \underbrace{\alpha_M, \dots, \alpha_M}_{k_M})$

このような $T$ を $S$ の Run Length Encoding (連長圧縮) という. なお, RLE は一意に定まる.

Code

def Run_Length_Encoding(S):
    """ Run Length 圧縮

    S: 列
    """
    if not S:
        return []

    R=[[S[0],1]]

    for i in range(1,len(S)):
        if R[-1][0]==S[i]:
            R[-1][1]+=1
        else:
            R.append([S[i],1])

    return R

def Alternating_Length_Encoding(S, first, second, equal = True) -> tuple[list[int], list[int]]:
    """ アルファベットサイズが 2 である列 S に対して, 最初に現れる first と残りの second について, それぞれが連続して現れる回数のリストを求める.

    Args:
        S: 列
        first: 最初に現れる文字
        second: 次に現れる文字
        equal (bool, optional): True にすると, 返り値における 2 つの配列の長さが等しくなる. Defaults to True.

    Returns:
        tuple[list[int], list[int]]: X, Y を整数のリストとしたタプル (X, Y). これは以下を意味する.
            * S = (first が連続して X[0] 個)(second が連続して Y[0] 個)(first が連続して X[1] 個)(second が連続して Y[1] 個)...
    """
    x: list[int] = []
    y: list[int] = []

    if S[0] == second:
        x.append(0)

    for a, k in Run_Length_Encoding(S):
        if a == first:
            x.append(k)
        else:
            y.append(k)

    if equal and len(x) > len(y):
        y.append(0)

    return x, y

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ~~~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page