第4回HOJコンテスト感想 第6回HOJコンテスト B問題 想定解など


1317[Contest 6B-1 6th Contest!!]
ぐるっと回ればOK。
  • [16B]a(X):XXX, a(a(a(a(a(s)))l))

  • a(X):XXXlXXXla(Xss) a(r)
  • [12B]a(X):XXX, a(a(a(a(a(s)))l))

  • [11B]a(T):sa(T-1)la(25), a(1)

  • よく見ると8B形なのです。
  • [8B]a(X):Xa(sXr), a()

  • UZUじゃないけど外周を全部回収する形に収束しますね。
    ちなみに壁を使えなくしたバージョンをA問題にしました。
    1318[Contest 6B-2 umbrella]
    規則は分かりやすいでしょうか。短縮技術で差がつくかもしれない問題。
  • [18B]
    a(X):XrXrXXrXrXa(ssX)
    ra()

  • [16B]
    a(X):XXXlXXXla(Xss)
    a(r)

  • 2倍関数を定義してもかえってバイト数がかさみます。
  • [17B]
    w(X):XX
    a(X):w(XXXl)a(Xss)
    a(r)

  • こういうときは多変数の利用で縮みます。重要テク。
  • [15B]
    a(X,Y):YYa(Xss,XXXl)
    a(r,)


  • 1319[Contest 6B-3 Windmill 3]
    HOJで流行りの?Windmillで画像検索したら意外とまっすぐだったという。
    規則は簡単でどう縮めるか。
  • [23B]
    a:srsl
    b:aaa
    c:blbbaal
    d:ccld
    d

  • 2倍関数を使ってみる。
  • [22B]
    w(X):XX
    a:srsl
    w(w(w(aaalw(w(aa))l)l))

  • [22B]
    w(X):XX
    a:rsls
    w(w(w(aw(aa)w(aaar))r))

  • 2倍関数とsrslを両立する怪しい手法で実は結構縮む。
  • [19B]
    w(X):XsrslX
    w(w(lw(lw(w())lw(w(w())))))

  • コンテスト中に21Bが出ていたけどそれは何だろう。
    1320[Contest 6B-4 four points]
    スカスカで経路は色々ありそう。解答例:
  • [13B]
    a(X):XXa(rslssX)
    a(r)

  • [15B]
    a(X):XXXX
    a(a(a(a(a(s))rr)l))

  • [16B]
    a(X):XXXa(rslXlssr)
    a(r)


  • 1321[Contest 6B-5 Squares]
    4倍関数の練習のつもり。用意していた想定解はこれ。
  • [18B]
    a(X):XXXXr
    a(a(a(ssa(a(ssr))l)))

  • 特に他の解答例は用意していませんでしたw
    コンテスト中は22Bや24Bが多かったらしいが、どういう感じだったのだろう。
    1322[Contest 6B-6 Asterisk]
    規則は簡単ですね。どう書くか。再帰で増やしても良いですが、
    「3つについて同じことをする」というのを上手く裁くために
    6倍関数などで直接増やした方が短く書けると思います。 同じ形の操作をss,srsls,slsrsについて行うので、上手く関数を定義して
    「a(ss)la(srsls)a(slsrs)」のようなコードを目指すと良さそうですね。
  • [34B]
    a(X):XXXXXX
    b(X):a(a(a(X)ll)ll)
    b(ss)lb(slsrs)b(srsls)

  • 対辺の処理はいくつか方法があります。対辺は回収せず最後に点対称でさばく:
  • [33B]
    a(X):XXXXXX
    b(X):a(a(X)ll)
    a(b(ss)lb(slsrs)b(srsls)l)

  • 6倍関数に方向転換を混ぜておく:
  • [32B]
    a(X):XXXXXXll
    b(X):a(a(a(X)))
    b(ss)lb(slsrs)b(srsls)

  • さて、意外と見落としやすいですが、b(ss), b(slsrs), b(srsls)が全てb(s***s)の形であることから
    さらに次のような短縮をすることができます。
  • [28B]
    a(X):XXXXXXll
    b(X):a(a(a(sXs)))
    b()lb(lsr)b(rsl)

  • 結構短くなるもんですね。
    1323[Contest 6B-7 Ou]
    A問題と合わせて凹凸です。経路から悩ましいですね。
    2つ経路を紹介しておきましょう。まずは、対称に補ってから、回収手順を工夫する
    イメージのもの。正方形から正方形を繰り抜いた形を、上手く回収。長さ6の棒を連打。
  • [18B]
    a(X):XXXXXX
    a(ra(a(sa(ra(s)r))))

  • ちなみにこの「正方形から正方形を繰り抜いた形」にはマニアックなテクニックがあります。
  • [15B]
    a(T):sa(T-73)sssra(T+164)
    a(1)

  • 「(6,6,6,7)を18セット+6」という73個周期の数列を実現しています。
    詳しい原理はここに書くと長くなるので解説記事を参考にしてください。
    通称12B定跡とか言われている構文です。実は数値が255を超えても良ければ
  • [数値が足りない12B]
    a(T):sa(T-73)ra(T+383)
    a(1)

  • として12Bが実現できるのですが、これだと数値がオーバーするため、sssrと3つ水増しして
    必要な数値を減らしています。ちなみにこれは想定解じゃなくてコンテスト中に気付きましたw

    次にもう1つの経路です。内側から1層ずつ作っていくとa(sX)な再帰に乗るというもので、
    作問当初はこれが想定していた経路でした。
  • [26B]
    a(X):XlXllXrXXrXllXlXrsla(sX)
    ra()

  • これを縮めて24Bくらいにはなりそうですが、あんまり考えていません。
    こういう感じの経路でも微調整で大きく縮む余地はありそう…。
    1324[Contest 6B-8 Tournament]
    「適切に移動して、古いパターンをつけ加えたものを新しいパターンとする」。
    フラクタルだとかよく言われる種類の問題です。
    縦の長さは4で固定。横の長さが「0,1,3,7」となっていますね。
    「0,1,3,7」は「XXs」で再帰すれば作ることができます。

    実装を考えましょう。基本的な作り方は、例えば再帰の最後の段階は
    「4降りて横に7進み、(3のときのパターン)をくっつける。さらに
    左に14進み(3のときのパターン)をくっつける。もとの位置に戻る」
    という具合です。育てる長さをX、パターン全体をYに覚えさせて次のような実装になります:
  • [31B]
    a(X,Y):Ya(XXs,llsssslXlYlXXrYrXlssss)
    a(,)

  • フラクタルと呼ばれる問題は、2変数の再帰を使えることが大前提となり、
    難しいと考えられがちですが、ほぼワンパターンの考え方で実装できるので、
    是非身に付きて他の過去問などにも活かしてみてください(^^)
    あとは短縮。2回出てくるlssssを文字でおくことで2Bの短縮になりますね。
  • [29B]
    b:lssss
    a(X,Y):Ya(XXs,lblXlYlXXrYrXb)
    a(,)


  • 1325[Contest 6B-9 Tournament]
    よくわからず
  • [26B]
    a(T):sa(T-1)
    b(X,T):XXb(a(T)ra(7-T)lX,T+1)
    b(rr,1)

  • というのを想定解(笑)としていたのですが、Solve者にことごとく抜かれているという
    状況だったので、コンテスト中に考え直しました。
  • [24B]
    a(T):sa(T-1)
    b(T):a(T)ra(7-T)lb(T-1)
    b(6)llb(6)

  • あれ普通に24Bだった。
  • [23B]
    a(T):sa(T-1)
    b(T):a(T)ra(7-T)lb(T-1)l
    b(6)b(6)

  • もう1B縮む。b(6)の右側にlをつけています。これにより、展開した結果として右側に
    lが6個余分についてくれて、結果として180度方向転換が実現されます。

    inserted by FC2 system