https://atcoder.jp/contests/agc034/tasks/agc034_a
すぬけくんしかいない場合を考えると、a地点からc地点に到達できる条件は、\([a,c]\)の間に連続する黒マスがないこと、である。
2人いる場合を考えると、\(c<d \) の場合は、すぬけくんとふぬけくんの順序を入れ替える必要がないから、 ふぬけくんに先にゴースさせて、すぬけくんがその後ゴールすれば良い。 よって、一人だけの場合の条件をすぬけくん、ふぬけくんでそれぞれ考える。
\(c > d \) の場合、順序を入れ替える必要がある。順序が入れ替わるのは、
(す)(ふ)(空)
という状態になっている時だから、ふぬけくんの現在いる位置、またはそれより右側で、前後が白マスになっているところを探す。 つまり、三連続で白マスになっている場所を探す。
この時、候補の中で1番左の位置にある三連続白マスを考えれば良い。(状態が実現できなければ、それより右の三連続白マスで実現することは不可能のため)
後は、
(す)(ふ)(空)
の状態に到達できるか確認して、到達できれば、順番を入れ替える必要がない\(c < d \)の場合に帰着できる。 この時、当初の目的地を飛び越えていないかもチェックする。 到達できなければ、実現不可能。