[For competition professionals] Run-length compression summary

When to use

What is good

A method used for image compression. A huge amount of data can be compressed without impairing reversibility. However, the amount of data is not always smaller than that of the original data. On the contrary, it may increase for data with few continuous structures.

What to do

It is represented by a combination of letters and numbers that indicates how many times the same letter is repeated.

template

from itertools import groupby

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

# RUN LENGTH DECODING tuple -> str
def runLengthDecode(L: "list[tuple]"):
    res = ""
    for c, n in L:
        res += c * int(n)
    return res

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

Example of use

ABC019 B --Takahashi-kun and string compression

from itertools import groupby

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

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

ABC136 D - Gathering Children

Eventually it will gather at the boundary between R and L. Either the last move changes depending on the number of moves, so you only have to look at the odds.

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

It can be maximized by inverting the continuous part and connecting it to both ends. I don't want to invert both ends if possible, so skip the 0th and invert only the odd index.

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   #Invert only odd indexes.
        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)

reference

itertools reference https://docs.python.org/ja/3/library/itertools.html#itertools.groupby

Recommended Posts

[For competition professionals] Run-length compression summary
Binary search summary for competition professionals
[For competition professionals] Summary of doubling
[For competition professionals] Minimum spanning tree summary
[For competition professionals] Union Find Tree Summary
[For competition professionals] Prime number, divisor, prime factorization summary
[For competition pros] Priority queue (heapq) Summary
Summary for learning RAPIDS
Pipenv usage summary (for myself)
Reference resource summary (for beginners)