kojingharangの日記

SRM 589 Div1 250 GooseTattarrattatDiv1

22:33 |

• 文字列が与えられる。文字の置換を文字列全部に対して何回か行う。文字列が回文になるように置換するとき、置換する文字数の最小値を求める問題。
• 1≦N≦50

• 何と何と何を同じ文字にすると良いかを union-find で求める。geese なら g-e, e-s ということで g-e-s を同じ文字にすればいい。
• それぞれのグループについて、どの文字に統一するかを決める。文字列における文字の出現回数が多いものに合わせるとコスト最小。

• accepted

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool Union(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool Find(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

class GooseTattarrattatDiv1 {
	public:
	int getmin(string S) {
		UnionFind uf(26);
		int N=S.size();
		REP(i, N/2) {
			uf.Union(S[i]-'a', S[N-1-i]-'a');
		}
		map<int, int> vis;
		int ans = 0;
		REP(i, 26) {
			int root = uf.root(i);
			if(vis[root]) continue;
			vis[root]=1;
			string same;
			VI cnt;
			REP(j, 26) {
				if(root==uf.root(j)) {
					same+=string(1, 'a'+j);
					int ct=0;
					REP(k, N) if(S[k]=='a'+j) ct++;
					cnt.PB(ct);
				}
			}
			//cout<<string(1, 'a'+i)<<" "<<same<<" "<<cnt<<endl;
			if(same.size()==0) continue;
			sort(ALLR(cnt));
			ans += accumulate(ALL(cnt), 0)-cnt[0];
		}
		return ans;
	}
};

ツイートする