読者です 読者をやめる 読者になる 読者になる

ctyl's problem solving

競技プログラミングが主な話題です。

ICFPC 2016 参加レポート

kenkooooさん,roitiさん、わいんさんとICFPCにチーム"COBOL Lovers"で参加していました。

全員非学生なので金曜は問題を読む日にして、土日に集まって問題を解いていました。会場を提供してくださったkenkooooさん及び同居人の方に感謝します。

問題概要

ICFP Programming Contest 2016: Official Site

  • 正方形の折り紙を折った時のシルエット(頂点と辺の情報)が与えられる。どのように折り目がついたかの展開図と、折った時の頂点がもともとどの点と対応しているかを答えよ。ただし、最初は折り紙は(0,0), (0,1), (1,1), (1,0)を4頂点とし、入力は必ず有理数で表現される。折った後の折り紙は回転移動や平行移動を含んでいる場合がある。

入力は次の順に与えられる。

  • 折り紙を作る多角形の個数。以降の入力が多角形の個数分与えられる。
  • 多角形の頂点の個数
  • 次に頂点が列挙される。中実の場合は時計回り、中空の場合は反時計周りに列挙される。
  • 線分の本数
  • それぞれの線分の両端の頂点
1
4
0,0
1,0
1/2,1/2
0,1/2
5
0,0 1,0
1,0 1/2,1/2
1/2,1/2 0,1/2
0,1/2 0,0
0,0 1/2,1/2

ビジュアライズしたもの(kenkooooさん作) f:id:ctylim:20160809224148p:plain

次の順で出力する。

  • 展開図の頂点の数
  • 折った時の各頂点の座標
  • 展開図の折り目がついた多角形の数
  • 多角形の頂点の個数、及び上で出力した頂点のどのindexに対応するかを時計回り、または反時計周りで列挙
  • 折られる前に各頂点がもともとどこにいたか

出力例

7
0,0
1,0
1,1
0,1
0,1/2
1/2,1/2
1/2,1
4
4 0 1 5 4
4 1 2 6 5
3 4 5 3
3 5 6 3
0,0
1,0
0,0
0,0
0,1/2
1/2,1/2
0,1/2

1日目

問題を読む。yukicoderがあったので参加した。

2日目

折り紙を買う。会場にてチームメイトと合流する。すでにkenkooooさんが問題をクロールして、入力をビジュアライズするスクリプトを書いていたので、ありがたく使わせて頂く。そして全員がpythonを使う流れに。入力に有理数表現があって、fractionモジュールがあるpythonを使うのは結果的に正解だった。

2日目は有効な手法をほとんど実装できずに終わってしまった。roitiさんが何も折らない正方形の解をひたすら無差別に提出していたからか、一時期順位が50位くらいまで上がった時があった。オーバーフローさせるだけの(クソ)問題がいくつか提出されていて、インタラクティブなコンテストの難しさを感じた。(正解者は入力のサイズに比例した点数が獲得できる)

公式から折り紙シミュレーションプレイヤーの提供があった。ソースは難読化が施されたjavascriptで書かれていたらしく、それを解読したら難読化されたアルゴリズムが記述されていた。もちろん読めない。

凸包解はコンセプトは簡単に思いついたが、実装が難航し、この日は手動提出+正方形爆撃で終了。

3日目

とにかくプログラムを書いて簡単な非自明な問題に正解することを目標とした。夕方ごろまで実装が何も進まず、鶴を折れなかったり、わいんさんが筋肉で非自明な問題を提出をしているのを観察していた。ずっと頂点の対称移動の方針で考えていたが、面の対称移動をする方法を思いつき、夕方頃から1回折る問題に解答できるソルバーの実装を始める。わいんさんがあらかじめ実装していた対称移動ライブラリをお借りしたが、実装が終了する前にわいんさんの帰る時間となり見送ることに。

すまん、どうしても寿司が食べたかったんだ...

食後に折り目によって分割された面を木で管理する方法を思いつく。帰宅後は自分のソルバーの続きを実装。 夜中に1回折る問題を半自動(折り目のみ指定)で数問通した。この程度だったら2日目に実装できたレベルだが、疲れたので次のステップに進むことはできなかった。kenkooooさんから面を木で管理する方法でかなりうまくいったらしいが、無限のバグで死亡したという報告を受け、寝る。


総評

最終順位は約300チーム中80位前後でした。自分の貢献度が低すぎてチームメイトに申し訳なかったのですが、ワイワイできて楽しかったです。3日目に思いついたアイデアを2日目に思いついていたらもうちょっと生産的になったかも、という後悔もありました。またインフラの重要性も感じ、前半でインフラをどれだけ充実できるかも勝負を有利に進めるポイントとなった気がします。というのも、提出の結果は手動提出時のリザルトページかAPIレスポンス経由でしか取得できず、チーム参加の場合は提出環境を統一して、問題リストを一括管理する必要を感じました。公式のジャッジシステムやシミュレーションツールがとても出来が良く、公式ツールレベルの実装に達しただけでも相当上位に食い込めそうな印象でした。チームUnagiが潜伏しながら首位争いをしていて、格の違いを感じました。ネタが折り紙だからか、日本人のチームが上位に多かったようです。普段のコンテストと違い、こういった長時間のコンテストも楽しかったので、来年も参加したいと思います。


チームのソースコード及び自分のスパゲッティソルバーはこちら。 github.com