第4回HOJコンテスト感想

  • 結果.1位でした〜♪今回は特にzephoriaさんが手ごわかったです.
    最後の方,黄緑を3つ残して悩んでいたのですが,眺めている問題すべてでzephさんが
    Bestだったので負けているイメージしかなかったけど競り勝っていたみたいですw

    結果→

  • 遅刻でした.19時50分くらいに帰る予定が電車が止まって詰んだ.50分遅刻.
    pasta先生も90分ほど遅刻でしたね.まぁ仕方ない.自分はあと50分あっても
    1B縮んだかどうかです.黄緑問題だったやつはすぐに思いつけなさそうな手法で負けてたし.
    Best化出来たやつをもう少し落ち着いてやってればもう1Bくらいは伸びてたかもね.でもその程度だろうなー.
    というわけでそれなりには実力を出し切れたコンテスト.

  • 今回は,些細な短縮にはこだわらず,とりあえず一通り(論外ではないByte数で)Solve.
    短縮は後回しにして,Bestになっているものについては,後で考えるつもりだったのを
    除いてほとんど触らないように心がけました.結果として最後にあわてたりが少なく
    コンテスト中の立ち振る舞いとしては上手くいった方だと思います.前回の反省を活かして.

  • ほぼどの問題もバイト数がばらける良い問題だったように思います.
  • 当たり前のように使っていた人もいたようだけど自分は知らなかった新テクに遭遇.
  • Div制は割と上手く機能したように思うので次回以降も採用かな〜?
  • byte制限が過剰に緩いのは賛否分かれそう.

  • コンテスト中のmas解のバイト数

    1124[Contest 4A-1 Magic square]
    見たまま書いて終了.実は別の規則を示唆していた問題だったんですねぇww

  • [8B]a:lsrsa, la


  • 1125[Contest 4A-2 Rice field2]
    流石に規則認識は簡単.太いので「逆向きにたどる」と重ねるか,太く進むかで迷う.
    とりあえずSolve優先ということでsrslを基準のパーツにして書いてみる.
    srsと2倍関数処理も関数定義に組み込んで最初に書いてみたのがこれ.

  • [20B]a(X,Y):XrXYYY, a(,a(,a(a(a(,ra(,a(s,)l))l,),)))

  • 後から見てもよくわからない感じになってしまったけどそういうもんですよねw
    pastaさんが18Bにしていたので粘る.色々やったのをとりあえず紹介.
    まずsrslを主人公にして別な感じに書いてみた.

  • [20B]a(X):XXXr, b(X):Xa(X), b(b(a(a(srsl)r)))

  • だいぶ見た目はすっきりしましたね.次にダイレクトに太くなぞってみた.

  • [19B]a(X,Y):XXXYYr,a(a(,a(,a(,a(a(sr,)s,))l)),)

  • 2倍関数がまどろっこしいので4倍にしちゃえ→pastaさんと同じ18B.

  • [18B]a(X,Y):XXXXYYYr,a(a(a(,a(,sr)s),),)

  • これでBestだったのでコンテスト中はここで一区切り.コンテスト終了後に少し
    考えたけど18Bが増えただけでまだ17Bは出来ていません.

  • [18B]a(X):XXXr, b:a(a(a(sr)s))l, a(blb)

  • [18B]a(X):XsrsX, a(a(ra(a(a()a(a(r)a()l)))))


  • 1126[4A-3 Aho modoki]
    とりあえずSolve優先ということで,それっぽいパーツでなぞってみた.

  • [51B]c:srsl, q:cccrrcccrcccrcccrcrccrcccrcccrccrcrcccrcccrq, q

  • とりあえず何回も出てくるcccrを1つにしてみる.

  • [32B]c:srsl, t:cccr, q:trtttcrccrttccrcrttq, q

  • これでBest付近まで行ったので,綺麗な再帰に乗せるとかよりもこういう雰囲気でいいのかなーと予想.
    数値を使って12B定跡の変形でsrslとrを並べるとかも考えたけどあの構文は180度まわるのが苦手でちょっと厳しそうw
    素直に自明な圧縮をほどこして28Bまで.まずはccrをまとめる.

  • [30B]c:srsl, u:ccr, t:cu, q:trtttcruttucrttq,

  • crの方がcより登場回数が多い上にc:srslという定義の形からして,c:srsに書きかえると縮む.

  • [28B]c:srs, u:clc, t:clu, q:trtttcuttucttq, q

  • これでも非Bestだったので暫く粘ったがダメでした.壁もないから繰り返しの始点変更できないし
    pXq型の関数で何かをまとめようにも個数が上手く合わなくて上手くいかず手詰まり.
    zephoriaさんのBest解は「pXqの関数でまとめようにも個数が合わない→捨てちゃえばいいじゃない!」
    という解でした.今まで「繰り返しの場合は,パターン境界できちんと区切りをつけないと!」と思っていたので
    盲点だった.この後に及んでまた新テクに出会い…やっぱりHOJすげぇなぁ〜〜.
    1127[Contest 4A-4 Oba-chans]
    見た瞬間XXrrだろと思い,さっと書いて1発OK.map見てからClearまで10秒とかじゃないかなw

  • [17B]a(X):XXll, a(a(a(a(slssr)a(s))))

  • slとsrはXとXllの関係だけど離れてるから無理だよね〜.綺麗に書けたしBestなのでこれでOK!
    と自信満々に立ち去った問題だったのですが実は16Bになるみたいです.
    1128[Contest 4A-5 Center piece]
    一目,これはやばい!全然わからん!苦手そう!と思ったけど何とかなりました.
    同じように深さ1で窪んでいるものの位置関係に注目.
    近くのものとペアにするとダメだけど遠くのものとペアにするとぴたっとはまりました!
    一番遠くの窪みまでの移動方法に注目すると見えやすいね.
    中央の窪みも怪しいと思っていたけどこれで説明がつく.とりあえず規則把握が
    合っているか確認するために実装してみる.考えやすくするため,
    変数には方向転換を含めない形で実装.

  • [30B]a(X,Y):YrYrYrYa(sX,srXlYlXXrYrXrsrr), a(,)

  • これでClearになったので短縮を考える.Yにどれかの方向転換を混ぜたい.
    Y成長の左端と右端を考えると,Yにllの方向転換を混ぜてみたくなった.実装.

  • [26B]a(X,Y):YYlYYa(sX,srXlYrXXrYlXrs), a(,)
  • 最初のXは長さ0だから初項のYには向き入れないでOK.
    2倍関数も役に立たなさそうだしこれでBestになったのでこれで提出.
    最後にSolveした問題でした.全問まともにSolve出来て上位入りは確信できた瞬間.
    1129[Contest 4A-6 Sharp 3]
    先端部に注目してまず規則の仮説を立てる.最初に作ったコード.

  • [31B]w(X):XX, a(X,Y):w(w(XYllYrYllYrXl))a(sX,srslY), a(,)

  • これでSolveして安心して短縮に進む…予定がちょっと回収できてない!!
    回収しそびれたところを自然な流れで回収したい…暫く考えていると,
    「4方向やればいいんじゃ」という発想に.書いてみる.

  • [28B]w(X):XX, a(X,Y):w(w(Xw(w(YllY)l)Xl))a(sX,srslY), a(,)

  • これでClear出来たのであとは自明な短縮を〜.と思ったけど,sXで育てているのは
    移動の役割しか持っていないので,中央に戻らないことにした方がパーツ減って良さそう.
    外側に出ながら…というのはたまにある規則認識.とりあえずXに方向転換混ぜずに書いてみる.

  • [25B]w(X):XX, a(X):w(w(w(w(XllXl))rX))sa(srslX), a()

  • Xにちゃんと方向転換を混ぜると2B縮みそうなので調整.

  • [23B]w(X):XX, a(X):w(w(w(w(XlX))X))sa(Xslsr), a(l)

  • 自明な短縮はもうなさそうで,単独Bestになったのでコンテスト中はここまで.
    実はこの規則認識だと,移動経路と棒を立てるのが重複していて無駄になっています.
    きちんとSharp状だけど最短距離で回収すると22Bが実現可能.
    次々規則認識を改善していかないといけないから,思いこんじゃうと難しいね.

  • [22B]w(X):XX, a(X):w(w(w(XlX)X))sa(lsrsX), a(l)


  • 1130[BARUSU!!w]
    Solve出来ない気はしなかったけど,あまり上手く書けず,
    上手い経路があるのかなぁとか色々と悩んだ問題.
    自然に境界をなぞってどさくさに紛れて右手を回収すればよい.
    再帰で作ると壁衝突で位置がずれちゃうので数値をつけた再帰の打ち切りで.
    すぐに28Bにはなったけどそこからあれこれ苦労した問題でした.
    以下コンテスト中に作った解のコピペ.

  • [28B]w(X):XX, b(X,T):rXlsb(sX,T-1)w(w(rs)XX), w(w(b(,5)rs))

  • [29B]a(X,Y,T):rXlsa(sX,YsX,T-1)YYrsa(,rsr,5), a(,rr,5)

  • [27B]a(X,Y,T):rXlsa(sX,srXXXr,T-1)rYYsa(,,5), a(,,5)

  • [27B]a(X,T):Xa(sX,T-1), c:ra(lsr,5)ra(,5)lsla(,5)rc, c

  • [27B]a(X,T):Xa(rslX,T-1), c:a(s,5)ra(,5)srra(,5)rrc, c

  • 最後の2つは22:57と22:58にsubmitしたもの.最後に提出した解のほんの隣くらいに
    25B解が落ちていたのですが,もう少し時間があれば出来たかというと微妙なところw
    1131[Contest 4A-8 Branches]
    よく分からないけど(移動先に同じ形がくっついてる)が2セット.
    向きが変わっているっぽい.全然分からないのでとりあえず最小単位のパーツを
    特定するため長さをはかってみる.長さ7…??0,1,3,7,15,…かな??
    と思って細部のパーツを調べるも,どうも1,3とかには見えない.そこでとりあえず試したテストコード.

  • [テストコード]w(X):XX, c:sssssss, cw(cllcl)c

  • ………あれ?何が起きた!?!?と思ったら普通に長さ測り間違えてたwww
    というわけで,普通に1,2,4,8という長さをどういう順番につけるかだ!
    (正面→正面 or 右)→(正面 →正面 or 左)→とつけていけばいいということなので
    あとは適当に,2種の動作を2変数に覚えさせて再帰してみる.
    まずは規則確認のため,一番分かりやすく各変数に方向転換を入れずに書いてみる.

  • [29B]a(X,Y,Z):YlZra(XX,XZrZrXrr,XYlYlXrr), a(s,,)

  • このときまだ未Solveがあったのでとりあえずこの29Bで放置.流石に縮むので後で戻ってきました.
    まず,lZrをZに変換してやる.

  • [27B]a(X,Y,Z):YZa(XX,XrZrZXrr,lXYlYlXl), a(s,,)

  • YlがYになるように変換.

  • [26B]a(X,Y,Z):YrZa(XX,XrZrZXr,lXYYXl), a(s,l,)

  • rZがZになるように変換.

  • [23B]a(X,Y,Z):YZa(XX,XZZXr,XYYXl), a(s,l,r)

  • 易しいルーチンワークで23Bになり,これでかなり綺麗になった感じ.
    1132[Contest 4A-9 Boss crystal]
    Bossなので怖いけどSolveは出来そうな形.
    「4倍関数で1周」がいくつか重なってそうに見える.
    現在地に止まっていても外の輪には乗っていないので,4倍して1歩進みそう.
    パーツ成長がよく分からないのでとりあえずなぞって規則を確かめてみる.

  • [テストコード]a(rss)sa(rsslsrssrslss)sa(rsslsrsslsrssrslssrslss)

  • ちゃんとそれっぽいところを通った!このrss,rsslsrssrslss,…を再帰に乗せようとすると
    それっぽいものが浮かんでくる.というわけで

  • [テストコード]a(X):XXXXsa(rsslsXrslss), a(rss)

  • これでSolve?Bossな割に簡単だったな〜.……と思いきやダメだった!!!!
    ダメな場所をチェック.なんだここ??どうすんだ??と思いきや正面にs進むタイミング
    の問題だった.とりあえずそれで書いてみる.

  • [25B]a(X):XXXrslXa(rsslsXrslss), a(rss)

  • Bestが22B.流石にこんな単純な規則だから最適化しなくちゃ!というわけで色々粘る.
    まず,sの方向が正面になるようにしてみた.

  • [24B]a(X):XXXsXa(sslsrXslssr), ra(ssr)

  • この2本を軸として短縮を探っていく.まず最初の解でrslを文字で置くと1B減る.

  • [23B]b:rsl, a(X):XXXbXa(bbsXbss), a(rss)

  • X成長のところはrslXs型の関数が望ましいけどそれをすると実行部のXXXbXが
    短縮できないの
    でこの方針は23Bまで…と思ってましたがここも
    右に捨てれるっていう!Best解かっこえぇ〜.Best解:

  • [22B]b(X):rslXs, a(X):XXXb(Xa(b(b()Xb()))), a(b(r))

  • すごいね!これには及ばなかったけどせっかくなのでコンテスト中に作った他の23B解たちを.

  • [23B]a(X,Y):XXXYXa(YYlYrXYss,rsl), a(r,)

  • [23B]a(X,Y):XXXsXa(sYrXYsr,sls), sra(l,)

  • あんなテクニックというよりも,初項rssがうざいので「特殊な初項」系かなーとか
    考えていました.一番下のやつは初期位置がずれまくってて残念な感じにw
    戻る inserted by FC2 system