〜関数の分割,統一〜

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

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

関数の分割

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

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

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

例1 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化できるかも?) 作るパーツに応じて変えるるのが良いでしょう


再帰への応用

(具体例は追々追加する可能性があります) 今まではそのうち止まるコード(=再帰を利用しない)について述べていましたが今回は再帰のコードについてこの事実が応用出来る例を述べましょう. ちなみに使用される事はあまりないので特殊な状況でしか使わないかもしれません.

これは2歩進んだ後右に2*(n-1)歩分の十字,左に2*n歩分の十字を作って と言うのを繰り返す問題です.(この規則が分かるのが難しいのはここでは問題にはしませんw)

さて実装方法ですが,まずは愚直に四倍関数を用いて

b(X):XXXX
a(X):ssa(rXX)rra(rsXsX)a(sX)
b(s)a(r)(31B)

もちろんこれを縮めていってもいいですがここでは成長速度の調整を用いましょう(すると厄介な四歩分の位置調整も少し消えてくれます)

b(X):XXXXrr
a(X,Y):ssb(rYY)b(rXX)a(sX,X)
ssa(r,)

(Yに1個前のXを保存する事で上のような書き方を回避しました) さらに成長速度を1個分遅くする事で最初の二歩も消せてお得です

b(X):XXXXrr
a(X,Y,Z):ssb(rZZ)b(rYY)a(sX,X,Y)
a(r,,)
(29B)

これはrXXと言う関数を次のように組み込むと縮みます

a(X,Y,Z):ssZZZZrrYYYYrra(sX,rXX,Y)
a(r,,)
(27B)

これを関数の分割(1*4を2*2にする)を行う事で最終的には次のように出来ます

a(X,Y,Z):ssZZrrYYYYrra(sX,rXX,YY)
a(r,,)
(26B)

この問題については少し経路を変更する事(というかそっちが先に思いつく人も多いと思いますがw)でもう少し縮むのでトライしてみてください.(こっちを更新するかもしれません)

まずこの状況を上手く再現する事が出来る場合があります,それはあるパーツを偶数個のもののみくっつけたもの,もしくはあるパーツを奇数個のみくっつけたものを作りたい時です.こんな状況なかなかなさそうですが意外と使える場面はあります.さらにこの状況下で上で述べた"相加相乗"が応用出来る場合があります. かなり限られた場合ですので問題を書いておきます..

HOJ講座


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2013-02-07 (木) 22:08:18 (2021d)