読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Kth Max Subarray(改: Suffix Tree)

https://www.codechef.com/DEC16/problems/KTHMAX

上の問題の一文を削除します。

You are given an array A of size N. Let us list down all the subarrays of the given array. There will be a total of N * (N + 1) / 2 subarrays of the given array. Let us sort each of the subarrays in descending order of the numbers in it.

この問題を解くには Suffix Tree が使えます。Suffix Tree を構築するアルゴリズムとして Ukkonen のアルゴリズムというのが知られています。

原理を理解するのには以下の動画が役立ちました。実際に構築する様子を見てみると、たしかに上手くいくなぁという気持ちになるアルゴリズムです。

Suffix Tree using Ukkonen's algorithm - YouTube

以前から習得したいと思っていたので、ちょうど良かった。