気づけば簡単だけど本番に気づける気がしない。
https://community.topcoder.com/stat?c=problem_statement&pm=14264
問題
良い文字列とは以下のものを指す。
- "()"は良い文字列である。
- 良い文字列Sがあったとき、それを1回以上繰り返して全体を括弧で囲んだもの"(SS...SS)"もよい文字列である。
- これは一般的なcorrect bracket sequenceの定義と異なる点に注意。
- それ以外はよい文字列ではない。
文字列sが与えられる。
sの部分文字列として得られる良い文字列のうち、辞書順k番目のものを求めよ。
(部分文字列を取り出した結果同じ文字列が複数回登場しても1個とカウントする)
解法
s | ≦150なので、実際に150文字以下の部分文字列を全部列挙してしまおう。 |
そうするとたった163777個しかない。
あとは163777個をソートし、sの部分文字列となるもののうちk個目を答えればよい。
class RepeatedStrings { public: int issubstr(string a,string b) { int x=0; FORR(c,b) if(c==a[x] && ++x>=a.size()) return 1; return x>=a.size(); } string findKth(string s, int k) { vector<string> S; S.push_back("()"); int i,j; FOR(i,S.size()) { string t=S[i]; while(t.size()<=s.size()) { S.push_back("("+t+")"); t+=S[i]; } } sort(ALL(S)); S.erase(unique(ALL(S)),S.end()); FORR(r,S) if(issubstr(r,s)) { if(k--==1) return r; } return ""; } }
まとめ
Div2 Hardならともかく、Div1 Mediumで全列挙で済む問題、逆に盲点で気づきにくそう。