問題
https://codeforces.com/contest/1551/problem/B1 (新しいタブで開く)
問題文
文字列が与えられる。文字列を以下の条件を満たすように塗る。
- 各文字は、どれか 1 つの色で塗られているか、もしくは塗られていない状態にする。
- 同じ色で塗られている文字は、互いに異なる。
- 各色で塗られている文字数は同じ。
- 上記条件を満たすよう、塗られている文字数を最大化する。
2 色で塗るとき、最大でそれぞれ何文字塗れる?
制約
サンプル
5
kzaaa
codeforces
archive
y
xxxxxx
2
5
3
0
1
考察
文字の出現回数を数える。
2 回以上出てくる文字は、2 色で塗る。
1 回しか出てこない文字は、1 色ずつ同じ個数塗ればいい。
2 回以上出てくる文字の種類数を 、1 回しか出てこない文字の個数を とすると、答えは 。
コード
https://codeforces.com/contest/1551/submission/123482676 (新しいタブで開く) (最初に書いたコード)
void solve() {
string s;
cin >> s;
if (s.size() < 2) {
cout << 0 << endl;
return;
}
map<char, int> mp;
loop(i, s.size()) {
mp[s[i]]++;
}
ll ans = mp.size();
loop(i, s.size()) {
if (mp[s[i]] >= 2) {
ans++;
mp.erase(s[i]);
}
}
ans /= 2;
cout << ans << endl;
}
https://codeforces.com/contest/1551/submission/183320070 (新しいタブで開く) (B2 も見据えたコード)
void solve() {
string s;
cin >> s;
vector<int> cnt(26, 0);
rep(i, s.size()) cnt[s[i] - 'a']++;
int ans = 0;
int odd = 0;
rep(i, 26) {
if (cnt[i] >= 2) ans++;
if (cnt[i] == 1) odd++;
}
ans += odd / 2;
cout << ans << endl;
}