Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AGC029-B 「Powers of two」 (600)

atcoder.jp

概要

整数が書かれた N個のボールがある。 i個目のボールには A_iが書かれている。

これらのボールからいくつかのペアを作り、各ペアに書かれた整数の和が2べきとなるようにしたい。最大でいくつのペアを作れるか求めよ。

制約

  •  1 \leq N \leq 2 \times 10^5
  •  1 \leq A_i \leq 10^9

補題

まずは後のために、2べきに関する以下の補題1を示しておく。

  • 各正整数 nについて、 n \lt 2^s \leq 2nなる正整数 sちょうど1つ存在する。

証明

 s = \lfloor \log_2 n \rfloor + 1について、 \log_2 n \lt s \leq \log_2 n + 1より n \lt 2^s \leq 2nが成り立つ。よってこの sが具体的構成となる。

唯一性は 2^{s - 1} \lt n \leq 2^s \lt 2n \leq 2^{s + 1}より成り立つ。  \square

解説

まず残っているボールのうち、書かれている整数で最大のものを Bとおく。このとき、他のボールに書かれている任意の整数 Aについて、 1 \leq A \leq Bが成り立つ。

ここで上の補題から、

  •  A + Bが2べき
  •  1 \leq A \leq B

を満たす Aちょうど1つ存在する( \because A = 2^s - B)。 Aの唯一性から、 Bはこの Aが書かれたボールとしかペアになることはできない。

ここで Aが書かれたボールが存在しなければ、 Bと書かれたボールはペアに使えないので捨てて良い。

もし Aと書かれたボールが存在すれば、貪欲に Bと書かれたボールとペアにするのが最善となる。これはもしそうしなかった場合、 Aの相手を Bに変えることで、元々の Aの相手をフリーにできて自由度が増すからだ。


まとめると、以下のような貪欲法が最適となる。

  1. 残っているボールのうち、書かれている最大の整数を Bとおく。
  2.  A + Bが2べきで、 1 \leq A \leq Bを満たす Aを求める。
  3.  Aと書かれたボールを探す。
    • 存在しなければ、 Bと書かれたボールを捨てて1に戻る。
    • 存在すれば、作れるだけペアを作って1に戻る。

これはmapを使い、「ボールに書かれた整数」と「ボールの個数」をペアにして管理すれば十分高速にシミュレートできる。

実装例

実装は決して軽くないが、かと言ってそれほど重くはならない。

#include <iostream>
#include <map>

using namespace std;

int mypow(int b, int n) {
    if (n == 0) return 1;
    if (n == 1) return b;
    if (n % 2 == 0) {
        return mypow(b * b, n / 2);
    } else {
        return mypow(b, n - 1) * b;
    }
}

// n < 2^kなる最小の2^kを返す
int minbeki(int n) {
    int ret = 1;
    while (n >= ret) {
        ret *= 2;
    }
    return ret;
}

int main() {
    int N;
    cin >> N;

    map<int, int> cnt;
    // key = 書かれた整数, value = ボールの個数

    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        if (cnt.find(a) == cnt.end()) cnt[a] = 0;
        ++cnt[a];
    }

    int ans = 0;

    // cntをkeyが大きい方から見ていく
    for (auto itr = cnt.rbegin(); itr != cnt.rend(); ++itr) {
        int b = itr->first;
        if (cnt[b] == 0) continue;

        int a = minbeki(b) - b;
        // bとペアになりうる整数aを求める

        if (a == b) {
            // bと書かれたボール同士でペアを作る
            ans += cnt[b] / 2;
        } else {
            if (cnt.find(a) == cnt.end()) continue;
            // aと書かれたボールが存在しなければ次へ

            // 少ない方に合わせてペアを作る
            ans += min(cnt[a], cnt[b]);
            cnt[a] -= min(cnt[a], cnt[b]);
        }
    }

    cout << ans << endl;
    return 0;
}

慣れていないとmapを上から見ていく部分にギョッとするかもしれない。 rbegin()rend()は使い方を知っているとたまにお得。

感想

  • 600点にしては難かと思ったが、ここ最近の問題を見るとそうでもないかも。
  • 数学的記述がとても強くて申し訳ない。
    • しかし競プロの考察は数学的記述で書きやすいのも事実。

  1. ちなみにこの補題は「知ってた」ものではなく「その場で気がついた」ものである。