🦁

Codeforces Round 993 (Div. 4) D. Harder Problem 貪欲解法

に公開
競技プログラミング
tech

問題:https://codeforces.com/contest/2044/problem/D
(以下の解説はChatGPTによって作成されました)

【解説】配列構築問題の解法 ～出現回数を管理するテクニック～

こんにちは！この記事では、ある配列から条件を満たす新しい配列を構築する問題の解法について解説します。この記事を読めば、コードの意味をスッキリ理解し、自分でも応用できるようになります！

問題設定

入力

  • 配列 a（長さ n）

出力

  • 配列 b（長さ n）：次の条件を満たす
    1. 元の配列 a の要素を参考にしながら構築する。
    2. 配列 b 内の各値の 出現回数が「できるだけ均等」になる。

例えば、次のような入力があった場合：

n = 5
a = [2, 2, 1, 3, 2]

出力する配列 b の例：

b = [2, 2, 1, 3, 1]

解法の全体像

アイデア

配列 b を次の手順で構築します：

  1. 出現回数を管理 しながら配列 a の要素を順番に b に追加。
  2. 出現回数が偏らないように注意（すでに多すぎる値は追加しない）。
  3. 足りない部分は、別の値を使って補完。

解法の詳細手順

1. 出現回数を記録

b に値を追加するとき、その値が「何回出現したか」を管理します。
この情報は map を使って記録します。たとえば、次のような状態を記録します：

cnt[2] = 2  // 値 2 は b に2回出現
cnt[1] = 1  // 値 1 は b に1回出現
cnt[3] = 1  // 値 3 は b に1回出現

2. 最大出現回数を制御

「出現回数が偏らないようにする」という条件を満たすため、現在の「最大出現回数」を記録します（例：ma = 2）。
新しい値を追加するときは、この ma を超えないように調整します。

3. 配列の補完

a の全要素を確認した後、b の長さが n に満たない場合は、別の値を追加して長さを揃えます。このときも、出現回数が偏らないように注意します。

コードの具体例

以下が解法を実装したコードです：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll q; cin >> q; // クエリ数
    while (q--) {
        ll n; cin >> n; // 配列の長さ
        vector<ll> a(n); 
        for (auto &x : a) cin >> x;

        // 出現回数を記録するマップ
        map<ll, ll> cnt;
        vector<ll> b;
        ll ma = 0; // 現在の最大出現回数

        // 配列aを順に見ていく
        for (ll i = 0; i < n; ++i) {
            // a[i] の出現回数が最大回数を超えるならスキップ
            if (cnt[a[i]] >= ma) continue;

            // 最大出現回数に達するまでa[i]をbに追加
            while (cnt[a[i]] < ma) {
                b.push_back(a[i]);
                cnt[a[i]]++;
                ma = max(ma, cnt[a[i]]); // 最大値を更新
            }
        }

        // b の長さが n に足りない場合、補完する
        ll t = 1; // 小さい値から探す
        while (b.size() < n) {
            if (cnt[t] == ma) {
                t++;
            } else {
                b.push_back(t);
                cnt[t]++;
            }
        }

        // 結果を出力
        for (ll x : b) cout << x << " ";
        cout << endl;
    }
}

手順を具体例で確認

入力例

n = 5
a = [2, 2, 1, 3, 2]

配列 b を構築する流れ

  1. 最初の値を追加

    • b = [2]
    • 出現回数 cnt = {2: 1}
    • 最大出現回数 ma = 1

  2. 次の値も追加（まだ制限に達していない）

    • b = [2, 2]
    • 出現回数 cnt = {2: 2}
    • 最大出現回数 ma = 2

  3. 次の値（1）を追加

    • b = [2, 2, 1]
    • 出現回数 cnt = {2: 2, 1: 1}

  4. 次の値（3）を追加

    • b = [2, 2, 1, 3]
    • 出現回数 cnt = {2: 2, 1: 1, 3: 1}

  5. 最後の値は追加せず、補完

    • 配列の長さが足りないので、1 を追加：
      • b = [2, 2, 1, 3, 1]

結論

この解法では、「出現回数を管理するテクニック」 を使って、条件を満たす配列を効率的に構築しています。
ポイントは以下の3つ：

  1. 出現回数を map で管理する。
  2. 最大出現回数を制御して、偏りを防ぐ。
  3. 足りない部分は適切に補完する。

この方法は、配列操作に限らず、他の問題にも応用できます！ぜひ試してみてください！ 😊

Discussion