Asa's Website

B1 - Wonderful Coloring - 1

cpcodeforcesdiv3greedystring

最終更新日

Table of Contents

Loading...

問題

https://codeforces.com/contest/1551/problem/B1

問題文

文字列が与えられる。文字列を以下の条件を満たすように塗る。

  1. 各文字は、どれか 1 つの色で塗られているか、もしくは塗られていない状態にする。
  2. 同じ色で塗られている文字は、互いに異なる。
  3. 各色で塗られている文字数は同じ。
  4. 上記条件を満たすよう、塗られている文字数を最大化する。

2 色で塗るとき、最大でそれぞれ何文字塗れる?

制約

サンプル

5 kzaaa codeforces archive y xxxxxx
2 5 3 0 1

考察

文字の出現回数を数える。

2 回以上出てくる文字は、2 色で塗る。
1 回しか出てこない文字は、1 色ずつ同じ個数塗ればいい。

2 回以上出てくる文字の種類数を xx 、1 回しか出てこない文字の個数を yy とすると、答えは x+y2x + \lfloor \frac{y}{2} \rfloor

コード

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