「競プロ典型 90問」Smallest Subsequence (最小部分列問題)

最小部分列問題 「 競プロ典型 90 問」の 006 - Smallest Subsequence（★5） (最少部分列問題) という問題を解いてみたのですが、最初は解説をみてもさっぱり分からず打ちひしがれていました･･･。 が、けんちょんの競プロ精進記録 を見るに、どうもこの問題を解く途中で出てくる nex という配列が「極めて汎用性が高いので、実にさまざまな問題で活用できます！！！」ということらしく、ちゃんと理解しといた方が良さそうだ･･･ということで気を取り直して取り組んでみたところなんとか理解できました。 せっかくなので忘れないうちに解説記事を作って記憶を定着させたいと思います。なお後半の実装パートは、Haskell で実装します。 けんちょんさんの解説記事にあるとおり、この問題 (を全探索で解く場合) の解法のキーになるのは事前に「任意の文字が i 番目以降に出現する位置」を二次

[hase0510]

id:naoyaさんが典型90やってる〜。ぼくはセグ木でやりました。文字とインデックスのタプルを載せて、[最後に選んだ文字+1, Sの長さ−残り文字数)の範囲でminを取るのをK回繰り返せばOK。

[razokulover]

“文字列Sのi文字目以降で、文字cが出現する（最初の) インデックス」を探すためのデータ構造ですが、二次元配列を事前に構築しておく･･･というのが定番の方法のようです。”