天下一ジグソーパズルふたたび(天下一プログラマーコンテスト2013予選B [C])

スポンサーリンク

概要

問題文 →
公式解説 →
自分の提出 →

解法

直前 $1$ 行分の情報を持つタイプの DP により解けます(アリ本 p.179)。

あるところまで埋めた時点での

  • 直前 $1$ 行分について、下に向けて凸にしたかどうかのビット列
  • 最後の $1$ マスについて、右に向けて凸にしたかどうか
  • これまで全体で使った四辺が凹のピースの個数
  • これまで全体で使った四辺が凸のピースの個数

を DP のキーとして、「特殊なピース」の最大値を値とします。


状態が、$HW\cdot 2^W\cdot 2\cdot (HW/2)^2$ 程度で、遷移は状態あたり $O(1)$ です。全体として、$O(H^3W^3\cdot 2^W)$ 時間で解くことができます。最大ケースに対して、状態数は合計で $10^7$ 程度となります。

タイトルとURLをコピーしました