ABC 055 D-Menagerie

D - Menagerie
どこか連続する2つの位置について羊狼の割り当てを決めると, 片側の決まった動物から, すべての場所の配置を決定することができます. よって, 1番目と2番目の羊狼の割り当て(2*2=4通り)を決め, それが条件を満たしているかどうかを確認し, 4つ試して解が存在しなければ-1を出力します. 高々4通りで, 文字列の長さはNであるので計算量はO(N)でおさえられます.
Submission #2920588 - AtCoder Beginner Contest 055