POJ 1769 Minimizing maximizer

データ構造を工夫しないと通らない、かといって典型的なデータ構造を探してきて適用すれば良いわけではない。どうにかオーダーに間に合うように工夫するのが楽しかった問題。

長さn (2 <= n <= 50000)の任意の数列を入力として、最も大きな数を出力する機械(Maximizer)を作りたい。ただし部品として使える道具は、ある区間[i, j] (1 <= i, j <= n) を昇順ソートしてくれる機械(Sorter)だけ。何段かこのSorterを重ねる事でMaximizerを作る。例えばn=10の場合だと[1, 10]のSorterが一つあれば良いし、[1, 5]のSorterの下に[5, 10]のSorterがあっても良い。

問題は、ある完成品のMaximizerが与えられているとき、無駄を省いて最小いくつのSorterでMaximizerが実現できるか答えよというもの。与えられるSorterの数はm(1 <= m <= 500000)。もちろんSorterの順序を入れ替えてはいけない。n=10の場合[1, 5] -> [3, 6] -> [5, 10]は[1, 5] -> [5, 10]に出来るので答えは2。

右端に数列の最大要素が移動しさえすれば良いので、要は上から下に選んだSorterを見ていった時に、左端から右端へ連続して移動できれば良い。f(i)を「ある位置iに最大要素を移動させるための最小コスト(Sorterの数)」として更新していけば答えが求まるので、典型的なDPと言えばそうなんだけれど、問題は最小コストを保持するデータ構造。

int dp[n];  // dp[i] = 位置iへ最大要素を移動させるための最小Sorter数

のようにしてしまいたくなるが、nの更新をm回繰り返すと50000*500000=250憶になってTLE。ここは次のような構造体をsetに入れて更新してゆくことでdpの代用とするのが正解(なのかは分からないがぎりぎり間に合った)。

struct S {
  int l;  // 区間の左端
  int r;  // 区間の右端
  int cost;  // 区間の最小コスト
  bool operator<(const S& s) const {
    return l < s.l;
  }
};

初めにsetには(S){1, n, INT_MAX}を入れておく。各段階では新たなSorterによって更新可能な範囲を書き換えていく。要はdpの区間を圧縮したようなもの。新たなSorterで更新可能な範囲の右端と左端の検索はlog(n)程度で済むし、区間はプログラムの実行全体でO(m)ほどしか生成されないので、setの各区間を更新していってもO(m*log(n))の時間で済む。
計算量の考察とそこそこの実装を求める良い問題でした。