No.025 D

数字は初めから指定されている数字も含めて1から順に置いていくとする.

このとき, 数字を置いたマスの上下1マスを含めて考え, 以下の4パターンを考察する.

1: 数字を置いたマスが端である

2: 数字を置いたマスの両側は空である

3: 数字を置いたマスの片側にのみ数字がある

4: 数字を置いたマスの両側に数字がある

1 のときは矛盾はない. 端には条件がない

2 のときは矛盾はない. 両側には後で数字が埋められるが, 埋められる数字は今置いた数字より大きい

3 のときは矛盾する. 片側の数字は今置いた数字より小さく, もう片側には今置いた数字より大きい数字が埋められるためである

4 のときは矛盾はない. 両側には今置いた数字より小さい数字が置かれている

以上のことより, 残りの空きマス状況だけ分かれば組み合わせの数を求められる.

あとは BitDP で解けばいい.