E. Binary Strings and Blocks
包除原理を使う問題にしか思えなかったけど、違ったようでびっくり。
正しい解法は、DPでした。
最後に色が変わった箇所がiとしたときの塗り方の個数をDP[i]とすると、[l,r]の条件から、次にどこまでで色が変わらなくてはいけないのか？ が分かるので、そこまで一気に（セグ木などを使い）加算していく。
言われてみれば自然なDPだけど、1マス1マス決めていくことしか考えていなかったせいか、全く思いつかなかった。
何個条件に違反しているか？ という包除原理を考えていたけど、これだと、ある区間と別の区間に交わりがあったとき、両方に違反しているか？ などを上手く数えられないので上手くいかないのですね。
0 件のコメント:
コメントを投稿