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.
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.
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)))
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))
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 itertools https://docs.python.org/ja/3/library/itertools.html#itertools.groupby
Recommended Posts