第2回HOJコンテスト感想・解説
今回は作問者としての参加でした．

作問者として気をつけたこと

割とこちらの思惑はちゃんと機能した気がする…ほっ．
コンテスト直前期はかなり，これでいいのかなぁ〜？？？とか考えまくっていました．

一番危なかったの：実は2-1は，最初すこし違うマップだったのだけど，乱歩チェック忘れていて，
コンテスト開始30分前くらいにチェックしたら変態解単独Bestがあったので差し替えたんですよｗｗ
予備を用意しておいて良かった．乱歩チェックしたと思っていたんだけど再チェックして良かった．
現状の2-1にも乱歩的なBest解はあるのだけど単独Bestにはならないので許容．
全部準備おわったの19:54とかだったよ，めっちゃあぶないｗｗ
問題のストックがもうちょっと柔軟に番号変えとか再編集とか出来るようになると楽になるかも．

なお「乱歩対策」であって，「ソルバー対策」は意図していません．
それすると14B以下Bestのとか出題出来ないし．0805の16Bだって，単純に16Bだと探索厳しくても
a(X,Y):XXXXa(**,**), a(**,**)に限定すれば簡単に探索出来ちゃいますからねぇ．
プログラム動かして解けちゃう問題がコンテストに混ざるのはある程度仕方ないと思った．

mas解のバイト数
0801[HOJ_contest 2-1 small octagon]
どこで区切っても同じことなんですが，適切な位置からとあるパターンを4回繰り返せばよいです．例として

  • [16B]a:ssrslsrssa, sssra

    • で16B．しかし，無限回繰り返しちゃうと，実は自動的に初期位置があってしまい

  • [12B]a:ssrslsrssa, a

    • で12B．なぜ初期位置が違うのに同じ経路に収束するかはちょっと考えて原理を理解しておいてください．
    簡単な説明：壁にぶつかるときに横（縦）の座標が強制的にそろう．
    4方の壁にぶつかる経路では，パターンを作ってとにかく何回も繰り返せばよい．頻出の重要な考え方です．
    なお，経路選択の幅を活かしsrssrsを単位にする方法もありそうですが，Bestにはつながらないようでした．

  • [14B]a:srssrsl, c:alac, c

    • ちなみに乱歩的な解の例：

  • [12B]a(X):Xa(srsXXX), a(r)
    • 0802[HOJ_contest 2-2 2-2]
    長文風の問題．ですが，意外と短くなっちゃいますね．
    まず大事なのが対称性．片方の2を回収すれば，点対称同手順でもう片方も回収できます．
    移動距離も4や8が多く，2倍関数が有効に使えます．
    実は「2の回収」にも真ん中で対称性があり，そこも2倍関数でOKですね．
    対称性に注目して適当に書いてみると：

  • [33B]w(X):XX, c:w(ss), rw(ccw(clcclccrrccrccrc)rrcc)

    • もちろんこれは色々無駄があって，

  • [29B]w(X):XX, c:w(ss), rw(ccw(w(clc)crrcw(crc))rrcc)

    • くらいにはなります．この方針でもうちょっと縮めることも可能ですが，
    実はもっと良い方法があります．それは(2-1と同様？）壁を利用するものです．
    壁を利用すると，実は「4歩の動き」は不要で「8歩の動き」だけを単位として
    全体が作れてしまいます．その方針できちんと詰めると次の23B解に到達します：

  • [23B]w(X):XX, c:w(w(ss)), w(rcw(cw(lc)rw(rc)r)r)

    • なお，2倍関数の変種でも23Bが可能で，

  • [23B]w(X):XXr, c:w(w(ss)l)l, w(rcw(cw(lc)w(rc)))

    • ここまでくると22B欲が出てくる（タイトル的にも）のですが，残念ながら22B解は見つけていません．
    0803[HOJ_contest 2-3 uzumaki squares]
    まずは初心者っぽく書いてみるとこんな感じ：

  • [17B]a(X):XXXlXlXlXa(sX), ra(s)

    • もうちょっと慣れた人なら，次の15B解にはすぐ到達できるかと．

  • [15B]a(X):XXXlXlXlXa(sX), a()

    • なお，a(l)とかで考えると

  • [16B]a(X):XrXrXXXXra(sX), a(l)

    • になったりしそうです．このように変数に方向転換を含めた方が短くなる問題もありますが，
    今回はかえって損ですね．一般的には，まずは何も方向転換を入れずに書いてみてから
    慎重に変数変換すると間違えにくいのではと思います．
    変数変換の講で少し近い内容を解説しています．

    さて，15B解が作れて終わり…かというと，さらに12Bまで縮めることができます！
    15B解が書けると，次のものを3回ずつ繰り返せばいいことに気付くでしょう：
  • (空文字列), l, s, ls, ss, lss, sss, lsss, …
    • そこで，Xの部分に次々とこれらが呼び出されるように再帰を組みます．
    2回で後ろ側にs1つ分育つように…これには多変数を利用した上手い方法があります．

  • [12B]a(X,Y):XXXa(Ys,X), a(l,)

    • 2種のものが，それぞれ2回にs1つ分成長しながら，交互に呼び出されます．
    大事な構文なのでよく原理を理解して，常識化しておくべし？
    成長速度の調整2の講で，ちょっと違った切り口からですが
    この構文を解説しているので参考にしてください．
    0804[HOJ_contest 2-4 Tiling]
    適当に綺麗そうな図で作問してみた系．
    4分の1の領域を作って4倍するのが普通だと思います．
    さらに適切に経路を組めば，それぞれの4分の1の領域も，パターンの4倍として
    作成することが出来て，実はかなり小さいパーツを（向きを変えながら）16倍すると出来るという問題．
    よくあるパターンですね．このような問題では2倍関数やその変種が役に立ちます．
    （4倍関数を用意した方も居たっぽいですが，4倍関数は4倍を3回以上しない限り，
    2倍関数の劣化版と考えてください．）
    「1つのパーツの16倍」と認識出来ればClearには間に合うと思います．

    割と何も考えずに作ってみると32Bでした．
  • [32B]w(X):XX, p:sss, w(w(w(w(prplprpllplprprpppr))r))

    • これだと間に合っていませんが，明らかに2倍関数がまだ使えて

  • [27B]w(X):XX, p:sss, w(w(w(w(w(prpl)w(lp)w(rp)ppr))r))

    • 割と素直に書いただけなのに，これだけでもかなり上位になっちゃいます．
    少し経路の長さを犠牲にしつつも2倍関数が活きるコードにしてみてmasが一番最初に解いたときの26B：

  • [26B]w(X):XX, p:sss, w(w(w(w(w(w(prpl)prr)w(pp)r))r))

    • 2倍関数を使って，中央への行き帰りを楽に書いていますね．でも
    経路が長くなっているのであまり上手いとは言えないかも．もう少し考えると
    経路を伸ばさなくても2倍関数で中央を回収できる気がした．

  • [25B]w(X):XX, p:sss, w(X):XX, p:sss, w(w(w(w(pw(rplw(pr))pppr))r))

    • これでいま見つかっているBest．よく見たら上述の32Bをちゃんと2倍関数で圧縮しているだけだったｗ
    なお2倍関数の変種を使っても同様の25Bが実現しました．

  • [25B]w(X):XrX, p:sss, w(w(w(w(pw(rplw(p))rppp))r))
    • 0805[HOJ_contest 2-5 s or rs]
    まず，規則についてですが，タイトルが示唆しています．
    さて，先端まで10歩．4+3+2+1です．4-(真っすぐ or 右)-3-(真っすぐ or 右)-…
    として到達できる場所全体が白マスになっています．
    それを4倍している…というのもありますが．
    タイトルの意味を解読することで圧倒的に解きやすくなる問題も結構多いので頭に入れておきましょう．
    先端に注目すると予想はしやすいので本当はノーヒントでも良かったのだけど．

    さて，この規則が分かってしまえば，慣れている人ならすぐに実装できてしまいます．
    まず選択する手法は，2変数の再帰．1つはsXで「s,ss,sss,ssss」を育てます．
    もう1つ(Y)は「正面に4歩，以下正面または右のみに3,2,1の順」というものですね．
    Yの方は，「回収したあとトータルで方向をどれだけ変えるか」という情報が維持されるよう
    注意しながら規則を考えましょう．次のようなコードが考えられます：

    Yに方向転換を含めない場合
  • [22B]a(X,Y):YrYrYrYa(sX,XYrYrXrr), a(,)

    • Yに方向転換rを含める場合（回収したあとrを向く）
  • [17B]a(X,Y):YYYYa(sX,XYYXl), a(,r)

    • Yに方向転換rrを含める場合（回収したあとrrを向く）
  • [22B]a(X,Y):YlYlYlYa(sX,XYlYlX), a(,rr)

    • Yに方向転換lを含める場合（回収したあとlを向く）
  • [19B]a(X,Y):YYYYa(sX,XrYYlXr), a(,l)

    • このように，何をYにした場合でも瞬時にコードを書けるようにしておくと良いです．
    今回は，4方向にYを実行することを要求されるため，Yにlやrを含めておくと短くなります．
    ここで紹介した17Bコードが，masが最初に作った解です．しかし実はさらに減って

  • [16B]a(X,Y):YYYYa(sX,XYYXl), a(,)

    • 初期向きのrが不要でした．これは珍しい節約で，原理もちょっと複雑です．
    雑な解説をすると，YYlという規則だとYの初期向きによらずrに収束することと関係します．
    その過程では必ずしもrを向かないですが，そこはXが長さ0なおかげでなぜかセーフという危うい事情ｗ
    ちなみにYに方向転換lを含める方針だと

  • [17B]a(X,Y):YYYYa(sX,XYYlX), a(r,)

    • ここまで縮みます．他に，上記の解でいう「YY」にあたる部分がYになるように
    再帰を組んでくれた人も居たようです（17Bが可能）．問題によってはそっちの方が
    1B有利だったりするので難しいですね．理論的に説明も出来るけど色々試すのが基本．
    0806[HOJ_contest 2-6 twisted square]
    まず考えるだろうコード

  • a(X):XXXXa(sslsrX), a(l)
    • では隙間がたくさん出来るのでそれをどう埋めるかという問題．
    色んなアプローチがありそうで，どんな解き方をしてくるのか気になっていた問題です．

    方法1：基本的には上記のコードと同経路を歩くのだが，その際になるべく
    内側を巻き込みながら歩くことにする．安直に書いてみると

  • [24B]p:lssl, q:pps, a(X):XXXXa(qqlqrX), a(l)

    • この方針の解は色々あったようで，きっちり頑張ると20Bとかになるようです．紹介．

  • [23B]a(X):b(X)a(b(ssl)lsrssX), b(X):XXXX, a(l)

  • [20B]a(X):XXXXa(sbsbbbsX), b:sl, a(l)

    • 同様の方針で直接作っている解もありました．
    一見再帰だけど直接作っちゃった方が短い問題はしばしばあり，
    結構多くの人に見逃されやすい方針になっているようです．

  • [23B]b:sslsr, a(X):XXXXXXl, a(a(a(la(b))rb))

    • 方法2：全く違う方向性の書き方．mas解はこっちでした．
    sslsrを一気に育てるからダメなんであって，ゆっくり育てることで隙間をなくすことができます．
    成長速度の調整をして3回でsslsr育つように．構文は成長速度の調整2参照．
    直観的に一番分かりやすいのが

  • [21B]a(X,Y,Z):XXXXa(sY,sZ,lsrX), a(l,l,l)

    • もう一工夫して方向転換をつけるタイミングを調整するともう1B縮んで

  • [20B]a(X,Y,Z):XXXXa(sY,slZ,srX), a(l,l,)

    • どちらも実際にやってくれていた人が居たようです．

    さらに

  • a(X):XXXXa(Xrssls), a(l)

    • を元に同じことをすると，

  • [19B]a(X,Y,Z):XXXXa(Yls,Zs,Xrs), a(l,,)

    • となってこれがmas解でした．なぜ後ろからつける方が上手くいくのかの事情は
    あまり上手い説明が思いつきません．自分も色々やりながら見つかった感じでした．
    0807[HOJ_contest 2-7 1.2.3.4.5.6]
    まずは規則．1歩-曲がる-2歩-曲がる-…として到達可能な点全体が白いです．
    実は6,5,4,3,2,1の順だと比較的ありふれた問題で，過去問にもあります．
    手法は2-5と似ていますね．知らない人は探してみてもいいかも？

    さて，今回は，「1歩-（2歩以上）-1歩で戻る」という順序なので，再帰では上手く書けません．
    いや，無理矢理書くこともできますが

  • [45B]a(X,P,Q,R,S,T,U):XXa(PrXXrP,Q,R,S,T,U,), ra(,ssssss,sssss,ssss,sss,ss,s)

    • 何となく無駄に努力をしてみても

  • [37B]c:sss, a(X,P,Q,R,S,T,U):XXa(PrXXrP,sQ,R,S,T,U,), ra(,cc,cs,c,ss,s,)

    • 30Bを切れる気配はあまりないですねｗｗ

    さてさて，このように再帰の逆順っぽいもの，標語的には小で大を挟むものは
    数値引数で綺麗に実装することができます．

  • [23B]a(X,T):Xra(sX,T-1)rXXra(sX,T-1)rX, a(,7)

    • 2倍関数を使って

  • [19B]w(X):XX, a(X,T):w(Xra(sX,T-1)rX), a(,7)

    • Clear出来てしまえばバイト数にはあまり差がつかなさそうな問題で
    コンテストに出すかは迷ったのですが，手法への理解が試せるし
    運や思いつきでなくちゃんと実力で解ける問題なのと，綺麗であまり見たことのない
    種類の問題・解法だったので出題してみました．
    0808[HOJ_contest 2-8 Sticks]
    想定は，1+2+3+4+5+…と育てるところが長さ15を作るのと両立できて，
    数値引数の再利用を書いてみる→色々再利用できて綺麗に解けるよ！
    という想定でした．

  • [23B]a(X,Y,T):rYlXlYra(sX,Y,T-1), a(,a(,a(,,6),8),3)

    • 実際には15=1+2+3+4+5を使っていたのは聞いた範囲ではmas解だけで，
    ちょっと失敗した感じの出題でした．実装技術で競うのは好きだけど
    こういう気付きの差で競うのはそこまで好きではないので．
    まぁでも素直にa(T):sa(T-1)系で作るとしてもそれなりには
    実力でバイト数がバラけたんじゃないかな？という感じで安心．
    後半に置いてますがClear難易度低め，もうちょっと別解とか検証して
    出題した方が良かったですね．唯一ちょっと後悔な出題です．

    まぁ気にせずいくつか解を紹介．基本的には15歩は適当に作って，
    1,2,3,4,5,6は再帰で付け加えて行けばOKです．育てすぎても問題ないので
    位置合わせとかも特に考えず，とにかく作って実行していれば大丈夫．
    15歩作るときの関数a(T):sa(T-1)に上手く方向転換を混ぜておくと
    圧縮が利きやすく，これを上手く使えた人がBest付近に来られたようです．

    いま適当につくった25B．
  • [25B]a(T):sa(T-1)r, c(X,Y):Yrrc(sX,Ya(15)Xla(15)l), c(,)

    • コンテスト中に実際にあった25Bたち：
  • [25B]a(X):ra(X-1)s, b(X,Y):lXa(27)b(XYa(15)a(18)l,sY). b(,)
  • [25B]a(A):ra(A-1)s, b(B,C):Bb(Bla(15)lCa(15),sC), b(ll,)

    • 3つめは1つめと一緒だね．
    0809[HOJ_contest 2-9 Final Stage]
    裏話をすると，タイトルが思いつかなかったので最後に置いただけで最難とは思っていませんｗｗ
    作るのが苦手な経路ゲーを頑張ってつくってみた．とがっているところとかに注目して経路を見つけてね．
    規則探しでは，どうせそんなに材料は多くないのでは！？という思い込みもポイントかも？
    自分は経路見つけるの苦手な人なのであまりちゃんと解説できませんが．

    規則が見つかれば制限バイト数には間に合うはず．例によって2倍関数が使えて，例えば

  • [29B]w(X):XX, a(X,Y):w(w(w(w(Yl))l))a(slssrXrssls,XY), a(,)

    • Best解は，特殊な2倍関数を用いて

  • [27B]w(X):XlX, a(X,Y):w(w(w(w(Y))r))a(w(s)srXrsw(s),XY), a(,)

    • なお直接作っても良いです．再帰で作る選択肢の方が有名ですが，直接作った方が有利なこともあるので
    次の解も選択肢に挙げられるようになっておくとどこかで役に立つんじゃないかと．

  • [29B]w(X):XX, a(X):slssrXrssls, w(w(w(w(a(a(a()))a(a())a()l))l))

  • [27B]w(X):XlX, a(X):w(s)srXrsw(s), w(w(w(w(a(a(a()))a(a())a()))l))

    • コンテスト参加ありがとうございました＋お疲れ様でした♪
    戻る inserted by FC2 system