Eine Methode zur Bildkomprimierung. Eine große Datenmenge kann komprimiert werden, ohne die Reversibilität zu beeinträchtigen. Die Datenmenge ist jedoch nicht immer kleiner als die der Originaldaten. Im Gegenteil, es kann für Daten mit wenigen kontinuierlichen Strukturen zunehmen.
Es wird durch eine Kombination von Buchstaben und Zahlen dargestellt, die angibt, wie oft derselbe Buchstabe wiederholt wird.
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))
Schließlich wird es sich an der Grenze zwischen R und L sammeln. Entweder ändert sich der letzte Zug abhängig von der Anzahl der Züge, sodass Sie nur die Gewinnchancen betrachten müssen.
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
Sie kann maximiert werden, indem das durchgehende Teil umgedreht und an beiden Enden angeschlossen wird. Ich möchte nicht beide Enden invertieren, wenn möglich, also überspringe den 0. und invertiere nur den ungeraden 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 #Invertiere nur ungerade Indizes.
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 Referenz https://docs.python.org/ja/3/library/itertools.html#itertools.groupby
Recommended Posts