Hatena::Grouptopcoder

yowa の TopCoder 日記

TopCoder yowa / twitter: @yowa

2016-08-19

ICFPC 2016 参戦記

10:02 | ICFPC 2016 参戦記 - yowa の TopCoder 日記 を含むブックマーク はてなブックマーク - ICFPC 2016 参戦記 - yowa の TopCoder 日記

毎年恒例3日間のお祭り、ICFPC <http://icfpc2016.blogspot.jp/> に参加した。

他のチームの方々の参加記(気づいた分)

ざっくりまとめ

  • チーム yowa として1人で参加した。
  • 折り紙を折る問題だった。
  • 出来上がりが凸多角形になるものだけ解くソルバを書いて、あとは個別対応した
  • 出題はサイズ600くらいの、凸多角形ではないけどシンプルな同じパターンの問題を出した。
  • 途中の順位は最高で2位(開始37時間後(ほぼ真ん中))、順位表フリーズの時点(終了3時間前)で10位だった。

  • 順位表的には過去最高に健闘できたと思う

問題

問題文はこちら: <http://icfpc2016.blogspot.jp/2016/08/task-description.html>

テストケースは、

  • 入力として、折り紙の完成形の外枠の形(silhouette)と、折り目や紙の端がどこを通るか(skeleton)が与えられる
  • 出力は、元の正方形の折り紙上の点(source)が完成形のどこに対応するか(destination)、各部分はどんな形に折られるか(facets)を答える

というもので、スコア

  • 運営サイドや他の参加者が作ったテストケースを解く(完全一致で高得点、完全一致した参加者が少ないほど高得点、問題サイズが大きいほど高得点)
  • 自分が作ったテストケースを他の参加者にむけて出題する(完全一致した参加者が少ないほど高得点、問題サイズが小さいほど高得点)

のようにして決まる。

やったこと

問題を見たら、座標は有理数で表されていて、分母分子が数百桁になるようなケースもあるようだったので、有理数が手軽に使える言語として Ruby を使うことにした(自分が使える言語が RubyC++ の二択だった)。

正直、普通に手でやる折り紙(この点をあの点に合うように谷折りして、こっちの線とあっちの線が合うように山折りして……)と、解答形式である facets の概念がぜんぜん頭の中で一致せず、なにやっていいのかわかんないまま十時間とか経過した。

わかんないにしてもとりあえず手でやる折り紙シミュレータを書くしかないだろうと重い腰を上げ、紙の移動・回転・頂点が特定の位置に行くように折る・頂点を特定の線で折る、の機能を実装した。

(「skeleton で定義される多角形を開いていき初形の正方形に戻す」が正攻法なんだろうなあと思いつつも)完成形が同じであれば、実際の折り手順がどうであろうと正解と判定されるので、 skeleton は完全無視することにした。

完成形が凸多角形であるような問題は、

  • 完成形がスッポリ含まれるような位置に初形の正方形を配置して、
  • 完成形からはみ出してる部分があったら内側に折り込む
  • はみ出しがなくなるまで繰り返し

という greedy な手順で完全一致解ができあがるよなーと思ってそれ実装。

凸多角形でない問題については、完成形の凸包を作ってそれに向かって上記手順を行うことにした。完全一致でない解でも一応スコアがもらえるので submit しなければ損だけど、まあ投げないよりはマシ程度のスコアしかもらえないのであんまり意味は無い。

出題は、

  • 凸多角形だとあっさり解かれる
  • (解かれにくさが同じなら)サイズが小さいほど有利なので、小さめの問題
  • 自分のシミュレータは折り紙の開く操作(折り鶴の3手目の三角形を四角形にする、みたいなやつ)を表現できてないので、そんな問題は考えない

みたいなことを考えつつ、結局一つの角を起点に上下に折り返すだけというやる気の感じられないものが出来上がった

http://i.imgur.com/8MXzT84.png

汎用ソルバを作るのは最初から諦め、あとは問題を目視して個別対応→他の問題にも適応できるか走らせる、という感じ。

  • 初形を平行移動・回転させたあと、1回だけ折って到達できないか?
  • 特定の形に特化したソルバ。下のようなL字型なら「『頂点0,1,3,4が直角で、辺1-5と辺5-4を足したら長さ1で、0-6と6-3を足したら1で、0-1の長さが1/k』という条件にマッチするなら、初形から1/kに細長く折ったあと1回折ってL字型にする」みたいにベタに書き下した。とは言っても他にやったのは最後にもう一回折るC字型、S字型くらい。
  • 手動で解く。手動で解くツールは作れてないので、「頂点 3 を座標(1/2,1/2)に重なるように折る」みたいなのをいちいちコードで書いた。

思ったこと

途中の時点で高順位だったのは、その時点で自分が出題した問題が解かれていなかったから。上記の通りの生成法なので

  • 初形の4頂点のうち2~3箇所は直角のまま残る
  • 左上から残りの3頂点までの距離は初形のときのまま

のような、いかにも解く手がかりになりそうな情報が残ってる感じだったので、汎用ソルバを作ってるチームにはさっくり解かれるだろうなあと思っていただけに、(潜伏していたUnagiチームはさておき)そんなに未回答のまま残るとは想定してなかった。順位表フリーズの時点でも3~4チームしか解いてない模様。

汎用ソルバは最初から諦めていたので全然考察してなかったけど、他のチームの参加記を見た感じ、ちょっとやそっとのやり方ではあっという間に組み合わせが爆発してしまうようだ。

以上より、運営サイドが想定してたより難しい Task だったんじゃないかなあ、と感じた。(あるいは Unagiチームを想定して出題された?)

開始前に公式アカウントのTweetショートコーディングっぽいのがあったので、タスクショートコーディング要素があるのかなあ、と思ったら、そこまででもなかった。個人的に好きなICFPCの問題のタイプは「毛色の異なる複数のサブ問題が組み合わさっていて、それぞれのサブ問題をてきとーに解いてもそれなりスコアは得られて、どのサブ問題についても注力して解けばスコアアップにつながる」みたいな感じなので、解答側にもショートコーディングするような要素があればもっと楽しかったかもなあと思った。

テストケースの取得や解答のsubmitなどを行う API が用意されていたので自動化が楽でよかった(自動化できたとは言ってない)。ただ「自分がこれまでに投げた解答の一覧や、一致率の一覧を得る」みたいな API は用意されておらず、ローカルで一致率を計算できてない(完全一致したかすら判定できてない)上に submit 時の応答のログを取るのをサボっていたので困った。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yowa/20160819