本記事の目標
- ２通りの実装方法を知る
- 具体的な応用例(AtCoder Beginner Contestの問題)
具体例
連続する要素を(値, 連続個数)の形式 で圧縮するアルゴリズムです。
例えば、
strings = "aabbbbbbbbbbbba" #圧縮前
↓
[('a', 2), ('b', 12), ('a', 1)] #圧縮後実装コード
def rle(s):
n = len(s) #文字列の長さ
ans = [] #圧縮後のリスト
l = 0 #始点
while l<n:
r = l+1
while r<n and s[l]==s[r]: #異なる文字になるまで進む
r += 1
ans.append((s[l], r-l)) #文字,連続する個数
l = r #連続しなかった文字から探索を開始
return ans使い方
strings = "aabbbbbbbbbbbba" #圧縮前
print(rle(strings))
#[('a', 2), ('b', 12), ('a', 1)]itertools.groupby()の利用
自分で実装しなくても、pythonの標準ライブラリにランレングス圧縮を実行できる関数 itertools.groupby() が用意されています。
from itertools import groupby
strings = "aabbbbbbbbbbbba" #圧縮前
ans = [(k, len(list(g))) for k,g in groupby(strings)]
print(ans)
#[('a', 2), ('b', 12), ('a', 1)]応用例: AtCoder Beginner Contest 283: C
応用例として、以下の問題をランレングス圧縮を使って解いてみます。
高橋君は、レジ打ちの仕事をしています。
レジの機械には
00,0,1,2,3,4,5,6,7,8,9の 11 個のボタンがあります。 レジの機械には、はじめ 00 が表示されています。 ボタン00を押すと、表示されている数が 100 倍されます。 それ以外のボタンを押すと、表示されている数が 10 倍されたあとに、押されたボタンに書かれている数が加算されます。高橋君は、レジに整数 S を表示させたいです。 レジに S が表示されている状態にするためには、少なくとも何回ボタンを押す必要があるか求めてください。
AtCoder Beginner Contest 283 C: Cash Register
実装コード
def rle(s):
n = len(s) #文字列の長さ
ans = [] #圧縮後のリスト
l = 0 #始点
while l<n:
r = l+1
while r<n and s[l]==s[r]: #異なる文字になるまで進む
r += 1
ans.append((s[l], r-l)) #文字,連続する個数
l = r #連続しなかった文字から探索を開始
return ans
if __name__ == "__main__":
S = input()
Nums = rle(S) #ランレングス圧縮
ans = 0
for string, num in Nums:
#数字が0で、かつ 個数が偶数個の場合
if string == "0" and num%2==0:
ans += num//2
#数字が0で、かつ 個数が奇数個の場合
elif string =="0" and num%2==1:
ans += num//2 + 1
#0以外の数字
else:
ans += num
print(ans)例として、 $S=40004$ を入力した場合を考えます。
この時、ランレングス圧縮すると [('4', 1), ('0', 3), ('4', 1)] となります。
重要なのは数字が0の場合です。0が奇数個であれば、’00’を偶数回 + ‘0’を1回押すことが最適です。また、偶数個であれば、’00’を偶数回押すことが最適となります。
上記のコードで AC になることを確認できています。
まとめ
ランレングス圧縮の実装・利用方法についてまとめました。
自分で実装したコードは AtCoder Beginner Contest 019-B で正答になることは確認しています。
参考になれば幸いです
参考リンク: https://note.nkmk.me/python-itertools-groupby/
コメント