ABC097-C - naoppyの日記

今回はこの問題 C - K-th Substring の解説をしていこうと思います

問題概要

文字列sの異なる部分文字列のうち、辞書順でK番目に小さいものを出力せよ

この問題文は殆どが部分文字列や辞書順の定義についてで、大事なのは最初の2文です。

この問題文を見た時に、まず「異なる部分文字列」というところから、Setの使用を考えましょう。

Java以外の言語には、配列から重複部分を取り除く操作が用意されていることもあるみたいですが、この問題でそれを使うメリットはありません。

常に重複がない状態の方が扱いやすいからです。

制約

文字列長は最大3000
Kは1~5

明らかにKが小さいです。ここが怪しいと気づければいいですね。

~~読み飛ばして爆死はやめましょう~~

解法までの道のり(200点)

異なる文字列→Set、辞書順→Sort　より、TreeSetを使う！とすぐに考えられればいいですね。

まず問題を愚直にやってみることを考えます。

部分文字列の始点をi、終点をjとおきます。

二重forで全て列挙してTreeSetに入れて、K番目を取り出して出力。

これで200点は取れました。

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int k = sc.nextInt();
    TreeSet<String> set = new TreeSet<>();
    for(int i = 0; i < s.length(); i++) {
        for(int j = i; j < s.length(); j++) {
            set.add(s.substring(i,j+1));
        }
    }
    set.stream().skip(k-1).findFirst().ifPresent(System.out::println);
}

解法までの道のり(300点)

愚直にやると、列挙にO(N²)、TreeSetへの挿入にO(logN)、内部での文字列比較にO(N)なので、O(N^3logN)でTLEします。

制約を考えると、Kがとても小さい値だということを利用できないか考えます。

重要なことですが、計算量を落とすためには

探索する範囲を小さくする
探索する方法を改善する

という2パターンがあると思っています。これを頭に置いて、考えていきましょう。

Kは最大でも5です、すると、辞書順の定義より解は最大でも5文字だということがわかります。

どういうことかというと、ABCDEFという部分文字列があるのであれば、A,AB,ABC,ABCD,ABCDEという部分文字列も当然あります。

これらを辞書順に並べると、A<AB<ABC<ABCD<ABCDE<ABCDEFとなるので、5文字を超えると辞書順で必ず6番目以降になるので、制約より解ではありません。

これで探索の範囲がぐっと狭まりました。

自分で試してみたところ、これでACしました。

for(int j = i; j < s.length(); j++)

この部分を

for(int j = i, x = 0; j < s.length() && x < 5; j++, x++)

こう変えるだけです。

結論

制約をよく見ましょう
異なる、辞書順などキーワードからすぐに使うデータ構造などを考える
辞書順などの場合、自分で比較関数を作らない、ライブラリの既存のソート関数で問題ない

自分はさらに、一文字目がaの文字列から見ていくなどの高速化をしようとしましたが、結局意味はありませんでした。

"これくらいなら通る"という計算量の推定がまだまだ甘く、無駄な実装に時間を取られてしまったので反省です。