水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

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