[競プロ用]ランレングス圧縮まとめ

いつ使うのか

• 与えられる文字列で連続する回数・個数に着目する問題。

何がいいのか

画像圧縮などに利用される手法。膨大なデータを可逆性を損なわずに圧縮できる。
ただし、元データよりも必ずしもデータ量が少なくなるとは限らない。連続する構造の少ないデータでは逆に増加することもある。

どうするのか

同じ文字が何回繰り返されるかの文字と数字の組み合わせで表す。

テンプレート

from itertools import groupby

# RUN LENGTH ENCODING str -> list(tuple())
# example) "aabbbbaaca" -> [('a', 2), ('b', 4), ('a', 2), ('c', 1), ('a', 1)] 
def runLengthEncode(S: str) -> "List[tuple(str, int)]":
    grouped = groupby(S)
    res = []
    for k, v in grouped:
        res.append((k, int(len(list(v)))))
    return res

# RUN LENGTH DECODING list(tuple()) -> str
# example) [('a', 2), ('b', 4), ('a', 2), ('c', 1), ('a', 1)] -> "aabbbbaaca"
def runLengthDecode(L: "list[tuple]") -> str:
    res = ""
    for c, n in L:
        res += c * int(n)
    return res

# RUN LENGTH ENCODING str -> str
# example) "aabbbbaaca" -> "a2b4a2c1a1" 
def runLengthEncodeToString(S: str) -> str:
    grouped = groupby(S)
    res = ""
    for k, v in grouped:
        res += k + str(len(list(v)))
    return res

使用例

ABC019 B - 高橋くんと文字列圧縮

from itertools import groupby

# RUN LENGTH ENCODING
def runLengthEncodeToString(S: str):
    grouped = groupby(S)
    res = ""
    for k, v in grouped:
        res += k + str(len(list(v)))
    return res

def main():
    S = input()
    print(runLengthEncodeToString(S))

ABC143 C Slimes

from itertools import groupby

def runLengthEncode(S: str) -> "List[tuple(str, int)]":
    grouped = groupby(S)
    res = []
    for k, v in grouped:
        res.append((k, int(len(list(v)))))
    return res

def main():
    N = int(input())
    S = input()
    print(len(runLengthEncode(S)))
    return

ABC136 D - Gathering Children

最終的にはRとLの境界に集まる。移動回数の偶奇によって最後の移動がどちらかがかわるので偶奇だけ見ればいい。

from itertools import groupby

# RUN LENGTH ENCODING
def rfe_tuple(S: str):
    grouped = groupby(S)
    res = []
    for k, v in grouped:
        res.append((k, str(len(list(v)))))
    return res

def main():
    S = input()
    N = len(S)
    
    now = 0
    compressed = rfe_tuple(S)
    ans = [0] * N
    for lr, i in compressed:
        i = int(i)
        if lr == "R":
            now += i
            ans[now - 1] += i - i // 2
            ans[now] += i // 2
        else:
            ans[now - 1] += i // 2
            ans[now] += i - i // 2
            now += i
    
    L = [str(i) for i in ans]
    print(" ".join(L))
    return

ABC140 D - Face Produces Unhappiness

連続している部分を反転し、両端と繋がるようにすることで最大化できる。
両端はできれば反転させたくないので0番目は飛ばして奇数インデックスのみ反転させていく。

from itertools import groupby

# RUN LENGTH ENCODING
def runLengthEncode(S: str):
    grouped = groupby(S)
    res = []
    for k, v in grouped:
        res.append((k, str(len(list(v)))))
    return res

def runLengthDecode(L: "list[tuple]"):
    res = ""
    for c, n in L:
        res += c * int(n)
    return res

def main():
    N, K = map(int, input().split())
    S = input()
    compressed = runLengthEncode(S)

    for k in range(K):
        i = 2 * k + 1   # 奇数インデックスのみ反転させる。
        if i >= len(compressed):
            break
        compressed[i] = ('L', compressed[i][1]) if compressed[i][0] == "R" else ('R', compressed[i][1])

    reCompressed = runLengthEncode(runLengthDecode(compressed))
    ans = N - len(reCompressed)
    print(ans)

参考

itertoolsレファレンス
https://docs.python.org/ja/3/library/itertools.html#itertools.groupby