問題
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; }