AOJ 2326 : Number Sorting

DP データ構造

問題↓

Number Sorting | Aizu Online Judge

問題概要

  • [A,B]からなる数列が与えられます。
  • それらの数字を任意の数選んで出来る部分数列を
    辞書順ソートしたものと通常のソートをしたものの
    順序が一致するようなものは何通りでしょう？

解法

  • B-A <= 100000 の制約があるのでとりあいず全ての数字を文字列に直してソート
  • 実際の数字の順序でトポロジカルソート的な感じでdpの順序決めをする。
  • dp[i] = i番目までに条件を満たすような部分数列が何通りあるか
  • [A ~ D[i]) までのdpの総和 = dp[i] なのでそこはbitを使って高速化する。 
ソースコード

感想

若干ひねった数え上げは頭良くやろうとすると頭が足りなくてこんがらがるので

とにかく単純なdpを考えてデータ構造で殴るのが良さそう。殴れないのは累積和使うテクとかで頑張るのかな。