[Pour les professionnels de la compétition] Résumé de la compression de la longueur de tirage

Quand utiliser

Ce qui est bon

Une méthode utilisée pour la compression d'image. Une énorme quantité de données peut être compressée sans nuire à la réversibilité. Cependant, la quantité de données n'est pas toujours inférieure à celle des données d'origine. Au contraire, il peut augmenter pour les données avec peu de structures continues.

Que faire

Il est représenté par une combinaison de lettres et de chiffres qui indique combien de fois la même lettre est répétée.

modèle

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)))

Exemple d'utilisation

ABC019 B --Takahashi-kun et compression de chaîne de caractères

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

Finalement, il se rassemblera à la frontière entre R et L. Soit le dernier coup change en fonction du nombre de coups, il suffit donc de regarder les cotes.

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

Il peut être maximisé en inversant la partie continue et en la connectant aux deux extrémités. Je ne veux pas inverser les deux extrémités si possible, alors sautez le 0 et inversez uniquement l'index impair.

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   #N'inversez que les index impairs.
        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)

référence

référence itertools https://docs.python.org/ja/3/library/itertools.html#itertools.groupby

Recommended Posts

[Pour les professionnels de la compétition] Résumé de la compression de la longueur de tirage
Résumé de la recherche Bisection pour les professionnels de la concurrence
[Pour les professionnels de la concurrence] Résumé du doublement
[Pour les professionnels de la compétition] Résumé de l'arborescence de surface minimale
[Pour les professionnels de la concurrence] Union Find tree summary
[Pour les professionnels de la concurrence] Résumé des facteurs premiers, des réductions et des facteurs premiers
[Pour les professionnels de la concurrence] Résumé de la file d'attente prioritaire (heapq)
Résumé de l'apprentissage RAPIDS
Résumé de l'utilisation de Pipenv (pour moi-même)