天下一プログラミングコンテスト2013 予選B

C. 天下一ジグソーパズルふたたび

［問題文］

部分点解法（30点）

内側のピースに関する条件が無い場合となります。

N, M ≥ 3 の場合

外周の4辺に一つ飛ばしに「特殊なピース」を置くことで、「特殊なピース」の数を最大化できます。左辺と右辺にfloor((N-1)/2) 個、上辺と下辺にfloor((M-1)/2)個で、合計 floor((N-1)/2)*2 + floor((M-1)/2)*2 個となります。

2×N または N×2の場合

この場合は N-2 個となります。

部分点解法（40点）

3×3, 3×4, 4×3, 4×4で「特殊なピース」が4つ作れないケースは限られています。

3×3

A=1の場合: 「特殊なピース」を作ることはできません。

B=0の場合: 「特殊なピース」は3つが最大です。

3×4, 4×3

A=1, B=0の場合: 2つが最大です。

A=1, B=1の場合: 入出力例2にある通り、3つが最大です

4×4

A=2, B=0の場合: 2つが最大です。

A=2, B=1の場合: 3つが最大です。

満点解法（1）

満点解法（2）

まず、「特殊なピース」と「四辺が凹のピース」を黒、それ以外のピースを白と考えます。そして、N×Mの盤面を考え、以下の条件を満たすように黒のマスを配置していくとき、 外周の黒マスは最大いくつになり得るか、という問題と考えられます。

• 黒マスは縦横に隣合わない
• 四隅のマスは白マス
• 内側の黒マスはA個以上
• 黒マスに完全に囲まれた白マスのグループが木になるもの(後述)がB個以下

以下のような黒マスに完全に囲まれた白マスのグループに対して、マスを頂点、隣接を辺と考えたグラフを考えます。そのグラフが木であるとき、四辺が凸のピースが一つ必要です。そのグラフが木でないとき、つまり閉路があるときには、四辺が凸のピースは必要ありません。

□■□
■□■
□■□

□□■□□
□■□■□
■□□□■
□■□■□
□□■□□

□□■□■□□
□■□■□■□
■□□□□□■
□■□■□■□
□□■□■□□

上の性質を考え、枝刈り探索によって答えを求めることができます。