問題概要

問題URL

長さ$N$の数列$a = (a_1, a_2, \ldots, a_N)$が与えられる．
$a$の要素を自由に並べ替えることで以下の条件を満たせるか否か．

  • $a_{i}$と$a_{i + 1}$の積が4の倍数． $\forall i \in [1, 2, \ldots, N - 1]$

制約

  • $2 \leq N \leq 10^5$
  • $a_i$は自然数
  • $1 \leq a_i \leq 10^9$

考えたこと・解法

数列内の任意の連続する要素が4の倍数になる必要がある． $a_i$と$a_{i + 1}$の積が4の倍数になるのは

  • $a_i$と$a_{i + 1}$の少なくともいずれかが4の倍数
  • $a_i$と$a_{i + 1}$の両方が4の倍数ではないが2の倍数 のいずれかを満たす必要がある．

問題になるのは要素の配置方法で，4の倍数を用いる場合はもう一方の要素は 任意の自然数を用いることができるので例えば

1 4 1 4 1

のような配置が可能． このことから4の倍数の個数$n_4$に対してその他の自然数の個数$n_1$が \begin{align} &n_1 \leq n_4 + 1 \end{align} を満たしていれば$a_i$と$a_{i + 1}$の積が必ず4の倍数になる．

4の倍数ではないが2の倍数を用いる場合はもう一方の 要素も2の倍数である必要があるので

2 6 2 6

と連続している必要があり，2の倍数以外と連続させることができない． したがって，4の倍数ではないが2の倍数は偶数個をまとめて連続させることで 4の倍数を用いなくても$a_i$と$a_{i + 1}$の積が4の倍数になる． もし奇数個ある場合は余った1個をその他の自然数の個数$n_1$に追加して 式(1)の判定を行えばよい．

コード

// https://beta.atcoder.jp/contests/abc069

#define SUBMIT

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

void print_yes_no(bool cond, string yes = "Yes", string no = "No") { cout << (cond ? yes : no) << endl; }

int main() {
#ifdef SUBMIT
    auto& stream = cin;
#else
    stringstream stream(R"(6
2 7 1 8 2 8
)");
#endif
    int mul4 = 0, mul2 = 0, mul1 = 0;
    int n;
    stream >> n;
    for (int i = 0; i < n; ++i) {
        int a;
        stream >> a;
        if (a % 4 == 0) mul4++;
        else if(a % 2 == 0) mul2++;
        else mul1++;
    }

    mul1 += mul2 % 2;
    print_yes_no(mul1 <= mul4 + 1);
    return 0;
}