マラソン46

問題は特定の文章群からランダムにチョイスして、ランダムな長さ先頭から取ってきたのが種文で、その種文を桂馬飛びをしながら正方形の盤面に配置していって、その配置を入力として元の文章をかえせ、というもの。桂馬だと置けない時があるので、(20%の確率|置けない)のどちらかが起きると飛ぶ量を1マス増やして、また(20%の確率|置けない)なら1マス増やして…という感じになる。3マス以上飛ぶ桂馬飛びは同じ列や同じ行じゃないことで定義される。あと入力として各ターンに飛んだ量と、特定の関数 getWords を呼ぶと文章群の単語の出現頻度がもらえる。

まぁ圧縮だよなーとか思いつつ、とりあえずぼんやり適当に単語拾ってきて2gramでつなぐ…とかやって色々やってたんだけど、各ターンに飛んだ量を全くいかせてないし探索範囲広いしほげほげで、これでは論外だなあ…と思ったころには土曜が終わっていたように思う。

じゃあもう文章の先頭埋めるしかないかーということでやっと軌道に乗った。

最終的に埋めた物:

  • 全文章の先頭14単語に出現しうる単語を単語インデックスごとに。ただし getWords 関数の index で保持。
  • 全文章の先頭4単語を連続して。ただし上記先頭単語リスト内での index で保持。
  • 先頭5単語目から9単語目まででありうる 2gram 全部。ただし上記先頭単語リストの5-9番目の要素を順番にマージした配列の index で保持。

いやあわかりにくい。先頭4単語があればたいていの場合に4単語は復元できて、5単語目くらいならまだ組み合わせがかなり少ないので 2gram は無しで、6単語目から9単語目までは 2gram でそれなりにいけて、14単語目までは 2gram 無しでも、まぁ短い文章ならそんなに候補数増えないかなー、あとは getWords の単語リストを頼りに当てずっぽうみたいな感じで。

探索の評価関数は words.inject(1){|r,w|r *= w.size + w.score * 0.000001} という感じで、基本文字列長重視。長い文章だったら死ぬけど、長い文章はあんまり解けないのでまぁいいや…というような。

現状2位の人は保存する文章減らしたらしくて、ああそれは賢いなぁとか。あと1位の人がなんでその方法であんなにいいのか…とか。

つーかつっこんだ情報量は他の人より圧倒的に多い気がする。というわけで探索がヘチョすぎた予感が強いのであった…まぁやけに遅いとは思っていたんだ。

追記: そいや glog 使ってみてた。割とやりやすかったので次回以降も使っていくと思う。なんか SEGV とかした時にバッファを flush しないのがうざかったので 修正しといた

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h