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.
It is represented by a combination of letters and numbers that indicates how many times the same letter is repeated.
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))
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)
itertools reference https://docs.python.org/ja/3/library/itertools.html#itertools.groupby
Recommended Posts