〜関数の分割，統一〜

皆様初めまして，今回講座を書こうと思い立ったKtyaであります．現時点で講座を投稿している2人よりは実力が大分劣るために，当たり前のような内容の羅列だったりとか，表現が下手，理解が下手なところが多々あるかもしれませんが駄文お許しを

さて今回はタイトルの通り"関数の分割"について圧縮テクを紹介していきたいと思います．

関数の分割

高校数学でも習う有名な不等式で，"相加相乗の不等式"というものがあったと思います．直感的には明らかですが，この不等式は二つの（正の）数については次のように言い換えられます．

二数の積が一定のとき，二数の和を小さくするのは二数の差が小さいとき

これは三数，四数となっても似たような事実が成り立ちます． この事実はHOJでも応用（というか皆さん直感的に利用していると思いますが）できます．和がコードの長さに対応していると思っていただければ分かると思います．（以下このように二数を近い数にする事で圧縮するテクを相加相乗と呼んでいきます）

例１ 4　を（一つだけ）作るには 4*1 とするより 2*2としたほうが短いです

a(X):XXXX
a(ssrssl)

よりも

a(X):XX
a(a(ssrssl))

の方が短く済みます．この例は非常に些細でどうでも良く，さらに四倍関数を1個という制限付きなので役に立たなさそうに見えますが，後で述べるテクニック（こちらもそこそこ条件付きですが）で応用できます．

さて，これに続き"関数の分割"と言うのを考えてみましょう． 例えば諸事情あって次のような関数を使いたくなったとしましょう

a(X):XXXXXXrXXXXXX
(15B)

この関数を"分割"（と言うより、別の関数を用いて再現）してみます． 繰り返し等の補助として用いた関数にさらに補助としての関数をつけると言う事です． 例えば次が考えられるでしょう

b(X):XXXXXX
a(X):b(X)rb(X)
(15B)

新しい関数b(X)を定義しつつ，全く同じ15Bを得ました．先ほどのa以外にbという新しい関数を定義しながらbyte数は同じなので明らかに上位互換です． ただこれだけだとa(X)飲み使いたい時は意味が無いです．そこで先程述べた相加相乗をかんがえるのです．上の書き方だと6倍関数に1個のX すなわち6*1で6を実現していましたがこれを3*2とすればよいのです．(本当はもう少し条件は複雑ですがここでは略記しておきます）すると下のような別のバリエーションを得られます

b(X):XX
a(X):b(XXX)rb(XXX)
(15B)
b(X):XXX
a(X):b(XX)rb(XX)
(14B)

後半はお分かりの通り，byte数を減らせる手法，前半は二倍関数で少し小回りもよく、と言う感じでしょうか

ここではもう一つ別の見方を紹介してこの例は終わりにします

b(X):XrX
a(X):b(XXXXXX)
(14B)

上の例でa(X)内でb(X)を二度用いている所にムダを感じたところが発端ですかね． これを行うとHOJではよくあるギザギザパーツsrslをb(s)lと言う具合に1byte減らす事が出来ます． 同様に相加相乗を施すと

b(X):XXrXX
a(X):b(XXX)
(13B)
b(X):XXXrXXX
a(X):b(XX)
(14B)

などが得られます．お分かりの通り一つ目は13Bというとても短いbyte数で実現出来ています． もちろんどれかが常に一番いい，と言う訳ではないのでこのような分割の仕方も色々頭に入れておくといいかもしれません．（今までbest化できていなかったものについても，これによりbest化できるかも？)

再帰への応用

HOJ講座

トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS