数値関数による長文圧縮
をテンプレートにして作成
[
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
メニュー
]
開始行:
*数値関数による長文圧縮 [#rddb2d60]
フィールド全体を通して規則性に乏しく,
どういう経路を選んでもかなりのバイト数を要する問題は, し...
今回は, 数値関数の助けを借りて長文を攻略する手法を紹介し...
**基本的な考え方 [#ad322ddf]
不規則な長文であるほど, 多くの種類のパーツを作りたいわけ...
それら全てについて, 良い圧縮率を誇る関数を考えるのは, 困...
例えば1変数関数f(X)を用いて, f(-)の形で多くの種類のパーツ...
当然その引数もたくさんの種類が必要になってくるはずで, ~
でも引数の部分が巨大になると良い圧縮率は得られません.
そこで, 数値に注目します. 数値は, 1から255までの255種類あ...
したがって, 上手い数値関数f(T)を作ると,
> 255種類のパーツが, 全て2バイトf(-)として記述できる!
ことになります. もちろん「255種類のパーツ」とは言っても, ~
あまりに無秩序に各数値に割り当てるのは困難です. ~
そこで, 「ある程度統一性のある255種類」であり, なおかつ「...
次のようなものを数値に対応させることが考えられます:
+[s] or [rs] or [rrs] or [rrrs] を合計4個並べたものは全部...
+[s] or [rs] or [ls] を合計5個並べたものは全部で243種ある.
+[s] or [r] を合計8個並べたものは全部で256種ある. そのう...
+[s] or [rs] を合計8個並べたものは全部で256種ある. そのう...
これらの使い分けについてですが, 第1, 第2の方法は, 左にも...
第2の方法は, 後ろを振り返れなくなっているので問題によって...
使える問題だと, 第1の方法に比べて1つの数値で多く配置でき...
第3, 第4の方法についてですが, これもやはり第4の方法では, ...
第1の方法と第3の方法, 第2の方法と第4の方法を比べた場合, ...
圧縮率は経路によって異なってきそうです. 例えば
> ssssssss
だと第1の方法では2つ, 第3の方法では1つの数値に対応します...
> lsrslsrslsrslsrs
だと第1の方法では2つ, 第3の方法では (lをrrrと見なして) 3...
基本的には, 直進が多いか否かで選び分けると良さそうですね.
**実装例 [#wd85c0bb]
すべて, 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)の回...
実際にはmod 4で等しいというだけで, 大量のrが並ぶので, 実...
「ssssが作れない」(f(0)やf(256)に相当する) ので, 経路を調...
余分なものを紛れ込ませる必要がありますが, このタイプでは...
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余分に費やした代わりに, 犠牲が...
- 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進法小数展開を打...
**数値の並べ方 [#if7492d0]
さて, 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になる!...
引数を増やしていくと, 当然どんどん圧縮率は上がります. ~
仮想的に, 26個を超えて無限に多く引数を持たせると, 圧縮率...
しかし, 高い圧縮率を実現しようとすると, 関数定義の負担も...
例えば, 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個の数値を...
引数4個の場合はこの考え方だと92個の数値を並べて115Bになり...
> (88個の数値を並べる) + f(A) + f(B)
とした方が,
> (88個の数値を並べる) + g(A,B,C,D)
よりも短くなっています. このような計算を経て, 今回は引数...
----
結局この方法で長文を解くには,
-「s,rs,rrs,rrrs」あるいは「s,r」などの並びを数値1つにま...
-s,rs,rrs,rrrsあるいはs,rなどを使ってとにかく全targetを回...
-もちろん少ないs, あるいは少ないs,rの個数であるほど良い.
-用意した解答コードの各部分がどの数値に対応しているかを確...
-多くの数値をまとめて並べる関数を用意する. 並べる数値の個...
というステップが必要です. 問題によっては, s, rs, rrs, rrr...
数値の並びに変換するステップは特に大変なので, 何らかのプ...
もちろん, 有用な「並べ方」はここに挙げたものばかりとは限...
同じ並べ方についても, より良い関数定義がありうるかもしれ...
是非色んな手法を模索してみてください!
終了行:
*数値関数による長文圧縮 [#rddb2d60]
フィールド全体を通して規則性に乏しく,
どういう経路を選んでもかなりのバイト数を要する問題は, し...
今回は, 数値関数の助けを借りて長文を攻略する手法を紹介し...
**基本的な考え方 [#ad322ddf]
不規則な長文であるほど, 多くの種類のパーツを作りたいわけ...
それら全てについて, 良い圧縮率を誇る関数を考えるのは, 困...
例えば1変数関数f(X)を用いて, f(-)の形で多くの種類のパーツ...
当然その引数もたくさんの種類が必要になってくるはずで, ~
でも引数の部分が巨大になると良い圧縮率は得られません.
そこで, 数値に注目します. 数値は, 1から255までの255種類あ...
したがって, 上手い数値関数f(T)を作ると,
> 255種類のパーツが, 全て2バイトf(-)として記述できる!
ことになります. もちろん「255種類のパーツ」とは言っても, ~
あまりに無秩序に各数値に割り当てるのは困難です. ~
そこで, 「ある程度統一性のある255種類」であり, なおかつ「...
次のようなものを数値に対応させることが考えられます:
+[s] or [rs] or [rrs] or [rrrs] を合計4個並べたものは全部...
+[s] or [rs] or [ls] を合計5個並べたものは全部で243種ある.
+[s] or [r] を合計8個並べたものは全部で256種ある. そのう...
+[s] or [rs] を合計8個並べたものは全部で256種ある. そのう...
これらの使い分けについてですが, 第1, 第2の方法は, 左にも...
第2の方法は, 後ろを振り返れなくなっているので問題によって...
使える問題だと, 第1の方法に比べて1つの数値で多く配置でき...
第3, 第4の方法についてですが, これもやはり第4の方法では, ...
第1の方法と第3の方法, 第2の方法と第4の方法を比べた場合, ...
圧縮率は経路によって異なってきそうです. 例えば
> ssssssss
だと第1の方法では2つ, 第3の方法では1つの数値に対応します...
> lsrslsrslsrslsrs
だと第1の方法では2つ, 第3の方法では (lをrrrと見なして) 3...
基本的には, 直進が多いか否かで選び分けると良さそうですね.
**実装例 [#wd85c0bb]
すべて, 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)の回...
実際にはmod 4で等しいというだけで, 大量のrが並ぶので, 実...
「ssssが作れない」(f(0)やf(256)に相当する) ので, 経路を調...
余分なものを紛れ込ませる必要がありますが, このタイプでは...
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余分に費やした代わりに, 犠牲が...
- 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進法小数展開を打...
**数値の並べ方 [#if7492d0]
さて, 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になる!...
引数を増やしていくと, 当然どんどん圧縮率は上がります. ~
仮想的に, 26個を超えて無限に多く引数を持たせると, 圧縮率...
しかし, 高い圧縮率を実現しようとすると, 関数定義の負担も...
例えば, 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個の数値を...
引数4個の場合はこの考え方だと92個の数値を並べて115Bになり...
> (88個の数値を並べる) + f(A) + f(B)
とした方が,
> (88個の数値を並べる) + g(A,B,C,D)
よりも短くなっています. このような計算を経て, 今回は引数...
----
結局この方法で長文を解くには,
-「s,rs,rrs,rrrs」あるいは「s,r」などの並びを数値1つにま...
-s,rs,rrs,rrrsあるいはs,rなどを使ってとにかく全targetを回...
-もちろん少ないs, あるいは少ないs,rの個数であるほど良い.
-用意した解答コードの各部分がどの数値に対応しているかを確...
-多くの数値をまとめて並べる関数を用意する. 並べる数値の個...
というステップが必要です. 問題によっては, s, rs, rrs, rrr...
数値の並びに変換するステップは特に大変なので, 何らかのプ...
もちろん, 有用な「並べ方」はここに挙げたものばかりとは限...
同じ並べ方についても, より良い関数定義がありうるかもしれ...
是非色んな手法を模索してみてください!
ページ名: