n-knuu's logs

憧れ駆動。だいたい競プロ

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C. アメージングな文字列は、きみが作る!

Suffix Arrayのライブラリ整備のために解いた

解法

まず、a以外の文字を全てaにできる(つまりa以外の文字がK個以下)ならば、辞書順最小の文字列は、できるだけaの数を少なくするような文字列なので、答えはaがN-K個並んだ文字列である。
それ以外の場合を考えると、辞書順最小の文字列は、操作によって先頭から連続するaの数が最大になるような文字列である。つまり、文字列がどれだけ長くなろうと、全ての文字をaに出来ない限りは先頭から連続するaの数が多くなるものが答えなので、削除の操作には全く意味がない。
よって、文字列の先頭にaを付け加えるか、「前の方」のa以外の文字をaに置換することのみを考えればよい。(厳密にはaを加えるのは先頭でなくてもよく、「前の方」であればよい)

では、a以外の文字をaに置換するような「前の方」というのはどこかというと、これは、実際に先頭からaに置換してみればわかる。
例えば、S=abcabccab, K=4 の場合を考えると、まず、2文字目と3文字目はaに置換すべきである。なぜならこれらをaに置換することによって、4文字目のaを、先頭から連続するaに含めることができるからである。
5文字目以降はどうかというと、これは、置換してもよいし、もしくはその代わりにaを先頭に挿入してもよい。なぜかというと、どう頑張っても、8文字目のaを先頭から連続するaに含めることができず、このSとKの組で先頭から連続するaの数は最大で6にしかできないからである。


よって問題となるのは、「前の方」(上の例のSだと5文字目以降)をaで置換するか、aを先頭に挿入するかのどちらがよいかが問題となる。
ここでは、先頭から連続するaの数は決まっているので、求めたい辞書順最小の文字列は、先頭から連続するa以降で、辞書順最小の文字列を選べばよいことが分かる。
例えば上の例のSだと、答えの候補はaaaaaacab, aaaaaaccab, aaaaaabccab のいずれかであり、cab, ccab, bccabのいずれが辞書順最小であるかを調べればよい(ここではbccab)。

しかしナイーブに調べると、O(|S|^2)かかってしまい、TLEするので、Suffix Arrayを用いる。
Suffix Arrayを用いれば、辞書順最小となるような条件を満たす文字列を(蟻本のコードだと)O(|S| + |S|log^2 |S|)で求めることができるのでC++だと間に合う。

コード


感想

  • 蟻本上級に載ってるような題材だと、考察パートがかなり重いなあという感じだった(実装をバグらせなかったとは言ってない*1 )
  • Suffix Array + LPCのライブラリを整備したいだけなら、今年のKUPCのG問題(ネタバレ注意) なんかがオススメですよ!(宣伝)
  • DDPC改めDDCC、今年のCodeFestival予選みたいな順位をとれば、18卒権を行使して本戦に行けそうな気がするけど、一発勝負+去年事故ってるから怖いから精進したい

*1: