Hatena::ブログ(Diary)

HOJメモ

2011-10-23

第2回HOJコンテスト結果

| 23:16

http://karu.ninja-web.net/hoj/contest2.html
優勝しました!思考過程とコードを公開します。


0801[HOJ_contest 2-1 small octagon] 12B

a:ssrslsrssa
a

流石に一瞬で解けます。壁に接してるので初期位置は気にしなくても大丈夫。

0802[HOJ_contest 2-2 2-2] 23B
(初期位置を気にしなければ)8歩ごとに曲がってるのでとりあえずなぞる。

a:ssssssss
b:aralallararalalallarara
rbb

重複部分を文字で置く。

a:ssssssss
b:arclc
c:alallarara
rbb

とりあえず2倍関数だろー

a:f(f(ss))
c:f(al)lf(ar)a
f(X):XX
rf(arclc)

f(X):rXXにしたら更新できる気がしてきたのでちょっと変形。

a:f(ssss)
c:alarrararal
f(X):XX
f(rarcc)

適用

a:f(ssss)
f(X):rXX
lf(af(laf(ra)aal))


0803[HOJ_contest 2-3 uzumaki squares] 12B
ぱっと見これですよね。

a(X):XXXlXlXlXa(sX)
a()

XとlXが3回ずつ繰り返されてるのでそこを2回に分けて実行する。

a(X,Y):XXXa(Ys,X)
a(l,)


0804[HOJ_contest 2-4 Tiling] 25B
最初に考えた経路はこちら。(露骨に1B縮むのに気づいていない。)

a:sss
c(X):XX
c(c(c(c(c(aralar)c(araa)aar))r))

経路変更してみたのがこちら。

a:sss
f(X):XX
f(f(f(f(af(ralarar)aaar))r))

どう見てもf(X):XrX系ですね。

a:sss
f(X):XrX
f(f(f(f(arf(alf(a)r)aaa))r))


0805[HOJ_contest 2-5 s or rs] 16B

a(X,Y):XXXXa(YXXYl,sY)
a(,)

一瞬で解けたので解説のしようがない。

0806[HOJ_contest 2-6 twisted square] 20B
最初に書いたコードは恥ずかしいので封印して、
内側を回収しながら回る感じの経路です。

a(X):XXXXa(cclsrX)
b:lssl
c:bbs
a(l)

相当悩んだけど意外とあっさりした解でした。

a(X):XXXXa(sbsbbbsX)
b:sl
a(l)


0807[HOJ_contest 2-7 1.2.3.4.5.6] 19B
(多分)今回のボス。まず経路がわかりにくいですね。
左右にn歩伸ばしてその先端からさらに左右にn+1歩伸ばして…みたいな感じです。
再帰は「大で小を挟む」なので今回は数値で書かなければならないわけです。
色々試行錯誤して解いた感じなので思考過程とかはないです。

a(X,Y):b(Xra(sX,Y-1)rX)
b(X):XX
a(,7)


0808[HOJ_contest 2-8 Sticks] 25B

a(X):sa(X-1)
b(X,Y):Xla(24)lb(XYla(15)lla(15)l,sY)
lb(,)

まあこうなるよねって感じのコード。最初のlが露骨に無駄なので

a(X):sa(X-1)
b(X,Y):lXla(24)b(XYla(15)lla(15)l,sY)
b(,)

a(X)に方向転換も含めちゃいましょう。

a(X):ra(X-1)s
b(X,Y):lXa(27)b(XYa(15)a(18)l,sY)
b(,)

実際は色々悩んでましたがこうしてみるとごく普通の圧縮ですね。

0809[HOJ_contest 2-9 Final Stage]
最後だけど経路が見えれば難しくない。

a(X):XX
b(X,Y):a(a(a(a(Xl))l))b(YX,slssrYrssls)
b(,)

a(X):XlXで短縮。

a(X):XlX
b(X,Y):a(a(a(a(X))l))b(YX,a(s)srYrsa(s))
b(,)