CodeChef - Little Elephant and Movies

• 問題

制約を見て三乗想定かと思ったら二乗想定だった。

${O}(N^2K)$解

$P_1 \le P_2 \le ... \le P_N$と仮定してよい。また、$f(i) :=$ 映画$i$と同じpriorityを持つ映画の中でもっとも右にあるものの位置、とする。$P_0 = 0$としておくと都合がよい。

$\operatorname{dp}[x][y][z] = x$本映画を見た時点で、今までに見た映画で最もpriorityの高い映画の位置（タイは最初に見たものを優先）が$y$で、現在のexcitingnessがzであるような場合の数

でDPできる。

遷移について。$x < f(y)$ならexcitingでない映画が$f(y)-x$個あって

$$\operatorname{dp}[x+1][y][z] \mathrel{{+}{=}} (f(y)-x)\operatorname{dp}[x][y][z]$$

excitingな映画$y' = f(y)+1, f(y)+2, ..., N$については

$$\operatorname{dp}[x+1][y'][z+1] \mathrel{{+}{=}} \operatorname{dp}[x][y][z]$$

素朴にやると${O}(N^3K)$だが、累積和を取りながら遷移して${O}(N^2K)$。$(P_i)$のsuffixがタイになっている場合に、最後にそれらを全部足す必要があることに注意。

${O}(NK)$解

Editorialを見たら${O}(NK)$想定だった。同じpriorityの映画をまとめて、降順に挿入していけばよい。（リンク先参照）

Myers, Wilf. Left-to-right maxima in words and multiset permutations

discussionに載っていた論文。この問題とわずかに違って同じpriorityの映画は区別できない設定だが、考え方は同じで、区別できるようにするには各priorityの頻度の階乗を掛けるだけ。

よく考えるとこれはDEGwerさんの数え上げPDF（3.探索順の変更）に載っている典型とほぼ同じだった。