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; }