SRM563 Div1 Easy - FoxAndHandle
問題
長さn(:偶数)の文字列sが与えられる
sを2つの文字列x,yに分け、yがxのアナグラムになっているようにしたい
xとしてあり得る文字列のうち辞書順最小のものを求めよ
2 <= n <= 50
xとしてあり得る文字列が少なくとも1つは存在することが保証される
解法
1文字ずつ決めていく
今の仮の答えである文字列の各文字をsのなるべく左に対応させてみて、左からsを見た時にそれらが全て登場するまでにある文字が (sで登場する回数)/2+1 回以上登場したらダメ
(そうなった場合答えの残りの文字を決めきれない)
そうでなければok
↑史上最高にわかりにくい説明
コード↓の方がまだわかりやすいと思う
class FoxAndHandle { public: string lexSmallestName(string s) { int n = s.size(), a[26] = {}; each(i,s) a[i-'a']++; rep(i,26) a[i] /= 2; string res; rep(m,n/2) rep(c,26){ res.push_back('a'+c); int ok = 1, x[26] = {}, y[26] = {}, id = 0; rep(i,n) { if (s[i]==res[id]) { if (++x[s[i]-'a']>a[s[i]-'a']) ok = 0; if (++id==res.size()) break; } else if (++y[s[i]-'a']>a[s[i]-'a']) ok = 0; } if (ok) break; res.pop_back(); } return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12331&rd=15185