ARC097 C : K-th Substring(300)

作成日:2018.09.24
最終更新日:2018.09.24

問題概要

問題本文

 文字列$s$の異なる部分文字列のうち、辞書順で$K$番目に小さいものを求めよ。
制約
$1 \leq |s| \leq 5000$
$1 \leq K \leq 5$

考え方

 部分文字列は$O(|s|^2)$種類あるから、すべての部分文字列をソートするような方法では間に合わない。 そこで$K$が小さいことをうまく使えないかを考える。 $K=1$の時、答えは$s$に含まれる文字の中で辞書順最小であるものである。 $K=2$の時の答えは、それに$1$文字加えた文字列か$s$に含まれる文字の中で辞書順で$2$番目のものである。 同様に考えると、辞書順で$K$番目に小さい文字列は$K$文字以下になることが分かる。 すなわち調べる部分文字列は$O(NK)$個で良く、これらをソートすることにより答えを求めることができる。

ソースコード

マクロ等はこちら

int main(){
	string s; cin >> s;
	int K; cin >> K;
	set<string> solve;
	repp(i,0,s.size()) repp(j,1,6) solve.insert(s.substr(i,j));
	auto ans = solve.begin();
	repp(i,1,K) ++ans;
	cout << *ans << endl;
	return 0;
}

解法まとめ

 $5$($\geq K$)文字以下の部分文字列すべてを、重複をなくすためにsetに入れてソートする。 このようにした時の$K$番目の要素が答えとなる。(4-8行)

ARC097の他の問題 D E F

広告

自己紹介

プログラミングとかUTAUとかドット絵とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告