ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC055 D - Menagerie

問題
提出コード
構築です。

解法

i+1番目の動物は、i-1i番目の動物が何か判明していれば、自動的に決まります。
これは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匹が決まっていれば自動的に決まります。