ICFP Programming Contest 2016 参戦記
今年も*1チームUnagiで参加しました。チームメイトの日記：
開始前
Unagiは例年iwi家に集まって戦っているのだが，残念ながら私は海外出張が重なってしまい，iwi家にいられるのは最初の1日ちょっとになってしまった。
公式ツイートのうちhttps://twitter.com/ICFPContest2016/status/757792006345150464の出題者が中野圭介先生だと予想。根拠：
In this talk, I introduce an interesting property of B-terms, that is, whether repetitive right applications of a B-term circulates or not.
http://www.njpls.org/may16.html#keisuke
1日目 (Lightning)
朝〜昼
‥‥と思いきや，関数型言語ということもなく，折り紙だった。ICFP 2016が奈良開催のため日本人ジャッジによる出題で，なるほど日本らしい。
最初は，時間が無限にあれば解ける方法を話し合っていた。「合計面積1をナップサックすれば，何重に折られているかが分かる」みたいなことを言った気がする。実は「合計長1をたどると元の折り紙の1辺が分かる」ということの方がずっと大事だった。
折り紙についての論文を調べる。検索の結果，Erik Demaineが折り紙理論の権威っぽかったので，講義資料を読んだりするものの，今回の問題に直接つかえる内容はあまりなかった。（例えば，与えられた「骨格」に上手く肉付けして折り紙にする話題があったが，厳密に折りたい図形を作ることには応用できそうにない。）
chokudai, wataがソルバーを組みはじめる一方，手動でジャッジ出題の問題（「古事記」に載っている折り方という設定だった）を解いていた。問題番号30から33はI, C, F, Pの文字に折られていて，I（上下のserifつき）とかFとかは手動でも難しかった。後で振り返ると，このときに直角二等辺三角形のタイル張りに沿って折ることが分かっていても十分難しいという知見を得た。
昼〜夜
Lightning終了時から提出が始まる「折り紙の問題を（コンテスト参加チームが）出題する」パートに取り組むことにした。
折った結果の図形だけでなく，元の折り紙の4辺や折り線が問題のヒントとして与えられてしまうので，線を重ねると難しくなるのではと最初は考えていた。たとえば，同じ頂点を通る直線で何十回も折る作戦を思いついたが，
- 座標が有理数という制約により角の2等分線が必ずしも折れないこと
- 座標の分母の大きさを見ると何回目に折ったかのヒントになってしまいそうなこと
- 結局凸多角形になってしまいそうなこと
などの対策を思いつかずに断念。
「1辺1の正方形をタイリングできるパーツがあるとそれだけで全部埋めようとして探索失敗する」という感じの内容をwataが言っていたので，普通に手動が難しかった問題がプログラミングで解くのも難しいらしいと予想し，45度単位でしか折らない作戦に切り替え。その制約の中でなるべく気持ち悪い折り方をする方法を考えることにする。
折り紙の「展開図」から平面的な折り紙が可能か（以下，「有効な展開図」と呼ぶ）は各頂点のまわりを調べるだけで判定できるので*2，現実的な折り手順があるかは完全に無視できる。また，どのように折った状態からも（少なくとも）全部まとめて折ることができるのと同様に，有効な展開図であることを保ったまま折り線を書き加えることは難しくない。
実際の出題データ生成は次のようなプログラムを書いた。
- N×Nのグリッドを準備。次をM回繰り返す
- 折り線がまだない格子点をランダムに選択した後，その点から折り線を適切に4本のばす。新しく書く折り線はすでに書かれた折り線にあたるたびに屈折させれば*3有効な展開図を維持できる。
- グリッドで作業していたので，多角形のデータに直して出力。
「点から折り線を4本のばす」ときに，90度+45度+90度+135度にわけるパターンが選ばれると「気持ち悪い折り方」になるというつもり。2日目以降に自分がいなくなっても最低限の編集（パラメータ調整とかデバッグとか）ができるようにC++で書いた。
夜〜朝
ジャッジに提出するデータは，
- 折る前の頂点たちの座標
- 多角形たち（何番目の頂点を用いるかで表す）
- 折った後の頂点たちの座標
からなる。実は，上で生成した出題データはこのうち最初2パートしか作っていない。折った結果は展開図から（合同変換を除き）一意に定まるので，データの最初2パートから最後のパートを自動生成できる。iwiがソルバーに共通となる前処理・後処理を作っていたのだが，折った後の座標の自動生成はソルバーには必要なかったらしく自分が実装することになった。（冷静に考えれば，ソルバーは折った後の図形から解くわけで当然だった。）
「折り線は45度単位だけど，念のため任意の有理直線に対応しておこう」と思ったものの，C++の多倍長ライブラリを使った経験がほとんどなかったため，（こっそり*4）Haskellで書いた。折るだけなのでoru.hsと命名。
oru.hsの完成により「出題」準備がととのう。imos, sulumeによるビジュアライザに投げると狙い通り気持ち悪い折り紙ができていたので一安心。
2日目
朝〜昼
出題データ生成プログラムに直書きしていたパラメータを引数で与えるようにしたり，ランダムで一度書いた折り線をちょっと消すこともする改造をしたりした。(gen3.cc)
出題データは多めに作って，チームメイトたちによる目視で難しそうなものが選ばれた。パラメータはひとまず N=24, M=7 としたが，他チームに解かれる気配はなく，最後までその設定で乱数のseedだけ変えたものを提出していた。
ちょっと余った時間で実物の折り紙を折って解いていた問題の展開図を入力し，oru.hsを通して提出可能なデータにした。
その後
飛行機。
3日目
「国際会議の発表がひかえているからあまり参加できないかもしれない」と言っていたものの，
- 経由地の空港で，古事記の22, 24番を手動で解く。（24番を解いていた唯一のチームが24番を回転させただけの問題を出題していた。）
- 着いたホテルで，ソルバー用手動ヒントを作成。
後日
出題データに生成途中のものも追加してビジュアライズした*5：出題データ | Unagi | ICFPC2016。動画版(imos)：
他チームの参戦記より（追記）
fixstars（tomerunさん）
Unagiの問題が強そうなので方針をパクる。折るのは90度か45度の線のみで、skeltonの線がたくさん重なっているような非凸の図形だったら良い。
ICFP Programming Contest 2016 - TopCoderの学習のお時間 - TopCoder部
天羽々斬（osa_kさん）
Unagiが提出している問題を見ると、そもそも折っていくにしろ開いていくにしろダントツで難しい。そこで、Unagiは古事記くらいは解けるにしても、彼らが自分自身で出している問題は解けないんじゃないかという仮説を立て、同じような問題を作ることにする。が、そもそもUnagiの問題が手動でも解けない。
ICFPC2016 Team 天羽々斬 - osa_k’s diary
