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

ゆらのふなびと

競プロ, Python, C++

ICFPC2016に参加しました

ICFPC 参加記

だいたいのことは@さんが↓に書いてくれたので、この記事では時系列に沿ってやったことを振り返ってみたいと思います。

kujira16.hateblo.jp

主にソルバー担当でした。

~0日目

@ さんが声をかけてくれたのでノった。ICFPCのことはあまり知らなかった。

1日目

まずはみんなで問題文を訳した。

とりあえず正の得点を取る解を考える。シルエットを長方形で近似してそれめがけて折っていけばよさそう。競プロの幾何ライブラリが使えるかなと思ったのでC++で書くことにした。入力が分数形式かつ分子分母の桁数に制限がないという闇仕様なので、多倍長で有理数演算するためにboostを持ち出す。結局この日は入力を読み込むコードを書いただけで終わった。

2日目

目覚めるとYazatenソルバーができていた。神。

メインコーダーはYazatenさんに任せて、僕は折り紙を「折る」クラスを作ることにした。折り紙を面の集合(面は頂点の集合)と捉えて、折り線が与えられる度に面を分割→対称移動すればよさそうな気がした。そこまでは組めたんだけど、結局点を初期位置に戻す方法が分からずお蔵入りした。

近似解と並行して厳密解の議論をしていた。折り紙を折っていくのではなく開いていく全探索的なアプローチ。折り目と面を頂点、その隣接関係を辺としたグラフを考えると、validな開き方は折り目の頂点を含む連結な部分グラフに対応する……というようなことを考えていた。

shoraさんがビジュアライザやらテストケース見るツールやらを作っていてとても便利だった。神。

3日目

昨日議論していたことの実装を考える。幾何パートが重くて実装が全然思い浮かばない。boostに投げて楽をしようと思ったので午前中はboostの幾何ライブラリをいじって終わった。

午後から実装を始めた。まず入力から面を列挙する必要があったがこれが既に難しい。shoraさんやmenphimさんと議論しながらなんとか書き上げるがバグらせたしその時点で既に19時だった。諦め。

コードの残骸は↓にあります。

github.com

反省

結局役に立つコードを全然書いていなくて申し訳なさ。僕がコードを書きたくて待ち切れず先走ってしまった感じなのだけれど、最初の1日は丸々考察に使ってもよかった気がした。

他のチームはビジュアライザを使って人力で解いてたところも結構あるみたいで、そういうアプローチを考えてもよかった。

実装力をつけたい。

面白かったので来年も出たいです。