B1 - Wonderful Coloring - 1

問題

https://codeforces.com/contest/1551/problem/B1 (新しいタブで開く)

問題文

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

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

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

制約

• $1 \le t \le 1000$
• $1 \le |s| \le 50$

サンプル

5
kzaaa
codeforces
archive
y
xxxxxx

2
5
3
0
1

考察

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

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

2 回以上出てくる文字の種類数を $x$ 、1 回しか出てこない文字の個数を $y$ とすると、答えは $x + \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;
}