Beautiful Array [CodeChef December Cook-Off 2017 B]

https://www.codechef.com/COOK89/problems/BTAR

N要素の配列Aがある。
1回の操作で「配列の要素を2つ選んで取り除き、その和を挿入する」ことが出来る。
最低何回の操作で配列Aの中身を全て4の倍数にできるか。
もし、できないならば"-1"

解法

まずAの要素はmod4で考えると同じ剰余の要素は同一視してよい。
なので、「cnt[i] := mod4でiとなる数の個数」として数えておく。
これで今後は0,1,2,3から成る数列で考えていこう。
　
出来ない場合を考えてみると全ての総和をとると4の倍数にならない場合はできない。
なので、総和を取って出来ないかを判定しておこう。
　
ここからは貪欲に解いていこう。
1回の操作で4の倍数が作れるのが良い。
2を2つ使うことで4の倍数が作れるので、作れるだけ作っておく。
1と3で4の倍数が作れるので、こちらも、作れるだけ作っておく。
　
これをやると2が1つ余る場合がある。
その場合は1か3の余っている方をくっつけて4の倍数を作ろう。
ここまでやると、1か3しか残ってないので、貪欲にくっつけて答え。

int N, A[101010], cnt[4];
//---------------------------------------------------------------------------------------------------
int solve() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    rep(i, 0, 4) cnt[i] = 0;
    rep(i, 0, N) cnt[A[i] % 4]++;
 
    int sm = 0;
    rep(i, 0, 4) sm += cnt[i] * i;
    if (sm % 4 != 0) return -1;
 
    int ans = cnt[2] / 2;
    cnt[2] %= 2;
 
    int mi = min(cnt[1], cnt[3]);
    ans += mi;
    cnt[1] -= mi;
    cnt[3] -= mi;
 
    if (cnt[2] == 1) {
        if (cnt[1]) {
            ans += 2;
            cnt[1] -= 2;
        } else {
            ans += 2;
            cnt[3] -= 2;
        }
    }
 
    if (cnt[1] == 0) ans += cnt[3] / 4 * 3;
    else ans += cnt[1] / 4 * 3;
 
    return ans;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) printf("%d\n", solve());
}