タイトルに反して、実はやりたかったのは符号化ではなく、下の本の最初の「帽子の問題」。 www.oreilly.co.jp 問題は、前向き/後向きバラバラに帽子を被った人たちが一列に並んでいる状況で、整理員が指示を出して全員の帽子を同じ方向になる様にする、というもの。指示は「○番から×番の人」のように範囲で指定できます。なるべく少ない回数でそれを達成するにはどうしたらよいか、というわけです。 パッとみただけで「あ、これランレングスみたいなのして偶奇で判定だ」とは閃いたので、本は読まずに見切り発車始めてしまったのですが、ここで、はて、ランレングスってどう書くのがエレガントかなー、と脱線し始め、そちらの迷宮にハマってしまった、というパターンですかっこわるー(実際この本でも迂回しながらランレングス圧縮にランディングしてます。合わせてLZのような話も出ていました)。一般のランレングスの場合、処理対象