ランレングス圧縮の魅力　～茶diff攻略への強い味方～ - YU2TA7KA's BLOG ～take one step at a time～

0. はじめに
1. ランレングス圧縮（Run Length Encoding）とは
2. ランレングス圧縮の効果
3. ランレングス圧縮の魅力
4. ランレングス圧縮関連の問題例
5. 実装例
6. おわりに
7. 参考
8. 競技プログラミング関連書籍

組み込みエンジニアをしているyu2ta7kaです。茶diff埋めをしているときに魅了されたランレングス圧縮について書きます。

0. はじめに

競技プログラミングサイトのAtCoderはすでに数百回のコンテストが開催され、その過去問は3,000を超えます。それらの問題は有志のAtCoder Problemsというツールによってdifficulty（色）が与えられており、これを参照することで自分の実力に合った問題に挑戦することができます。その中で入門（灰色）の次レベルにあたる茶色問題を解くにあたり、強い味方となる「ランレングス圧縮」について書きます。
ファクシミリ画像（余白の多い白黒2値画像）の圧縮などに用途例がありますが、本記事では競技プログラミングの問題を解く観点にフォーカスして書いていきます。

1. ランレングス圧縮（Run Length Encoding）とは

連続する文字列をその文字と連続する個数の2文字で表現することで、データを可逆圧縮するアルゴリズムです。

数字も文字なので数字列に対してもランレングス圧縮は可能です。計算量は $O(N)$ です。

2. ランレングス圧縮の効果

大きな入力データを圧縮できる

圧縮アルゴリズムの本義です。例えば、 $n = 10^{100}$ 個という大きなデータ列であっても、それが全て同じ $a$ という文字であれば、 $a,1000$ とランレングス圧縮することで、扱うことが可能になります。

連続する同じ文字とその個数に着目するができる

文字列をランレングス圧縮することで、解答の実装がしやすくなります。
例えば、Kenken Raceという問題では、'.'で表現される何もないマスと'#'で岩があるマスが登場します。これらが、どれだけ続いているかを表現するためにランレングス圧縮をします。'...#...##...'は'.3#1.3#2.3'となります。pythonの二次元リストで表現したら、[[.,3],[#,1],[.,3],[#,2],[.,3]]となります*1。このリストデータを使って、制約を満たした状態で要求された操作が可能か判定するプログラムを実装することでAC*2できました*3。

変化点のみに着目することができる

数字列をランレングス圧縮することで、変化点にフォーカスした実装がしやすくなります。
この効果をRoad to Millionaireという問題で知って、個人的には目からウロコで魅了されました。
Road to Millionaireは、予め株価の変動推移が与えられ、所持金を最大にするように株の売買をした結果を求める問題です*4。2日間で株価が変動しないところはその間で売買を行っても、変化がないため考慮が不要です。そこで、変動推移の数字列をランレングス圧縮してしまいます。そうすると圧縮後の数字列は変化点のみになり、この数値を使うことで株価変動無し時の考慮を省いて単純化して、売買アルゴリズムを実装するができるようになります！凄くないですか！？

3. ランレングス圧縮の魅力

ランレングス圧縮の効果を3つ挙げました。大きなデータを圧縮し、データサイズを小さくできる効果に加えて、抽象化してデータを考察、操作できるようになることが魅力と思います。また、簡単なアルゴリズムの割に応用範囲が広いところも良いなと思います。
問題を解いている中で、ランレングス圧縮することで視野が開ける感じを感じた瞬間が気持ち良いです。ランレングス圧縮に限らないのですが、データをうまく構造化することで見通しがよくなる快感は競技プログラミングをする中でACする次に気持ち良い瞬間ではないでしょうか？*5

4. ランレングス圧縮関連の問題例

問題名	ランレングス圧縮の用途
B - 高橋くんと文字列圧縮	まさにランレングス圧縮をやってみよう
D - Integer Cards	大きなデータを圧縮して扱う
A - Connection and Disconnection	連続する同じ文字と個数に着目するために抽象化
A - ><	連続する同じ文字と個数に着目するために抽象化
A - Kenken Race	連続する同じ文字と個数に着目するために抽象化
D - Gathering Children	連続する同じ文字と個数に着目するために抽象化
D - Road to Millionaire	変化点のみに着目するために抽象化、数字列に対する適用
C - Big Array	入力データがランレングス圧縮されたデータ。圧縮データを展開したときのことを考える問題とも捉えられる。

5. 実装例

 fn rle(s: Vec<char>) -> Vec<(char, u64)> {
     let mut res: Vec<(char, u64)> = Vec::new();
     let mut pre = ' ';
     let mut chain = 1;
 
     for c in s.into_iter() {
         if c == pre {
             chain += 1;
         } else {
             if pre != ' ' {
                 res.push((pre, chain));
             }
             pre = c;
             chain = 1;
         }
     }
     res.push((pre, chain));
     res
 }