ABC055 D - Menagerie - ツバサの備忘録

解法

$i+1$ 番目の動物は、 $i-1$ と $i$ 番目の動物が何か判明していれば、自動的に決まります。
これは4通りあり、
$i$ 番目が〇か×か、そして $i$ 番目の動物がどっちであるか、です。

$i$ 番目が〇で羊の場合
$i+1$ 番目は $i-1$ 番目と同じ動物になります。
$i$ 番目が〇で狼の場合
$i+1$ 番目は $i-1$ 番目と違う動物になります。
$i$ 番目が×で羊の場合
$i+1$ 番目は $i-1$ 番目と違う動物になります。
$i$ 番目が×で狼の場合
$i+1$ 番目は $i-1$ 番目と同じ動物になります。

ということで、最初の2匹を羊羊、羊狼、狼狼、狼羊の4通り試し、上の法則をもとにして動物を決めていったときに、 $N$ 番目と $1$ 番目の部分の辻褄があうかどうかを調べれば、その並べ方が存在するかどうかがわかります。
自分は、最初を2匹ではなく3匹にしましたが、結局3番目の動物も最初の2匹が決まっていれば自動的に決まります。