POJ 3378: Crazy Thairs

問題

長さがNの数列が与えられる。その数列の長さ5の部分列で狭義単調増加するものの個数を答えよ。

制約条件

1 <= N <= 50000

解法

まず、答えがどのくらい大きくなるかを考えます。答えが一番大きくなるのは1, 2, 3, …, 50000の時で、その時の解は_{50000} C_5 \approx 2 \times 10^{31}になるので、64bit整数でも収まりません。

なのでおとなしく多倍長演算を書きます。今回は足し算だけあればいいと思います。

つづいて、問題の本題に入っていきますが、解き方は端的に言うとDPです。

DP表は
dp[i][j] = i番目の数が最後に来る狭義単調増加部分列で長さがjになるものの数
というように持ちます。

更新するときは、自分より小さな番号かつ、自分より小さな数が最後に来る部分列の長さが1増えることになるので、
dp[i][j+1] = sum { dp[k][j] where Ak < Ai and k < i }
となります。

このように2種類の順序を扱う時はBITが定番なので、今回もBITを使います。

与えられた数列を数が小さいものから順に処理していきます。処理の過程では数が自分より小さいものしかBITに入っていないので、添え字番号の大小だけを考慮し、BITを用いた和を計算します。

このときポイントは、数が同じものは添え字が大きい順に処理しないといけないということです。

例えば 1, 2, 3, 4, 5, 4, 5 という数列の答えは3ですが、添え字が小さい順に処理してしまうと、一番後ろの5を処理するときに、その前に出現している5の時に計算した値が数えられてしまいます。

多倍長演算があるのでかなり実装は重めでした。Submit何回したかなぁ(笑)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です