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

概要

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

解法

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

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

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

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

---

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