けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #586 (Div. 1 + Div. 2) D. Alex and Julian (R1900)

すごく面白かった

問題へのリンク

問題概要 (表現改)

 N 個の正の整数  a_1, a_2, \dots, a_N が与えられる。これらから最小個数を取り除いて、以下の条件を満たすようにせよ。

  • 残った整数から重複を許して奇数個選ぶどのような方法に対しても、選ばれた整数を 2 つに分けてそれぞれの総和が等しくなるようにはできない

制約

  •  1 \le N \le 200000

考えたこと

こういう問題はいろいろなケースを試して様子をつかむのが良さそう!

まずは  a がすべて奇数だったならば、それらから重複を許して奇数個選んだときに、それを足したり引いたりした結果は必ず奇数なので 0 にはできない。ゆえに、「すべて奇数」は整合する。

反対に  a の中に偶数  2m と奇数  2n+1 が混在していたならば、 2m 2n+1 個選び、 2n+1 2m 個選ぶ方法がダメなのでダメ。

以上から問題は  a がすべて偶数の場合に限られた。

2 で何回割れるか

 a = (18, 30) のようなケースでは、2 で割ると結局は  a = (9, 15) の場合と一緒である。よって  a = (18, 30) は条件を満たす。

一方で  a = (12, 18) のようなケースでは、2 で割ると結局は  a = (6, 9) の場合と一緒である。これは偶数と奇数が混在するので条件を満たさない。

以上のことを考えると、各  a_1, a_2, \dots, a_N に対して「2 で何回割れるか」がポイントになりそうであることがわかる。もしすべて 2 で割れる回数が等しいならば、その回数割ることですべて奇数になるので OK。しかし 2 で割れる回数が異なるとき、その回数の最小値の分だけ割ると「偶数と奇数が混ざった状態」になるのでダメ

まとめ

以上から、条件を満たす必要十分条件は「2 で割れる回数が等しい」ことであることがわかった。

よって、 a_1, a_2, \dots, a_N に対してそれぞれ 2 で割れる回数を求め、その値が最も多いところを残して消せばよい。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    vector<long long> nums(N, 0);
    vector<long long> count(100, 0);
    for (int i = 0; i < N; ++i) {
        int d = 0;
        long long A = a[i];
        while (A % 2 == 0) {
            ++d;
            A /= 2;
        }
        nums[i] = d;
        count[d]++;
    }
    
    long long ma = 0;
    int ima = -1;
    for (int i = 0; i < 100; ++i) {
        if (ma < count[i]) {
            ma = max(ma, count[i]);
            ima = i;
        }
    }
    
    cout << N - ma << endl;
    for (int i = 0, j = 0; i < N; ++i) {
        if (nums[i] != ima) {
            if (j) cout << " ";
            cout << a[i];
            ++j;
        }
    }
    cout << endl;
}