第1回HOJコンテスト感想
初のコンテスト！

  • どれも面白い問題で楽しかったです♪
  • 自分で探索しておいて言うのもあれだけど乱歩が最適な問題が3個というのがちょっと残念．
    でもコンテストということで手加減は一切しないという意味でもちゃんと探索しました．
    経路ゲー要素を意図しているのだろうけどもうちょっと積極的に乱歩対策しても良かったかもね．
  • 時間はまぁ足りました．
  • 基本的にはちゃんと全問詰められたけど，0746がダメだったのが個人的反省点．
    • mas解のバイト数
    0743[Welcome to my contest!]
    とりあえず小さめの乱歩あるだろと思い真っ先に探索して10B．

  • [10B]a(X):Xa(XXrs), a(l)

    • 流石に非再帰9Bは無理そうなのでこれでOK．
    0744[Ten thousand]
    流石に5倍関数を適切に3つ積めば終わりそう．

  • [13B]w(X):XXXXX, w(lw(w(s)r))

    • 特に迷う場所なかったです．
    0745[Growing square]
    まず最初に書いた16B解：

  • [16B]a(X):XXXXsrsla(sX), a(sr)

    • もうちょっと真面目に経路構築してみる．曲がる回数を少なくね(^^)
    とりあえず正方形っぽく描いて1周期後にはsrsの位置に居るように．
    ちゃんと長さを測ると再帰のn段階目は[n+1]r[n+1]r[n+1]r[n]rs．4回曲がるようにするとこんな感じ．
    ちなみに最初をn=0と数えています．Xに方向転換を含めて15B解が2通り．

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

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

    • 念のため14Bを1変数灰色マス0回で検索かけたけどなさそうなのでこれでOK．
    0746[Halo]
    ダメでしたｗｗｗコンテストで提出した24B解：
  • [24B]w(X):XrX, a(X):w(w(w(Xw(X))w(w(X)XlXr)))a(sX), a()

    • sXで育てる，最後に4倍させるとかは思いついたけどパーツが4倍関数に見えず死亡．
    卍は一瞬考えたけど，なぜか「(中央に入って4つつけて戻る)の4倍」という 経路を考えてしまう．あまりに基本な経路選択を見落とすとは…
    最初27〜30Bばかりで，コンテスト中の問題では一番Solveに苦労しました．
    早い段階で卍を諦めてしまい，時間内にその発想に立ち返れず．
    0747[8-way]
    最初に作った20B解．

  • [20B]w(X):XrX, a(X):w(w(w(X)w(llX)))a(ssX), a()

    • その後，トップが19Bだったのを見て，19Bに気付く．自明だったｗ

  • [19B]w(X):XrX, a(X):w(w(w(X)w(llX)))a(sX), a()

    • 灰色マス密度が少ないので色々経路選択ありそうだけどなかなか19B切れない．
    そもそも灰色マス密度とTARGETの個数的に乱歩解あるんじゃ？と思い14Bで乱歩探索してみたら出来た：

  • [14B]a(X,Y):Xa(Y,ssYYlX), a(l,)

    • 比較的序盤のうちから探索開始して裏でプログラム動かしていました．2変数14バイト1万ステップの探索だと
    a(X,Y):Xa(**,**), a(**,**)の型がコンテストに何とか探索できるくらいいや全部はちょっと厳しいかも．
    探索開始位置からそれほど深くないところに解が見つかって助かった．
    0748[R4]
    経路が見えるまでに時間がかかった．
    最初外側に行っちゃダメっぽく見えてたんですよね．外側の灰色マスがダミー
    最初に作った23B解：

  • [23B]a(X,T):Xla(ssX,T-1)rrXl, c:a(,7)rssc, c

    • rrなんて不要なはずの経路なのでこの書き方はダメだろ〜．
    左側はパターン同士の境目がl,右側はパターン同士の境目がr，左側と右側の境目がr．
    これに注意してまともに書き換えて21B：

  • [21B]a(X,T):lXa(ssX,T-1)rX, c:a(,7)ssrc, c

    • 初期向きが合ってないけど，4壁に接する経路で無限に繰り返すので問題ない．
    なお，最初からa(X):a(sX),a(l)のようなコードでXに方向転換含めてしまうと
    この辺の最善手が見えにくいので，よほど含めるべき方向転換が明らかな場合を除いて
    最初は方向転換入れずに考え始めるといいんじゃないかと思います〜．

    次に検討すべきは，関数の再利用．ssの部分はもっとたくさんsしてもいいことに注目して
    まずは「lX」部分を利用してたくさん繰り返す19Bを発見．

  • [19B]a(X,T):lXa(Xss,T-1)rX, a(rra(,7),10)

    • なんか向きの相性が悪い気がしたけど，「rX」部分で繰り返せばいいだけだった．17B．
  • [17B]a(X,T):lXa(Xss,T-1)rX, a(a(,7),10)

    • これが綺麗なコードで多分この方針の最善手．しかし結局理論値は乱歩でした．
  • [11B]a(X):Xa(lXsXss), a()

    • 灰色マス多そうで偶数歩単位で動く限りほとんど死なないので
    10Bは5万ステップずつ動かしたけどHitしなかったので多分11Bで理論値．
    0749[4STEP]
    まずは落ち着いて経路構築．経路が見えるまでに時間がかかったけど，
    再帰で増やしていくことを考えて行くと，1,2,3,4,…という正方形に注目できるでしょう．
    この順に正方形を回収すること，そして初期位置がパターンの境目に相当するように
    考えることで，時計回りの経路で，「1を回収ながら90度移動」「2を回収ながら90度移動」
    というのが再帰のパターンとして考えられました．
    こういうのは「1,2,3,4,…」よりも「0,1,2,3,…」の方が短縮になることが多いのだけど，
    初期位置とマップの関係を見る限り「1,2,3,4,…」とするしかなさそうで，とりあえずここで経路を固定．
    最初に書いたコード：

  • a(X):sXrssssssssrXrXrssssssssrXsa(sX), a(s)

    • 動作チェックで正しく回収できることを把握．ここで「XrssssssssrX」が2回あるので
    2倍関数を使う，または「XrssssssssrXがXになるようにする」の2択が発生．
    2倍関数の方向でとりあえず作った23B：

  • [23B]w(X):XX, a(X):sw(Xw(w(ss))rX)lsa(sX), a(sr)

    • これであっさりClearは出来るかと思っていたけど案外ノルマ厳しめだったｗ
    少し考えたけど縮まないので，もう1つの方針に立ち返ってみる．安直にやると24B．

  • [24B]a(X):sXrXsa(sXs), a(srssssssssrs)

    • ここから2B縮めればいいだけなので，何とかなりそう？
    いかにも「u(X):sXs」という関数が有効そうで，関数定義に+5B，使える回数が7回で-7B．
    22Bになるやん！というわけで書いて終わり．

  • [22B]u(X):sXs, a(X):u(XrX)a(u(X)), a(u(ru()u()u()u()r))

    • 他にもやりようありそう．経路選択も短縮も少しずつ非自明でこういう問題は結構好き．
    0750[Big rice field]
    一目，Clear出来ない心配はなさそうなので楽な気持ちで．
    安直には，パーツを作って16倍に増やせば良さそう．素直に書いて31B．

  • [31B]w(X):XXXXr, a(X,Y,T):Ya(sX,lw(XllX)s,T-1)Y, w(w(sa(,,5)r))

    • コンテスト序盤に31B解を投稿して，落ち着いたら戻って短縮考えようと思っていたのだけど，
    最後1時間くらい戦ったけど31Bから縮まりませんでした．同方法では短縮間違えてなさそう．
    別方法を検討．w(X):XrXlslXrXと定義してsw(w(s))sとするとそれっぽいパーツを
    割と小さいバイト数で作れることが分かり，この方針で適当に作った32B．

  • [32B]w(X):XrXlslXrX, a:sw(w(s))sr, b:arara, c:bbbbrc, c

    • いかにも何とかなりそうだけど，関数が再利用出来ず苦戦．XYXとかXrXとかも考えたけど
    いまひとつでした．何かありそうだけどタイムアップ．良く考えたら30Bには出来るべきだったかも：

  • [30B]q(X):XrX, w(X):q(X)lslq(X), a:sw(w(s))srr, q(q(q(q(aaa))l))

    • snuke先生の想定解と大体同じだけど補助関数が違った．多分ちょっと変数変換するとうつりあう．
    着眼は良かったっぽいけどスコアに結び付けられず残念…だけどまぁこれは仕方ないな．
    3時間の立ち回り・反省としては0746が迷走してしまったことくらいかなー．
    あとは割と上手くこなせた1位だったと思う．関係者の皆様お疲れ様でした♪
    戻る inserted by FC2 system