人権なし

青コーダーの競プロで解いた問題や開発の進捗などの記録です

ARC097 : C - K-th Substring

  • 問題

C - K-th Substring

文字列 s の部分文字列の重複を除いたうち、K 番目に小さいものを答える問題。

 

  • 解法

全ての部分文字列を列挙していては O(|s|^3) となり間に合わないので、工夫する。s の各文字から長さ 1~K のものが答えの候補となるので、O(|s|) に落とせる。

 

  • 解答

f:id:babcs2035:20180608164831p:plain

f:id:babcs2035:20180608164834p:plain

Submission #2633737 - AtCoder Regular Contest 097