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

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

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

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

分析ツールによる探索の可視化

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

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

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

手動ヒントツールの動作例

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