問題概要

$N$ 個の正の整数からなる数列 $a_{1}, a_{2}, \dots, a_{N}$ が与えられる。

この数列の項を適切に並び替えることによって、「どの隣接する 2 項の積も 4 の倍数」となるようにできるかどうかを判定せよ。

制約

$2 \le N \le 10^{5}$
$1 \le a_{i} \le 10^{9}$

考えたこと

各数が 2 以外の素数によって割り切れるかどうかはまったく関係がないことに注意しよう。そうすると、各数は次の 3 種類に類別して考えるとよさそうである。

A：4 の倍数
B：4 の倍数ではない偶数
C：奇数

A は、自身が 4 の倍数である上に、B や C とくっつけることによって、B や C が単体では 4 の倍数でないのを補うことができる。B や C は、A と隣接する必要がある。B と C の違いは「B は B 同士でくっついてもよい」という点だ。

ルールを整理すると、

A は、A と隣接してもよいし、B や C と隣接してもよい
B は、B と隣接してもよいが、C と隣接してはいけない
C は、A 以外と隣接してはいけない

と整理できる。総じて、基本的には「A を用いて、B や C をサポートしていく」ことを考える問題だと言える。

B は一箇所にまとめてよい

さらに考察を深めよう。まず、B は一箇所にまとめてくっつけるのが良いということが言える。B が離れていると、その分、より多くの A を必要としてしまうからだ。

そして、B をすべてくっつけてしまえば、それらの塊をまとめて C とみなしても変わらない。なぜならば、「B の塊」も C も結局、自身が左端や右端でない限り、A と隣接させる必要があるからだ。

つまり、A が $a$ 個、B が $b$ 個、C が $c$ 個あるとすると、

$b \gt 0$ のとき、A が $a$ 個、C が $c + 1$ 個あるという問題
$b = 0$ のとき：A が $a$ 個、C が $c$ 個あるという問題

へと帰着された。改めて、帰着後の A, C の個数を $p, q$ としよう。

帰着された問題

最終的に、次の問題となった。

$p$ 個の A と、 $q$ 個の C を並べたい。ただし、C 同士は隣り合ってはならない。

そのように並べることは可能か？

これはよく知られた問題で、

$p \ge q + 1$ のとき：可能（C を $q$ 個並べたあとで隙間に A を入れていき、残った A は適当な場所に入れる）
$p \lt q + 1$ のとき：不可能（C と C の隙間は $q-1$ 箇所あり、すべてを潰すことはできない）

と整理できる。

コード

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

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

    int two = 0, one = 0, zero = 0;
    for (int i = 0; i < N; i++) {
        cin >> a;
        if (a % 4 == 0) two++;
        else if (a % 2 == 0) one++;
        else zero++;
    }
    if (one > 1) one = 1;

    if (two >= zero + one - 1) cout << "Yes" << endl;
    else cout << "No" << endl;
}