HOJ講座

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

§0 経験則 いくつか長文を解いていて得た経験則

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

例えば

a:10文字
ssrsrrsssaa...

のような状況の時は,二倍関数や,f(X):sXXとかf(X):ssXXとかf(X):rsssXXとかを作るとすごく有用だったりします

たとえば

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
Last-modified: 2015-04-23 (木) 07:28:35 (1216d)