ARC069Dを解いた
解くのに無駄に時間がかかったので自分への戒めに解説を載せておく
問題概要は省略
以下、狼と羊をそれぞれWとSと表記する
siがoのとき動物列をaiとすると
{ai-1,ai,ai+1} = {SSS},{WSW},{SWW},{WWS}
xのとき
{ai-1,ai,ai+1} = {SSW},{WSS},{SWS},{WWW}となる
このときai-1,ai,siがわかっていればai+1が一意に決まるため４通り試せば全ての列を調べることができる 計算量はO(N)
作られた列が内容を満たしてるかどうかは先頭と末尾に反対側の要素を付け足して、一致するかを確かめれば良い(ソースコードの10,21行目部分)
実装方法についてはSを1、Wを0（逆でも良い）としてbit演算をすると良い
図よりxのときa[i+1] = a[i-1] xor a[i]っぽいことがわかるのであとは漸化式的に更新するときれいに書ける
～余談～
考察に１時間強、実装に３０分弱かかった
最初の４０分くらいはO(2^N)アルゴリズムから法則性を探してて本当に何がしたかったのかわからない
