Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2016-08-15

[] ICFP Programming Contest 2016 12:46 はてなブックマーク -  ICFP Programming Contest 2016 - TopCoderの学習のお時間


例年のように会社の人たちと参加した(チーム名:fixstars)。6人で合宿。


やったこと


ソルバ作成

紙を開いていくという王道な方針のソルバは他の人がやっていたので、違う方法を考える。

入力のskeltonを最小の多角形に分解して、それらを1x1の正方形になるように敷き詰める、という方針にした。


2日目の昼くらいには何となく動いて、雑魚問は解けるようになった。

ただ指数オーダーなのでちょっと入力が複雑になると全く無理。

改善しようとしたけどたいして良くはならず、解ける問題のうち最も複雑なのはこの程度でした(problem id 285)

f:id:tomerun:20160813214912p:image


出題用の問題作

2日目の夜に寝ながら考えたら、どうやら問題を解くよりも出題のほうがスコアに占めるウエイトが大きそうなことに気付いた。

その時点で自チームの出題は一応最後の分まで行われていたけど、けっこう解かれそうなので強化することにした。


Unagiの問題が強そうなので方針をパクる。折るのは90度か45度の線のみで、skeltonの線がたくさん重なっているような非凸の図形だったら良い。


このシンプル仕様でも紙を折る実装が難しくて、生成器を作るのに8時間くらいかかってしまった。

ランダムに折りまくって適当に設定した評価関数にかけて良いのを出力する、というものだけど、評価関数だけではあんまり強いのを抽出できず、何十個か生成した中から人目で強そうなのを選別していた。

(でも結局数十個しか作らないのだから、GUIを用意して人力で作るようにしたほうが良かった気もする)


なんとか最後11問は、これで作成した問題に置き換えることができた。


Unagiのものほど強くはないけど、ひとつを除いてUnagiにしか解かれていないし、サイズも1000未満なので、1問2000点以上入ることになっていてまずまずといえよう。

はじめに提出していたやつは20チーム以上に解かれていたので、置き換えたことで2万点ほど得られたことになる。良かった(ただしUnagiに対してはアシスト)。


なんか「いかにUnagi以外には解かれなくてサイズができるだけ小さい問題を作るか」という競争だった気がする。

サイズが小さいと解くうまみが少なくて、人力部隊のターゲットから外れやすくなるという効果もありますね。


ちなみに作ったのはこんなやつ(problem id 5607・5638)。

f:id:tomerun:20160815085141p:image

f:id:tomerun:20160815085140p:image


問題一覧作成

ソルバを作る過程でデバッグ用に問題を画像出力していたのを流用して、各問題がどんな見た目をしているかの一覧を作成した。

f:id:tomerun:20160813223017p:image


ちゃんとデプロイする環境を用意しなかったので、自分以外にはあまり活用されていない感


反省・感想


よかったこと

  • めっちゃでかいホワイトボードがあって活躍した
  • 合宿先からコンビニが近いと便利
  • 朝食がバイキングだったので時間に縛られづらく、朝食を取らない人の罪悪感も減じられた
  • 睡眠時間は1日5時間程度で、集中も続いて削りすぎずちょうど良いくらいだった
  • コンテストの形式が非常に良く練られていて、本質以外の部分でのストレスが無かった
  • たくさんソルバの実装ができた
    • 例年あまりソルバ担当にならないので…
    • 次回はインフラ方面やりたい

よくなかったこと

  • 最後ソルバにバグが残ってることが発覚して、取り切れず諦めてしまったけど、後で考えてみたらそのバグが存在したのは「解答サイズを最小にするため多角形をマージする」という部分なので、必ずしも実行しなくて良いところだった。それに気付いていればバグの影響をかなり抑えられたはずだが…
  • バグが残っていることに気付くのも遅かった。ソルバとしては解が出たら満点のはずなのだから、それ以外になっている時点で即アラートを上げてもらうようにしておくべきだった
  • コンテスト全体としての戦略に対する考察が不十分だった。出題がかなり重要であることにもっと早く気付いていたら、あと5万点くらい違っているはず
  • 会議室の鍵がひとつしかなくて扱いづらかった(一人だけ先に寝ておいて早起きしてくる、みたいなのがやりづらい)

そのほか

  • 「これyowaさん問題専用ソルバあってよいよね」「でも自分らでやりたくないよね」「だれかやってくれないかな」とずっと思っていたら天羽々斬がやってくれていた。ありがとう
  • モダン焼 フジ、学生の頃に気になってはいたけど結局行ったことがないままだ
 |