No.359

座標圧縮の変形を使う.

置いてある竹の長さ $a_i$ と $L - a_i$ をすべて並べ, $0, \lfloor L/2 \rfloor, \lceil L/2 \rceil, L$ を追加してソートする. ソート後の並びを $b_1, b_2, b_3, \dots, b_n$ とする. ただし, $0$ より小さい値と $L$ より大きい値は除外する.

空いている部分の片方を $x$ とすると, たとえば $b_1 \lt x \lt b_2$ の場合はすべて門松行列になるか, すべて門松行列にならないかのどちらかである.

よって, $b_1 \lt x \lt b_2$ の適当な値で門松行列になるか, $x = b_2$ で門松行列になるか, $b_2 \lt x \lt b_3$ の適当な値で門松行列になるか, $x = b_3$ で門松行列になるか… と調べていけばいい.