ARC104 C - Fair Elevator
問題
解法
まず、各階に、乗った階が指定されている場合はを、降りた階が指定されている場合は
をマークする（
、
は階数と被らない何かしらの数）。
ただし、どちらも指定されている場合は、乗った階に降りた階をマークする。
このとき、以下の場合はNoとなる。
- 同じ階が指定されている。
- 乗った階より降りた階の方が下にある。
次に、下の階から順に、乗り降りした階を対応させていく。
現在の階をとし、対応する可能性のある階を
とすると、
であり、この範囲を全探索すれば良い。
ここで、と
を対応させた場合、
とすると、
において、
と
は制約上対応しなければならない。
つまり、これらが対応できる場合、次に探索するのは
階からとなる。
ただし、以下の場合は
と
を対応することはできない。
（
と対応する階がない）。
がマークされているが、
である。
がマークされている。
に
や降りた階がマークされている。
最後に、ある対応付けが上手くいった場合はYesである。
上手くいかなかった場合は、探索開始が同じであれば結果は同じとなるので、メモしておく。
よって、動的計画法の考え方に帰着された。
計算量は（恐らく）である。
コード
Submission #17181371 - AtCoder Regular Contest 104
感想
場合分けが多いと厳しい。
