wataの日記

プロコンや研究の話など書くかも

ICFPC 2019 参加記

今年もUnagiチームのいつものメンバーで参戦。今年の問題は二次元グリッド上でロボットを動かして全部の空きマスを塗りつぶすという基礎タスクに、追加仕様でブーストアイテムなどが加わっていくというものだった。暫定順位では１位なので優勝出来ていると良いなあ

↓分裂アイテムを取って３体で塗っている様子↓

  

使用言語をRustに統一

Unagiチームは例年言語を統一せずに全員異なる言語で参加していたせいもあって、得意・不得意が割とはっきりしていて、問題をたくさん解くタイプは得意（複数ソルバで独立に解けるので）、対戦AIは苦手（複数AIで協力ムズイ）、仕様追加も苦手（追加されるたびに全ての言語で同じものを実装する必要が…）という状況だった。

しかし、2017年のpunterが対戦AI＋仕様追加で惨敗したのを反省して、去年はソルバ班がchokudai以外Rustに統一され（元々chokudaiがRustに切り替えると言い出したはずだったのだが…）、今年はついにchokudaiがC#を一行も書くことなく、ソルバ班全員がRust統一となった（インフラ班はGoも使っていた）。

↓ iwiwi が chokudai にRust入門サイトを教えている様子 ↓

去年の参加記（http://wata-orz.hatenablog.com/entry/2018/07/26/194842）にある通り、言語統一の利点は非常に大きく、ソルバ１つをパーツに分けて皆で作っていくことで、各自が自分の担当部分を改良すれば全体のスコアが伸びて分業が捗った。Rustに統一する利点としては、速度が十分速い・バグが出にくい・他の人が書いたコードを使い回ししやすい（自然とグローバル変数を使わなくなる＆変更されるものにはmutが必要になるので）というのがあると思う。実際、今回も色んなパーツを別々に書いて組み合わせたら一発で動くことが多かった。学習難易度が高いとよく言われるけど、競プロやICFPCのプログラム書く程度なら意外と簡単なので、バラバラの言語で参加してる他のチームもぜひRustに統一してみてはいかがでしょう！

 

 

以下３日間の流れ

一日目

imos & sulume がインフラ担当して、iwi & tos が入力読み込み・manipulator の可視判定・シミュレータなどのライブラリ部分書いてる間に、自分 & chokudaiがソルバのメインロジック部分を書き始めるという分担でスタートした。

全部のマスを塗りつぶすというTSPっぽい問題なので、ちょうどKaggle Santaと研究でTSPを最近やったこともあり、TSPと言ったらk-optだろーと考えるが、直接踏まなくても周囲のマスを塗れるので難しい…

とりあえず貪欲を書いたら当然大量の取りこぼしが発生して最後に回収する感じになったので、盤面をk-meansっぽい感じで区切って区域間をTSP的に良い感じに順序付け、区域の内部を塗り終えたら次の区域に行く、というのを実装してみた。が、区域の境目あたりを塗る部分で無駄な動きが多く、取りこぼして最後に回収するのと大差ない感じだったorz

一方、chokudaiは左手法で周囲を塗り、内側の塗られなかった各連結成分を再帰的に左手法で塗って外側の左手法パスにくっつけるというのを実装し、かなり良い感じだった。この方針でヤバイケースが特になさそう＆ブースターの活用や局所改善などやることが多い＆せっかくの言語統一ということでこのソルバをメインに決めて改良していくことにした。

ブースターのうち、extend（manipulatorの数を増やす）と、clone（分裂する）は明らかに重要なので対応することにした。左手法の途中でアイテム拾うのが大変なので、iwiがextendを集める部分を書いて、それを左手法ソルバの最初に呼び出し、更にcloneが出来る後半マップでは自分の没ソルバから盤面を区域に分割する部分を持ってきて、各区域を一体が担当するという感じでつなげたら一発で動いてLightningに間に合った。

 二日目

Lightning終了で少し休憩するかと思ったら４時間後からMiningなる別ゲームが開始するという仕様追加が来た。Miningは、「指定した点を含む/含まない・サイズがいくつ・頂点数がいくつ」などの与えられた仕様を満たすマップを生成するタスクに正解出来ると、一つ前のブロックで生成されたマップに対する塗りつぶしスコアに応じてコインを獲得でき、それを使って追加ブースターを購入して最終スコアを伸ばせるというゲームだった。得られるコインが正解チーム数に依存するため明らかにスタートダッシュが重要で、４時間後の開始に間に合わせるデスマが始まった。大きい正方形から始めて含まれてはいけない点から外部に向けてトンネルを掘り、最後に頂点数を調整するという感じのをtosが書いて間に合わせた。殆どのチームは似たような方針でマップを生成していたようだったが、一部全く違う方針の天才チームも居た（https://twitter.com/yosupot/status/1143107274983890944）。

Miningの１ブロック目に間に合ったのは４チームしか居なかったので、大量の報酬コインを得ることが出来た。が、あまりのデスマに殆どのチームが付いて来れなかったため、なんと９時間後に開始を延期＆既に得たコインも没収になってしまった (´・ω・`)　９時間後の再開時はchokudai以外疲れ果てて皆寝ていて、慌てて起きたら延期後に完成した自動提出プログラムと延期後にリファクタリングされたマップ生成プログラムが両方バグって２ブロック不正解になりスタートダッシュに失敗したorz が、その後は順調にコインを稼いでいって、おそらく最終的には一番金持ちになっていた。

ソルバの方は、chokudaiが引き続きブースター完全無視左手法ソルバの改良を続け、自分は殆どのマップでcloneを購入出来そうなのでclone部分の最適化をし、iwiが局所改善（塗らない動きを最短路で置き換える）を書いた。cloneは区域に分割するのはやはり境界部分で無駄が発生する＆均等に分割するのが難しいので、一体のつもりで生成したアクション列をk等分するという方針に切り替えた。manipulatorは妥協してkの倍数個回収し全員に同じだけ使うことにした。分割後の開始地点への移動分無駄が発生するので、終点の方が近かったら反転させたり、ビットDPで誰がどの区間を担当するかを最適化したりした。

三日目

chokudaiは引き続き左手法を最強にし、iwiが最適な購入計画をナップサックで求める部分を書き、自分はiwiの局所最適化プログラムを引き継いて枝刈り探索による最適化を追加した。最後一時間くらいで上下反転して右手法にするのも試すと良くなるから後でやろうと言っていたことを突如思い出し、急いで実装して実行キューに投げたらバグっており、急いで直して再度投げるなどしていたらキュー消化のため3000CPUとかが投入されたｗ

 

ICFPC 2018 参加記

今年もチームUnagiのいつものメンバーで参加。今年の問題は最大４０体のロボットを並列に操作して指定された３Dオブジェクトを出来るだけ効率よく構築・破壊するというタスクだった。各ロボットにどう仕事を割り振るかやお互い干渉しないようにどう動かすかなど、見た目以上に難しくてかなりの良問だった。暫定１位なので勝ててると良いなあ。

https://icfpcontest2018.github.io/full/live-standings.html

役割分担

  • wata & chokudai : 構築ソルバ
  • iwi & tos : 破壊ソルバ + 便利ライブラリ
  • imos & sulume : インフラ + ローカルシミュレータ

例年、役割分担や解法の議論とかのチームプレイはかなり良い感じなのだが、皆バラバラの言語を使うため、同じ機能を複数言語で実装したり、特に仕様追加がある問題の場合はすべての言語で仕様追加が必要だったりで、非常に無駄が多いのが問題点だと感じていた。そこで今年はRustで統一しようという話になっていた…はずだった…が始まったら皆バラバラの言語で書き始めて暗雲が立ち込めた。が、思ったより実装が色々重い（まともな点数を取るソルバを一から書くのがかなり大変）ということで結局最終的にはRustにそれなりに収束して色々なルーチンが色々なソルバで再利用されて過去最高効率だった。例えば最終的な破壊ソルバは高速初期配置(by tos) → 3Dダイクストラ(by iwi)を内部で使う支柱破壊(by wata)を逆再生した支柱建築(by iwi) → 平面GVoid (by iwi) → 高速集合(by tos) といった感じで色々なパーツを組み合わせることで出来上がっており、言語統一の力を感じた。来年さらに統一が進めば最強になるのではないだろうか。他のチームもRustを使ったところがそこそこ居たみたいだしRustの時代来てますね。とてもオススメですよ！以下ソルバ班の流れ。

１日目

事前情報でLive Standingsがあって最終提出のみが最終順位に反映されるとあったので、2014年みたいな独自のマシン語仕様が与えられてその上で動くAI作るタイプかなあと勝手に想像していたが完全に違った。優勝した2013年や2016年に近い形の、コンテスト時間中にどんどん問題を解いていくという、一番得意な形式だったのでやる気が出た。 

スコアの計算式的にHarmonics(ブロックを宙に浮かせる操作)は常時オフ以外お話にならないので存在を忘れることにし、宙に浮かせることなくオブジェクトを構築する方法を考える…が分からない…とりあえず適当な方法で構築して詰んだら諦めるソルバを作り、解けなかった問題については個別に対策を考えようということになった。

効率を考えると各ロボットが3×3の四角柱を縦に一気に構築するのが良さそう（移動一回あたり9マス埋めれる）ということになり、すでに作ったところからGroundedを保つように上 or 下に四角柱を構築していくソルバを書くことにした。障害物を避けながら目的地に到達するルーチン（競プロ力を発揮し、位置→ターン数で幅優先する代わりに、位置×方向→(ターン数,そのターン中にまだ進める歩数)でダイクストラをすると、辺の数が減って高速化出来る）や、初期配置・集合ルーチンなど、色々なソルバで必要になるであろうパーツが多すぎて大変だったので、iwi & tos によりRustでライブラリ実装が行われた。ここで言語が発散しなくて本当に良かった。

結局3×3の方針は、小さい問題はロボットが余って暇をする＆大きい問題は遅すぎて実行が終わらない＆結構詰む、でうまく行かなかった。chokudaiは全体をy座標が同じ層に良い感じに分割・順番付けしてGroundedを保つように上に行ったり下に行ったりしながら構築するソルバを実装したが、こちらもLightning終了までには全問解き切ることは出来ず、Lightningは提出なしで終了した。

二日目

仕様追加で破壊問題・再構築問題が追加され、更に矩形領域の一括構築・破壊操作(GFill,GVoid)が出来るようになった。3×3で埋めるよりGFillしたほうが明らかに効率が良いので、作りかけのLightning用ソルバを破棄。３種類の問題をどう解くのが良いかの議論になり、chokudaiソルバが詰む予定のケースがあるらしいので再構築ソルバを作れば詰んだケースの救出も出来るのではと思ったが、chokudai方針の層構築に比べて３D構築は実装が非常に難しい＆結局chokudaiソルバが全問解けそうという感じになったので破壊ソルバを作って一旦更地にしてから構築ソルバで再構築するという方針に決まった。破壊ソルバは、Groundedを保つように少しずつ壊すより、Harmonicsを思い出してGVoidで一層ずつ一気に消した方が簡単だしスコアも良さそうということになり、iwi & tos が担当することになった。

構築ソルバの方は破壊操作が加わったことにより、支柱を同時に構築することでGroundedを保つ戦略が取れるようになった。こうすると下から順に一層ずつ構築していくことが出来、最後の支柱破壊以外は障害物なしの二次元問題になるので非常に楽。下からの構築以外に真ん中からx軸方向 or z軸方向に半分に分けて横方向に一層ずつ構築というのも同じ方針で出来るので実装した。構築する向きによって必要な支柱の数が違うし、y方向ではなくx or z方向だと半分に分けて二層同時に構築するので一層あたりのロボット数が半分になり、暇になることの多い小さい問題での効率が上がった。

三日目

ようやく全ての構築問題に対して解答が出来た。スタート地点遠すぎだった。次に層構築で2D・1DのGFillを使う最適化を行った。作りたい層を良い感じにGFill可能な矩形領域のジョブに最初に完全に分割しておいて、その分割に従ってロボットを矩形の頂点に移動させてGFillしていくことにした。ロボットへのジョブの割当は一番近いところに貪欲に割り当てることにし、デッドロックしないように、既に他のロボットに割り振られたジョブをより近いロボットが暇になったら奪い取るという実装にした。Groundedを保つ順で構築しないといけないという依存関係がジョブにあり、支柱周辺のように依存関係の根本付近が細い場合に大量のロボットが暇になってしまうので、ジョブにロボットを割り当てたら完了を待たずに依存先のジョブにも先回りでロボットを割り当てたり、同じターンに同時に依存先までGFillしたりする最適化をした。

破壊ソルバの方はHarmonicsを必要な時だけオンにする最適化が入った段階で、ローカルシミュレータは通るけど公式シミュレータだと落ちることが発覚。公式とのシミュレーション結果に差がある問題を確認するために一旦提出した（潜伏していたわけではない）。破壊ソルバ・ローカルシミュレータ両者のバグは取れたけど、一問でも落とした瞬間敗北確実なスコア計算式なので念の為公式シミュレータを使って最終確認する機能をimosが実装した（ブラウザでページを開いておくと公式シミュレータが繰り返し走って結果をサーバーに送るのでマイニングと呼ばれた）。問題によっては単純な上からの面破壊だとHarmonicsが長時間必要になるため、構築ソルバの支柱破壊ルーチンを逆再生することで支柱建築をし、そのあとで破壊するという最適化が行われた。

最後に、30×30×30以下の小さい問題で結構負けていたのを、tos & chokudai が手動で解いたり、ソルバのパラメータを変えて実行したりして、最終的にほぼ全ての問題で凍結時点でのスコア基準で満点 or 満点-1のスコアが出た。

最終提出物を作る段階になって、最新版の破壊ソルバを使うと再構築問題が大量に死ぬことが発覚した。実は再構築問題は破壊ソルバの解と構築ソルバの解を単純につなげるだけではダメで、破壊ソルバの終了時点で原点に集合した際のロボットIDが1以外になっていると、構築ソルバの初期状態が違うので順番を並び替えないとダメだった。支柱建築をしない版の破壊ソルバは規則正しく動く性質上、必ずID=1が残るように集合していたため、それまで気づかなかった。このバグは時間内に修正できなかったので再構築問題は支柱建築なしの破壊ソルバとの組み合わせで解答を提出した。

構築例

f:id:wata_orz:20180726161938g:plain

宙に浮かないように支柱も建築して最後に破壊

f:id:wata_orz:20180726162014g:plain

GFillを使って面を一気に構築

f:id:wata_orz:20180726162019g:plain

 縦方向に作ることも出来る

0/1/all CSPs, Half-Integral A-path Packing, and Linear-Time FPT Algorithms

NIIの吉田さん、阪大の山口さんとの共著論文 https://arxiv.org/abs/1704.02700 が理論計算機科学のトップ会議FOCS 2018に採択されました。

概略

与えられたグラフが森か？二部か？与えられた2-CNFが充足可能か？など様々な問題が単純なDFS (unit propagation)によって線形時間で判定可能です。一方で、Noの場合に出来るだけ少ない個数の頂点(or 辺)・変数(or 制約)などを除去してYesにする最適化問題は多くの場合にNP困難となります。最適値を$k$とすると、$k=0$は超簡単（線形時間）ですが、$k$が一般の場合は激ムズ（NP困難）というわけです。では、$k$が小さい定数の場合はどうでしょうか？本研究では、このようなunit-propagationにより線形時間で解けるタイプの問題に対し、任意の定数$k$に対して線形時間で動作するアルゴリズムを与えました。問題ごとに専用のアルゴリズムを作って各個撃破するのではなく、分枝限定法＋増大路という一つの枠組みで様々な問題に適用できます。アルゴリズムは結構複雑ですが、実性能も結構高いだろうと思っています。せっかくなので今回の手法を用いると解ける競プロの例題を一つ作ってみました。

例題

$n (\leq 10^5)$人の間で$m (\leq 10^5)$回背比べをしました。$i$回目は$a_i$君と$b_i$君が背比べをし、$a_i$君の身長より$b_i$君の身長がちょうど$c_i (\leq 10^9)$cmだけ高かったそうです。$n$人のうち何人かはズルをして背伸びをしたりしゃがんだりして身長をごまかしため、結果に矛盾が生じているようです。少なくとも何人がズルをしたか計算して下さい。6人以上がズルをした場合は"Too many"と出力して下さい。

サンプル入力: n=4, (a,b,c)=[(1, 2, 1), (1, 3, 2), (1, 4, 3), (2, 3, 1), (2, 4, 1), (3, 4, 2)]

サンプル出力: 1 (4番がズルをして、残りの身長が(例えば)それぞれ1cm, 2cm, 3cm)

背景

パラメータ$k$に対して$f(k)\mathrm{poly}(n)$という形の計算時間で動作するアルゴリズムはFPT (Fixed Parameter Tractable)と呼ばれます。上の例のように、$k=0$だと簡単だけど$k$が一般だと難しい問題に対し、$k$が小さい場合にまで簡単さを拡張したい、というわけです。これまでにFPTアルゴリズムを作るための様々なテクニックが開発されてきましたが、その中で個人的に一番のお気に入りは半整数緩和を用いた分枝限定法です。

分枝限定法とは、答えの下界（or 上界)を何かしらの方法で計算して枝刈り探索する手法で、難しい問題を厳密に解きたい場合によく用いられるヒューリスティックです。近年の研究で、「半整数緩和」を持つ問題に対して、分枝限定法が唯のヒューリスティックではなく、$k:=$最適解$-$緩和解に対してFPTアルゴリズムとなることが分かってきました。直感的には緩和解が最適解と近ければ枝刈りが探索の浅いところで起きて高速に動きそうな気がしますが、この直感が正しいというわけです。

では、どういった問題が半整数緩和を持つのでしょうか？前研究「Half-integrality, LP-branching and FPT Algorithms (https://arxiv.org/abs/1310.2841)」では、$k$劣モジュラ性という劣モジュラ性の一般化を用いることで、unit propagationで解けるタイプの問題が半整数緩和を持つことを示し、FPTアルゴリズムを得ることに成功しました。また、最初の例にある二部グラフ判定・2-SATに対しては、緩和問題を最小カットに帰着して解くことで線形時間に出来るということも示しました。一方で、グラフが森かなど他の多くの性質に対してはそのような帰着が出来ず、緩和問題を解くために(指数サイズのLPなので）楕円体法を用いる必要がありました。これらの問題のうちいくつかは全く別の手法により各個撃破で線形時間が達成されましたが、他の問題に拡張出来ず、また$f(k)$の部分が非常に大きくなる、といった問題点がありました。

今回の研究の大きな動機となったのは、一つ前の記事で紹介しているFeedback Vertex Set (FVS)という問題を解くアルゴリズムの実性能を競うPACE challengeというコンペです。FVSは出来るだけ少ない個数の頂点を取り除いてグラフを森にするという問題で、まさに半整数緩和＋分枝限定法の枠組みが適用できる問題です。しかし先に述べたように、緩和解を求める既存手法が存在せず、そのままでは全く性能が出ませんでした。そこで、新たにFVSの半整数緩和を最大流っぽい増大路計算によって解く手法を開発し、コンペで優勝を果たしました。今回の手法はこの時のアイデアを元に、他の問題へ一般化したものとなっています。

 

Linear-time Kernelization for Feedback Vertex Set

https://arxiv.org/abs/1608.01463 が ICALP 2017 に採択されたので内容の解説をします．

 

概略

取り除くと残りが無閉路になる頂点集合を Feedback Vertex Set (FVS)と言い，与えられた無向グラフの最小FVSを求める問題をFVS問題と言います．これは有名なNP困難問題で，FPTアルゴリズムという理論アルゴリズムの研究分野で盛んに研究されており，PACE Challenge*1 というFPTアルゴリズムの実性能を競うコンテストの記念すべき第一回目 (2016年) の題材として選ばれました (ちなみに2017年のコンテストは 5/1 締め切りでまだ間に合うので興味のある方はぜひご参加ください)．この問題に対して，答えが$k$ (頂点数$n$に対してかなり小さいと想定)の時に $4^k n^{O(1)}$ 時間で動作するアルゴリズムを以前開発しており [2] *2，我々の手法の実用性を示すために参加を決めたのがこの研究のキッカケでした．このアルゴリズムは分枝限定法を用いており，実性能も相当高いはずと思っていたのですが，枝刈りに使う下界計算のために指数サイズのLPを解く必要があり（楕円体法で多項式時間にはなる），そのままでは全く速度が出ませんでした．そこで新たに，このLPを爆速で解くアルゴリズムを開発したところ，実はそれを用いて Kernelization という別の研究対象(詳しくは後述)の改善も出来るということに気づき，この論文になりました．ちなみにコンテストの方は @japlj さんと一緒に出てこの論文の手法を実装して優勝しました．

根付きFVSとLP緩和

以下のような根付き版の FVS 問題を考えます．

無向グラフ $G=(V,E)$ と根 $r \in V$ が与えられる．出来るだけ少ない点を除去して，$r$から到達可能な閉路が存在しないようにせよ．

$r$から出発して$r$に戻ってくる$U$-ターンをしない(同じ辺を何度も通っても良いが，辺$uv$の直後に辺$vu$を使うのはダメ) walk 全体を $\mathcal{F}$ としたとき，この問題は以下のような整数計画問題になります．\[\text{minimize} \sum_{v\in V}x(v)\\ \sum_{v\in V(C)} x(v)\geq 1\enspace (\forall C\in \mathcal{F})\\ x(r)=0, x(v)\in\{0,1\}\enspace (\forall v\in V-r)\]

この根付き問題に対するLP緩和の最適解は，$G$のFVSのうちで$r$を含まないようなものの大きさの下界を与えており，以下のような性質を持っています．

  1. 最適解で $0$, $\frac{1}{2}$, $1$ のみの値を取るものが存在する (Half-integrality)
  2. 最適半整数解を $x$ とした時，$G$の最小FVSで$r$を含まないものが存在するならば，$r$から$x(v)=0$の点のみを通って到達可能な点集合をどれも含まない最小FVSが存在する．(Persistency)

これらの性質を使うと割と簡単に分枝限定法の探索の深さが $2k$ で抑えられることを示すことが出来，探索木の大きさを $2^{2k}=4^k$ で抑えることが出来ます．

本論文では，このLPを最大流っぽい増大路アルゴリズムで$O(k|E|)$時間で解くアルゴリズムを与え(実装も結構簡単です*3 )，更にこの性質を使うことでグラフの大きさを$k^{O(1)}|E|$時間で$2k^2+k$点，$4k^2$辺まで小さく出来ることを示しています．

FPTアルゴリズムとは

2-SATが充足可能かどうかは線形時間で判定出来る一方で，Max 2-SATはNP困難であり，多項式時間アルゴリズムが存在しないと信じられています．では，「高々 $k$ 個以外の節を充足できるか？」という問題 2-SAT($k$) の計算量はどうなるでしょうか？実は任意の定数 $k$ に対して 2-SAT($k$)は線形時間で解くことが出来ます (具体的には計算量は節の数 $m $ に対して $O(4^k m)$ となる[2])．このように問題にパラメータ $k$ を導入し (Parameterized問題と言う)，$k$の関数 $f(k)$と入力長の多項式時間で解けるとき，その問題は「$k$に関してFPT (Fixed Parameter Tractable)」であると言い，そのようなアルゴリズムをFPTアルゴリズムと呼びます (Max 2-SATは充足されない節の数$k$に関してFPT)．難しい問題(Max 2-SAT)と簡単な特殊ケース(2-SAT)の間を調べる理論という訳です．

普通の多項式時間アルゴリズムの場合，(入力長に対する)多項式が小さなアルゴリズムの方が優れたアルゴリズムです．ではFPTアルゴリズムの場合，$O(4^k n)$ と $O(2^k n^2)$ はどちらが優れているでしょうか？ 当然，どちらが良いかは $k$ と $n$ のバランスに依存します．そのため，通常は入力長の多項式部分は無視して $f(k)$ を出来るだけ小さくする研究と，$f(k)$の部分は無視して入力長の多項式部分を出来るだけ小さく(特に線形に)する研究が並行して行われています．例えば先の 2-SAT($k$) の場合，$f(k)$の部分を小さくする方向の研究では $2.3146^k m^{O(1)}$ が達成されています [4]*4．

Kernelization とは

入力 $x$ とパラメータ $k$ を $(|x|+k)^{O(1)}$ 時間で大きさが高々 $f(k)$ の等価な入力 $x'$ とパラメータ $k'$ に変換する操作 を Kernelization と言います．Kernelize が可能ならば自明に FPT アルゴリズムが得られ (Kernelize 後の入力を自明な全探索で解けば良い)，実はその逆も成立し，FPTであることとKernelize可能であることは等価です．しかし，$k$の多項式にまで入力を小さく出来るかどうかは非自明で，出来るだけ小さなKernel，つまり多項式時間でどこまで入力を圧縮出来るか，が研究されています．

ここでもし，$k^{O(1)}|x|$ 時間で $(x,k)$ を $|x'|\leq k^{O(1)}$ かつ $k'\leq k$ を満たす $(x',k')$ に変形できれば，これを前処理として行ってから$f(k)|x|^{O(1)}$時間のFPTアルゴリズムを適用することで，全体の計算時間は$k^{O(1)}|x|+f(k)|k|^{O(1)}$となります．すなわち，線形時間かつ $f(k)$の部分も($k$の多項式倍を無視して)最小なアルゴリズムが得られるわけです．本論文ではFVS問題に対してこれが可能であると示しています．

*1:https://pacechallenge.wordpress.com/

*2:Yoichi Iwata, Magnus Wahlström, Yuichi Yoshida: Half-integrality, LP-branching, and FPT Algorithms. SIAM J. Comput. 45(4): 1377-1411 (2016)

*3:https://github.com/wata-orz/fvs/blob/master/src/HalfIntegralRelax.java

*4:Daniel Lokshtanov, N. S. Narayanaswamy, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh: Faster Parameterized Algorithms Using Linear Programming. ACM Trans. Algorithms 11(2): 15:1-15:31 (2014)

ICFPC 2016 参加記

運悪く日程が被ったDCJ決勝は棄権し今年もいつものチームでICFPCに参加．メンバーと役割分担，問題概要はchokudaiの記事を参照．ソルバの実行結果ログなどから思い出したところによると，以下の様に３日間作業した．

 

一日目(Lightning)

公式Twitterの発言から関数型ゲーかと思いきや，折り紙の折り方を求める問題だった．foldつながり？各チームが解答と問題を両方提出し，他のチームの問題を沢山解けば解くほど，自分のチームの問題が解かれなければ解かれないほどスコアが高いという形式で，ICFPCに本気で挑むキッカケともなった2010年を思い出した．この形式はジャッジの好みに影響されない公平感があって好き．折り紙に関する理論研究が色々あることは有名な事実なので，とりあえず論文をググったりしたが，直接役に立ちそうな知見は得られなかった．

 

問題を読んでchokudai＆iwiらと相談しながら，全体の戦略を練る．スコアの計算式から厳密解と近似解の間に物凄い差があり厳密ソルバが必須であろうということと，二日目から一時間に一問ずつ問題を出題出来るという仕組みから，初日のうちに小さくて激ムズな問題を作成する必要があることが分かる．解答サイズを制限ギリギリにすることでショートコーディング必須ゲーに出来るのでは…と危惧していたが，スコアに影響するのは問題サイズではなく模範解答のサイズであることが発覚し，そういう問題は出題する旨味がほぼゼロなので安心した．が，勘違いしたままのチームが居たのかショートコーディングゲーな問題がチラホラあった．

 

とりあえず，無限に時間があれば厳密解が求まる手法を考えることにする．公式ビジュアライザで遊んでいたら，鶴を折るためには広げる操作が必要なので単純な折り曲げ操作しか出来ない公式ビジュアライザでは不可能なことが発覚する．広げ方のパターンを色々搭載しても複雑な折り方をされたら解けなくね…と色々考えているうちに，実際に紙を折っていったり，折られた状態から戻していくという方針ではなく，Skeletonの各面を正方形に敷き詰めていく探索(例えばSkeleton上で面Aと面Bが辺aで接している時，展開した状態で面Aに対応するパーツがどこかにあり，それに辺aを介して隣接するのは面Bもしくは辺aに関して反転させた面Aのどちらかなので二通りに分岐するという感じ)をすればどんな複雑な折り方をされても無限に時間があれば解けそうという結論に至り，それを実装することにした．

 

今年も相変わらず，複数人で協力して一つの言語で一つのソルバを書くということはしなかったが，入力が結構使いにくい形式で，全部一人でやるのは大変＆自分とchokudaiのソルバの両方で同じ処理が必要そうということで，iwiが線分アレンジメントなどの面倒な前処理と，出力を短くする後処理をするプログラムをC++で作成し，それに自分のJavaソルバやchokudaiのC#ソルバがサンドイッチされて実行されるというカオス仕様になった．多倍長分数ライブラリや幾何ライブラリは当然予め用意してあったが，実数使わずに分数のままで回転させたり反転させたりする操作が激しく難しかったのでtosに教えてもらって実装．この関数はchokudaiのC#ソルバ(と確かC++)にも移植されて使われた．

 

ログによると初日の0:00にはソルバは一通り出来上がっていて，この時点で古事記(ジャッジの用意した問題)を1問あたりの制限時間1分で101問中50問解けたらしい．この時点でのアルゴリズムは，まず角に接するSkeletonの面を一つ適当に選んでスタートし，各辺に対して折る(=面を反転させて置く)か折らない(=Skeleton上で隣接する面をそのまま置く)かの二通りで分岐していく探索．既においた面と重なるようには置くことが出来ず，二通りどちらの置き方も出来ない，もしくは残りの面積がまだ使っていないSkeletonの面積を下回ったら枝刈りを行う．できるだけ浅い所で枝刈りをしたいので，置けるかの判定は分岐する１辺のみで行うのではなく，全ての未処理の辺について各探索ノードで毎回行った．更に，もし１通りしか置き方がないと分かった辺があれば分岐せずに先にそこを決めた．探索順序は割と適当で，最初に角に置く面はランダムに選び，分岐はまだ使っていないSkeletonの面が使えるものを優先した．

 

デバッグと探索の改良のために，昔ICPC用に作った幾何問題用簡易ビジュアライザを使って探索の様子を動的に見れるようにしたところ，通常，探索アルゴリズムは間違った方向を深く探索してしまうのを避けるために，制限時間を長くするよりも探索順を変えて何度も探索したほうが効率的な場合が多いのだが(例えばSAT Solverのrestart)，今回の場合はそもそも多倍長有理数幾何が重すぎる上に，枝刈り判定のために毎ノードで大量に幾何計算を行っていてほぼバックトラックなしのストレートで探索が進んでいても制限時間内に終了していないことが発覚．試しに制限時間を10分に増やした所，解ける問題数が60問に増えたので高速化を開始．重たい多倍長有理数計算を避けるために，各面にdoubleでbounding boxを持たせ，衝突判定時に先にbounding box同士が衝突しているかの判定を行って衝突しないものはスキップしたところ爆速になって問題数が71問に増えた．

 

問題をよく見てみると，最初に横に何回か折りたたんで長方形にしてから残りを折るものが結構あることが分かったので，次はそういう問題用の機能を搭載することにする．辺の長さから何分の一の長方形にしたら良いかの候補を列挙し(長さ1/dの辺があったら1×1/dの長方形を試すことにした)，正方形に埋め込む代わりに長方形に埋め込んでから最後にそれを正方形に戻せば良い．この拡張により解ける古事記問題が78問に増えた．

 

ここまでで9:00になってLightningが終了．自分のソルバは凸多角形のような簡単なものでも解けないのがあったのでchokudaiが凸ソルバを作って解けなかった問題を拾ったり，一部手作業で解けたものなども提出した．9:00の時点の順位表でトップになって喜んでいたら9:00に公開された各チームの提出問題分のスコアが含まれていることが発覚し，その分のスコアを抜いてみたら実は2位で残念だった．他の上位チームも結構接戦で皆探索書くの速いなあと思っていたが，実は手作業で解いているチームが多かったっぽい．

 

二日目〜三日目 

Lightningが終わって各チームが問題を出題出来るようになった．我々のチームは初日のうちにtosが激ムズ問題生成器を開発し，それの出力を人の目で見て更に選別して難しそうなのを出題した．tos作の出題した問題ビジュアライザ: http://tosk.jp/icfpc2016/viewer.html

 

他のチームの出題した問題にすぐに解答を送ることも出来るが，出題した問題が解かれたらより難しい問題を次は出題してくることが予想されるため，出来るだけ他のチームが我々の解ける簡単な問題を出題し続けてくれるよう，正答数３未満の問題には解答を提出しないという潜伏作戦を取ることにした．

 

他のチームの問題を見ていたら一見簡単そうに見える問題で細かい面が大量発生しているせいで正方形に埋め込んだ時の面の個数が爆発し衝突判定が相変わらず爆遅であることが発覚．毎回全ての辺について二通り試して衝突判定するのは時間がかかりすぎてヤバイ(各探索ノードで辺の数×面の数回の衝突判定)ので，新しい面を置いたら各辺について二通りそれぞれ今置いた面と衝突するかを判定するようにした(各探索ノードで辺の数回の衝突判定に改善)．この高速化で古事記の解ける問題数が87問に増えた．

 

探索順序がかなり適当だったので改良しようと色々試したがあまりうまく行かず，特に最初の一手を間違えると絶望するケースが多数．そこで，四角形の周囲に来る辺の長さは有理数かつ和が1にならなければならないという強い制約から周囲の辺が埋まるのではないかという議論になり，iwiが正方形の周囲に来る辺の列を探すプログラムを書き，そのヒント情報(角の一頂点から周囲４辺全てまで任意の長さの辺列)を受け取ってヒントの続きから問題を解けるようにソルバを改良した．一部の問題では周囲の辺列がほぼ一意に求まって解くことが出来たが，候補が大量にあって使えないケースが多かった．しかし，プログラムには分からなくても，目で見たら角に来そうな頂点が分かる問題が結構あったので，手作業で四角形の周囲に来る辺列を求めるGUIをsulume&iwiが作成し，人力で作成したヒントによって解ける問題数が大幅に増加した．

www.youtube.com

 

ヒントを与えた場合，普通に探索した場合と違って初期状態で正方形のあちこちに面が置かれるため，探索の深い所で発見した矛盾が探索の浅い所での決定の影響を受けていない場合が非常に多くなる．例えば極端な例として，正方形が完全に分断されて二つの独立な問題AとBになったとし，Aは大量に解が存在するがBには一切解が存在しないとしよう．Bを先に探索した場合にはBに解がないと分かった時点でAを探索することなく終了出来るが，Aを先に探索した場合，まずAの解aを見つけ，Bの探索に失敗し，次にAの解bを見つけ，やはりBの探索に失敗し，…とAの解の個数回だけBの探索を行う必要が生じる．AとBは独立なのでAに対するどの解を採用しようともBの探索は必ず失敗するので，Aから先に探索した場合でも最初のBの探索失敗時にやはり終了して良いはずである．そこでConflict Analysisを行って，矛盾が探索のどの決定に依存しているかを解析することにより，矛盾を解消可能な地点まで一気にbackjumpするのを実装した．このテクは昔Marathon Matchで使ったやつ(http://d.hatena.ne.jp/wata_orz/20100805/1281000288)で，ヒントなしだとほとんど性能は変わらなかったが(古事記は相変わらず87問)，ヒントありの場合の性能が飛躍的に向上した．ここまででついに古事記最終防衛問題と思われる鶴を倒すことに成功した．

www.youtube.com

↑ 見返してみると結構無駄が多いしまだまだ改善できそう

 

最終日0:00になり，解答を提出しない正答数のラインを3問未満→2問未満→1問未満→制限なしと徐々に緩めながら潜伏を解除することにした．自分のソルバの他にchokudaiが凸っぽい奴やショートコーディング問題や過去問回転させたやつなどを倒していき，解けない問題数は既に二桁になっていた．スコアボード凍結の3:00の時点では二位にトリプルスコア近い差を付けることが出来た．

 

 

 

Conflict解析を行ってもまだ数問だけ周囲４辺のヒントを完全に与えても解けない問題があったので，SAT Solverの技術を更に取り入れてソルバを改良しようとしたが，これはうまく行かなかった．そうこうしているうちに手動ヒント勢が問題を次々と倒していき全完が近づいてきたので，ソルバの改良は諦め，問題ごとにビジュアライザを眺めながら手動で良い方向に探索するようパラメータ調整することにより，ヒントありでも解けなかった問題を全て倒すことに成功した．

 

ラスト1時間半くらいでついに残りの問題数が一桁になり，全力で残りの問題のヒントを作成したが，惜しくも一問だけ残ってしまったorz 最後の問題は並行な線で非常に細かく大量に折りたたまれていて，一辺だけのヒントを与えた状態で，正方形を100.00% (小数点第三位四捨五入)埋めることに成功したよとソルバが出力しているのにも関わらず，超細かいパーツが埋まっていないらしく答えにはたどり着かず，二辺のヒントを与えれば解けそうなのに頑張っても手動でヒントが作れない…という状況だった．

  

 

感想

このチームでの参加も４年目くらいで大分慣れて来た感じがある．スコアボード凍結時点ではトップだったし，優勝出来ていると良いなあ…　最終結果は9/20に発表されるらしいです．相変わらずプログラミング言語の会議主催にも関わらずチーム内で使っている言語がバラバラだが，これはつまりタスクに合わせて適材適所で言語を選択するのが最適ということで…　最近はコンテスト引退気味だけどチーム戦はやはり楽しく，今年は問題も運営もしっかりしていて３日間楽しむことが出来た．運営の方々もありがとうございました．最近は研究の方でSAT Solver系のことにも手を出していて，上のソルバの動作とか見るとまだまだ改善の余地があるし，そのうち気が向いたらSAT Solverに学ぶ探索高速化術の解説を書くかも？