CODE RUNNER 予選A
CODE RUNNERの予選Aに参加しました。
結果
45位/336人
問題
ざっくり説明すると、2次元平面上に散乱している点から2つ選んで線を引いて、その線分の長さが点数になるというものです。何本引いても良くて、引いた線の長さの合計がスコアになるんですが、1つでも交差（接触）していると、0点になります。
ルール
競技時間3時間。1秒に1回以上のクエリは投げられない。(投げるとエラーが返ってくる)
解法
個人的にこうやって解いたよーってだけできっと何の参考にもならないです。乱数です、はい、乱数ぶん回してました。乱数で2点選んで、線を増やして、スコアが増えたら追加するというのを2時間くらい回していました。唯一成功した工夫は、最初の方は大幅に点数が増えるとき（長い線が引けるとき）だけ追加するということです。焼き鈍し方からヒントを得ました。最後の方は1でもスコアが伸びるなら引いてくれ、頼む！ っていう感じでした。乱数に祈るしか無い状況。
反省点
乱数と言っても、もう少し工夫の余地があったわけで、接触していたらアウトだから、すでに選ばれた点は乱数で選ばれないようにするべきでした。さらに効率よく調べるならば、一度調べて交差することが分かった線分に対してはもう調べないようにするべきでした。まあ、実装に時間がかかるくらいなら、さっさとクエリ投げてスコア積んでいこうと思っていたのでやらなくて良かったのかもしれませんが、何かしら工夫しないとスコアに差が付きにくいのかなと思います。途中で、それぞれの線分の長さを保存しておけばよかったと思ったのですが、手遅れでした。実際は手遅れでは無かったのですが、手遅れでは無いことに気づいたのが競技が終わってからだったので、どっちにしろ手遅れ。
まとめ
予選当日にCTF4bに参加していたので、帰宅が開始時刻の15分前とかで、夕食を優雅に食べていたら30分出遅れました。その割には意外と良いスコアだったなと思っています。ただ乱数の運が良かっただけかもしれませんが。
去年の予選の問題は30分くらい読み込んで理解できなくて諦めたのですが、今回は2分くらいで理解してコードを書き始められたので、とても単純で奥が深くて楽しめました。
また、ニコニコ動画でちょくだいさん(@chokudai)による生放送があり、それを聞きながら参加できたというのも面白かったですね。いかに早く多くの問題を解くかという競技プログラミングと比べて順位の変動が激しく、参加していなくても見ているだけで楽しいコンテストなのではないかと思います。
上位の人たちは、前半でデータ収集して後半で一気に順位を上げてきていたので、全く違うアプローチをしていたのでしょう。乱数に頼らず、データドリブンな方法で攻略したいものです。
追記
キャリフル側の登録ができていなかったのでついでに問い合わせてみると、
"予選ABの総合順位で上位の方のみ、
ということなので、単純に予選Aで50位以内に入っているからと言って本戦に行けるわけでもなさそうです。
