[[HOJ講座]]

長文問題の考察
今回は長文（ここでは規則が定まっていない問題のことを簡略のため長文と定義します)について触れようと思います．
長文問題をしっかりと圧縮しているプレイヤーはここ最近まで一人しかおらず，他のプレイヤーは大きく引き離されていました．
殆ど全ての長文問題でその一人がbestを取り続けていたために人々は何時しかそういう規則のない問題を敬遠するように成って行きました．
自分自身その一人が圧倒的な技術を持っているがために頑張っても追いつけないと思い込んでいましたが，改めて眺めてみるとそうではない事が分かりました．
長文問題の解き方と言うのは完全に決まっている訳ではありませんが基本的なメソッドはやはりこのタイプの問題の
先駆者であるmasさんの書いたhttp://mashojer.web.fc2.com/spring_festival_2012_solutions.htmlの最初の問題の解説を追うのが最も良いでしょう．
とは言ってもやはり問題に対してアプローチは大きく異なってきます．と言う事で"こうやれば絶対いい感じに圧縮出来る！!"なんてものは無い訳です．
と言う事で各問題に対する自分の考察を書いて行きます．ヒント，と言うタイトルにしようかとも思いましたが，それほどの自信は無いので考察で，
長文問題の解き方と言うのは完全に決まっている訳ではありませんが基本的なメソッドはやはりこのタイプの問題の先駆者であるmasさんの書いたhttp://mashojer.web.fc2.com/spring_festival_2012_solutions.htmlの最初の問題の解説を追うのが最も良いでしょう．
とは言ってもやはり問題によってアプローチは大きく異なってきます．と言う事で"こうやれば絶対いい感じに圧縮出来る！!"なんてものは無い訳です．
ですが，ここでは一般に有用な手法（というか書き方？）について少し触れます

§0 経験則
いくつか長文を解いていて得た経験則
-a(X):pa(X-1)などの任意のnに対してpをn回やる　と言う関数は使わない方が良い

関数定義に6Bもかかる割にpを繰り返すしか出来ず，さらに分割ができない
一見小回りが利くように見えてa(X):pXqとの相性がかなり悪いので小回りは寧ろ聞かない

-単純なn倍関数は使わない方が良い
同じパーツが明らかに多い場合を除き単純なn倍はa(X):pXqよりやや弱いイメージがあります．
一度a(...)でかこってしまうとたとえばb(X):pXq
一度a(...)でかこってしまうとたとえばb(X):pXqなどがどうしても使いにくくなります
例として
 p:aaa
 q:bbb
 ppppssrsppppssrsqqqsrqppq
 (33B)
というコードがあるときは
 p:aaa
 q:bbb
 c(X):XX
 c(c(pp)ssrs)qqqsrqppq
 (29B)
 
よりも
 p:aaa
 q(X):ppXbbb
 q(q(ssrsq(q(ssrs)))sr)q()
 (27B)
の方が短いです．ここまで露骨じゃなくても，パーツの個数が通常の問題よりも多くなるのでa(X):pXqの方が小回りが利くのです．
応用としてXXXpYqと言った類いの多変数+命令(ただし一つの変数が空ならただのa(X):pXqの形)という類いも有用な事が多いです．
ちなみに上のコードはこんな感じにもなります
 p:aaa
 q(X):ppXbbb
 d(X):q(q(sssrX))
 d(d())sr)q()
 (26B)


-置換した文字の使用回数が少ない場合は関数を考察しよう

例えば
 a:10文字
 ssrsrrsssaa
 ssrsrrsssaa...
のような状況の時は，二倍関数や，f(X):sXXとかf(X):ssXXとかf(X):rsssXXとかを作るとすごく有用だったりします

-同じ文字を生成するようにしよう
a(X):ssssXsssといったような関数を使っていると使える事があります

たとえば
 a(X):ssssXsss
 a(a(sa(rssr)a(sr)s)ra(ssr))
というコード，ぱっと見で諦める人もいるかもしれませんが2B縮みます．sをずらせるからです．
 a(X):ssssXsss
 a(a(a(srssr)a(sr))sra(ssr))
これによってsrがたくさん出来たのでこれを置換します．
 b:sr
 a(X):ssssXsss
 a(a(a(bsb)a(b))ba(sb))
こんな感じでしょうかね 

-壁を使う（もしくは使える）箇所をメモしておく

自分がよくやるのはどれか一文字を空で定義しておいて(wallのwをつかう派です)こんな感じで書く手法(コードは特にどの問題も意識していません）
 p:srslsrslsrslsrsl
 w:
 ssssprpssswrrsspprpprpppsrsspwrrsspppssp
こんな感じ．wがマーカーみたいなイメージです．
例えばb(X):ssXpのような関数を定義すると前半で"左側にssがない！！"みたいな状況になっちゃう訳ですが
 p;srslsrslsrslsrsl
 w:
 b(X):ssXp
 b(b()r)sb(wrrb())rpprpppsrb()wrrb()ppb()

前半で"左側にssがないから使えない！！"みたいな状況になっちゃう訳ですが，そこをwの所に押し付ける訳です．こんな感じ
 b(X):ssXsrslsrslsrslsrsl
 w:
 b(b()r)sb(b(b(b(b(b(wrrb())r))r)))srb(b(b()wrrb()))b()
最後にwを消すのを忘れずに．このコードだとこんな感じがひとまずいい感じ．
 a:srsl
 b(X):ssXaaaa
 b(b()r)sb(b(b(b(b(b(rrb())r))r)))srb(b(b()rrb()))b()
-違う方針に行く前に一度作った答えもちゃんと見直す
方針がどれくらい思いついているかにもよります．
トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS