はまやんはまやんはまやん

hamayanhamayan's blog

4-adjacent [AtCoder Regular Contest 080 C]

http://arc080.contest.atcoder.jp/tasks/arc080_a

解説

http://arc080.contest.atcoder.jp/submissions/1485220

  • A「4の倍数」
  • B「4の倍数でなく2の倍数」
  • C「2の倍数でない」

の3種類で分類して、考えれば良い。
ダメなパターンから考えてみると、Cの扱いに困ることが分かる。
Cの両端はAである必要がある。
そのため「Cの個数 <= Aの個数」である必要がある。
これが満たされれば作れる。
 
しかし「Cの個数 + 1 == Aの個数」であっても作れる場合がある。
それは、「Aの個数 + Cの個数 == N」のときである。
この場合に「CACAC」となり作れる。

int N, A[201010];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    int c2 = 0;
    int c4 = 0;
    int c = 0;
 
    rep(i, 0, N) {
        if (A[i] % 4 == 0) c4++;
        else if (A[i] % 2 == 0) c2++;
        else c++;
    }
 
    if (c4 + 1 == c && N == (c4 + c)) return yes;
    if (c4 < c) return no;
 
    return yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cout << solve() << endl;
}