超難問を72時間で解く――過酷なプログラミング大会「ICFP-PC」、その魅力は　優勝チームに聞く（2/3 ページ）

　私たちは、普段はソフトウェアエンジニア、アカデミアや企業の研究者、スタートアップ企業の社長など、さまざまな職場で活動しています。一見すると接点がわかりにくい組み合わせに思えるかもしれません。

　実は私たちは、学生時代に「ACM-ICPC」や「情報オリンピック」などのコンテストで競い合った、同世代のライバル同士です。6人全員が、国内大会での優勝や世界大会への複数回の出場を学生時代に達成しています。

テーマは「折り紙」　超難問をどうやって解く？

　そんなUnagiが優勝した昨年のICFP-PC。問題のテーマは「折り紙」でした。あらかじめ折り紙のシルエットが与えられ、そのシルエットを再現する折り方を答えるという問題です。

　この問題には面白いポイントがあります。参加チームは問題を解くだけでなく、他のチームが解くための問題を出題するというルールです。他のチームが作った問題について、シルエットから折り方を答えられれば得点を得ることができます。一方、問題を作成したチームは、他のチームに正解されると得点が減ってしまいます。そのため、出題できる問題数の制限範囲内で、できるだけ難しい折り紙の問題を作る必要がありました。

　ルールでは、折り紙は最終的に平面になるようにし、切り貼りはできません。シルエットは1つの多角形で、ヒントとして折り目が与えられます。紙が重なって隠れた折り目も教えてもらえますが、何枚の紙が重なっているかは分かりません。

　私たちの成績は、完全勝利に極めて近いものでした。Unagiが出題した全46問は他のチームに全く解かれることはなく、逆に他のチームが出題した全3482問のうち、3481 問を解くことができました。ちなみに、私たちが解けなかった唯一の問題を作ることができたチームは、それを理由に審判特別賞を受賞しました。

　私たちが問題を解くために用意した分析ツールの根底にある考え方は、全ての可能性をしらみつぶしに試す全探索アルゴリズムです。しかし全探索アルゴリズムは、問題のサイズが大きいほど解くのに時間がかかってしまうので、そのまま実装しただけではほとんどの問題に歯が立ちません。そこで、さまざまな考察に基づき、試す必要がないと断定できる分岐の探索を途中で打ち切る処理、いわゆる「枝刈り」を実装しました。他のチームと差をつけるために、効果的な枝刈りをできるだけ多く実装するために、工夫の限りを凝らしました。

　私たちの分析ツールは非常に強力で、大部分の問題は自動的に解けましたが、残りのとても難しい問題を解くために、人間がヒントを与える仕組みを作成しました。

　昨年の問題は難易度がかなり高く、上位に入賞したチームでも、人間が与える情報が多かったり、そもそも分析ツールを全く作成できず人間がほとんど解いていたり――という状況でした。

　私たちの場合は、人間が与える情報をあえてかなり薄くしました。これは、あらかじめ作成していた分析ツールにヒントを入れやすく、人間が効率的に与えやすいという点を熟考した選択でした。この判断が功を奏し、ほぼ全ての問題を解くことができました。

　他のチームに出題する問題の作成のためにも、独創的なアルゴリズムを開発しました。折れ線が複雑に重なる折り紙を作るために、軸に平行か45度になる方向に折れ線を設定。折り紙を折っていくのではなく、折れ線をランダムに描いていくような方針で、問題を作成しました。こうして作った問題は極めて難しく、実は私たちの分析ツールでも解くことができません。

この記事の著者

関連記事

• 

  「人生を楽しくする方法の1つがプログラミング」──17歳でドワンゴ入社のエンジニアと“現場目線”で学ぶ「プロハイハイ」

• 

  先生「どういう動きか教えて」生徒「プログラムに書いてあるからそれ見て」――大阪の小学校で「たこ焼き型ロボット」を使った実証実験

• 

  「若い人が作るアプリは、年寄りにはつまらない」――Excelアートを極めるスーパークリエイター若宮正子さんが今度は「Swift」始める

• 

  「りんな VS. Wikipedia」しりとり対決の行方は――“集合知の頂上決戦”が話題に　作者は高校生プログラマー