数値関数による長文圧縮

メニュー

• English Page
• イベント情報
• 問題
• 用語集
• HOJ講座
• 便利ツール
• 雑記
• リンク集
   

更新履歴

最新の10件

カウンター

今日：1 合計：1154

メニューを編集

数値関数による長文圧縮

フィールド全体を通して規則性に乏しく, どういう経路を選んでもかなりのバイト数を要する問題は, しばしば長文と呼ばれます.
今回は, 数値関数の助けを借りて長文を攻略する手法を紹介しましょう.

基本的な考え方

不規則な長文であるほど, 多くの種類のパーツを作りたいわけですが,
それら全てについて, 良い圧縮率を誇る関数を考えるのは, 困難といえるでしょう.
例えば1変数関数f(X)を用いて, f(-)の形で多くの種類のパーツを作る場合,
当然その引数もたくさんの種類が必要になってくるはずで,
でも引数の部分が巨大になると良い圧縮率は得られません.

そこで, 数値に注目します. 数値は, 1から255までの255種類ありながら, どれもが1Bとして扱われます.
したがって, 上手い数値関数f(T)を作ると,

255種類のパーツが, 全て2バイトf(-)として記述できる！

ことになります. もちろん「255種類のパーツ」とは言っても,
あまりに無秩序に各数値に割り当てるのは困難です.
そこで, 「ある程度統一性のある255種類」であり, なおかつ「長文圧縮に有効」と考えられるものとして,
次のようなものを数値に対応させることが考えられます：

1. [s] or [rs] or [rrs] or [rrrs] を合計4個並べたものは全部で256種ある. そのうち1種以外で255個.
2. [s] or [rs] or [ls] を合計5個並べたものは全部で243種ある.
3. [s] or [r] を合計8個並べたものは全部で256種ある. そのうち1種以外で255個.
4. [s] or [rs] を合計8個並べたものは全部で256種ある. そのうち1種以外で255個.

これらの使い分けについてですが, 第1, 第2の方法は, 左にも右にも曲がりやすいですね.
第2の方法は, 後ろを振り返れなくなっているので問題によっては使えないですが,
使える問題だと, 第1の方法に比べて1つの数値で多く配置できるので有効になるかもしれません.

第3, 第4の方法についてですが, これもやはり第4の方法では, 後ろを振り返れない代わりに圧縮率を追求しています.
第1の方法と第3の方法, 第2の方法と第4の方法を比べた場合, どういう形が作れるかという点では完全に一致しますが,
圧縮率は経路によって異なってきそうです. 例えば

ssssssss

だと第1の方法では2つ, 第3の方法では1つの数値に対応しますし,

lsrslsrslsrslsrs

だと第1の方法では2つ, 第3の方法では (lをrrrと見なして) 3つの数値に対応します.
基本的には, 直進が多いか否かで選び分けると良さそうですね.

実装例

すべて, f(1)からf(255)にそれっぽいのが現れるようになっています.

• s,rs,rrs,rrrsを4つ並べる. ただし「ssss」は作れない.

  a(T,A):ra(T-A,A)
  f(T):a(T,64)sa(T,16)sa(T,4)sa(T,1)s

  原理は詳しく説明しませんが, 大体4進法展開して(各桁+1)の回数だけrを並べる感じ.
  実際にはmod 4で等しいというだけで, 大量のrが並ぶので, 実行ステップ数は長くなります.
  「ssssが作れない」(f(0)やf(256)に相当する) ので, 経路を調整したり, ssllsllsssなどと,
  余分なものを紛れ込ませる必要がありますが, このタイプでは関数定義が現在知られているもののうち最小です.
  snuke氏が第2回HOJ祭りのProblem 1665の解として発表した関数.

• s,rs,rrs,rrrsを4つ並べる. ただし「rsrsrsrs」は作れない.

  a(X,T,A):Xa(r,T-A,A)
  f(T):a(,T,64)sa(,T,16)sa(,T,4)sa(,T,1)s

  上と大体同じ. 関数定義に2B余分に費やした代わりに, 犠牲が「rsrsrsrs」というあまり要らなさそうなもので済んでいます.

• s,rs,rrs,rrrsを4つ並べる. ただし「sssrrrs」は作れない.

  a(T,A):ra(T-A,A)
  f(T):a(T,64)sa(T,16)sa(T,4)sa(T,1)ls

  大体同じ. 第4項だけlを追加していて, ssssの代わりにssslsが犠牲になります.

• s,rs,rrs,rrrsを4つ並べる. ただし「srrrsss」は作れない.

  a(T,A):ra(T-A,A)
  f(T):a(T,64)sa(T,16)lsa(T,4)sa(T,1)s

  同様.

• s,rs,rrs,rrrsを4つ並べる. ただし「rrrsrrrsrrrsrrrs」は作れない.

  a(T,X):X
  b(N,T):rb(N,T-63)a(64-T,sb(N-1,T+T+T+T))
  f(T):b(4,T)

  T/63という分数の4進法小数展開を4段階で打ち切ったもの.
  1/63 = 0.001001001001....となることを利用しているらしいです.
  masが第2回HOJ祭りのProblem 1652の解として発表した関数だが, 残念ながら上記の関数の劣化？
  f(T)以外にb(-,-)を利用できる場面があればワンチャン. ガチ長文では難しいでしょうね. 一応紹介.

• s,rを8つ並べる. ただし「srrrrrrr」「rrrrrrrr」は作れない.

  a(T,X):X
  b(A,B,X):b(A-127,B,s)a(128-A,Xb(A+A,B-1,r))
  f(T):b(T,8,r)

  これも上記と同様で, T/127という有理数の2進法小数展開を打ち切っている,,はずです.
  

数値の並べ方

さて, f(T)という関数で, 色んなパーツを255種類すべて作れるようになりました！
例えばs,rs,rrs,rrrsを4つ並べた場合には, 「4歩が2Bになる！」というわけです.
しかし実際にはもうひと工夫することで, よりよい圧縮率が実現できます.
例えば次の定義をしましょう：

g(A,B,C,D,E,F):f(A)f(B)f(C)f(D)f(E)f(F)

この定義により, 6つの数値を7Bで呼び出せるようになります.
「4歩が1つの数値になる！」だったので, 「24歩が7Bになる！」となり, 約3.5歩を1Bにできました！
引数を増やしていくと, 当然どんどん圧縮率は上がります.
仮想的に, 26個を超えて無限に多く引数を持たせると, 圧縮率は実質「4歩が1B」となりますね.

しかし, 高い圧縮率を実現しようとすると, 関数定義の負担も増えていくので, ある程度のところで妥協しないといけません.

例えば, 90個の数値を並べることを考えましょう. この場合, gの引数を変化させると,

(gの定義) + (実行部分)

は次のように変化します：

• 引数1個：0 + 180.
• 引数2個：7 + 135.
• 引数3個：10 + 120.
• 引数4個：13 + (110 + 4).
• 引数5個：16 + 108.
• 引数6個：19 + 105.
• 引数7個：22 + 104.

gの定義は簡単ですね. 1つ引数を追加するたびに3B増えます.
実行部分は, 90の約数のところは簡単ですね. (90/N) * (N+1)というような式です.
引数7個の場合は約数になってはいないのですが, 91個の数値を並べてしまうことにしてしまうと, 104Bになります.
引数4個の場合はこの考え方だと92個の数値を並べて115Bになりそうですが,

(88個の数値を並べる) + f(A) + f(B)

とした方が,

(88個の数値を並べる) + g(A,B,C,D)

よりも短くなっています. このような計算を経て, 今回は引数が5個 or 6個として圧縮するのが最善だと分かります.

結局この方法で長文を解くには,

• 「s,rs,rrs,rrrs」あるいは「s,r」などの並びを数値1つにまとめる関数を定義する.
• s,rs,rrs,rrrsあるいはs,rなどを使ってとにかく全targetを回収する. 解答コード（文字列）を得る.
• もちろん少ないs, あるいは少ないs,rの個数であるほど良い.
• 用意した解答コードの各部分がどの数値に対応しているかを確認し, 数値の並びに変換する.
• 多くの数値をまとめて並べる関数を用意する. 並べる数値の個数に応じて引数の個数を調整する.

というステップが必要です. 問題によっては, s, rs, rrs, rrrsが500個以上も並ぶ場合もあり,
数値の並びに変換するステップは特に大変なので, 何らかのプログラムを用意しておくといいでしょう.

もちろん, 有用な「並べ方」はここに挙げたものばかりとは限りませんし,
同じ並べ方についても, より良い関数定義がありうるかもしれません.
是非色んな手法を模索してみてください！