ABC113D - Number of Amidakuji

問題

AtCoder Beginner Contest 113 - AtCoder

解法

条件を満たす横線の引き方は他の高さの引き方に影響されないため、各高さ毎に、各縦棒にたどり着けるのは何通りかをDPで求めれば良い。

DPの遷移としては、区間ごとに横線があるような引き方が何通りあるのかを事前に求めておけば、縦線毎に隣へ移動する場合を求めることができる。
また、横線があるような引き方が何通りかがわかれば、横線がない引き方が何通りかも全体から引けばわかるので、隣へ移動しない場合も求めることができる。

区間ごとに横線があるような引き方が何通りあるのかは、であることから、bit全探索によりで求めることができる。

計算量はDPと合わせて、である。

コード

Submission #11155114 - AtCoder Beginner Contest 113

感想

解説を見ずに解けると気持ちが良い。