mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ POJ suffix array まわりの問題をあんまり解いたことがないので解いてみました。蟻本のやつです。 問題 3581 -- Sequence 解法 蟻本 338 ページに書いてある通りです。最初の区切りは「一番大きい数が一番前にある」という制約から, 数列を逆順に見た時の接尾辞で辞書順最小のものを選べば良いことがわかります。これはよくある suffix array ですね(ただし, 「各部分は空であってはいけない」という制約から, 最初に区切るべき位置 p1 は, N-p1 >= 2 を満たさなければならないことに注意)。残りの部分を 2 つに分けたいです。別れた時の各数列が p, q で, … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2016%2F04%2F04%2F195930" title="POJ 3581: Sequence - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2016-04-04 19:59:30 rich https://mayokoex.hatenablog.com/entry/2016/04/04/195930 1.0 100%