C: 4-adjacent - AtCoder Regular Contest 080

arc080.contest.atcoder.jp

数列a[i]が与えられる。並び替えて隣同士の積がかならず4の倍数にするようにできるか判定せよ。

数列の要素を p:4の倍数、q: 偶数であるが4の倍数でないもの、r: それ以外に分類する。 rの隣には必ずpの要素が必要である。また、qは q同士で並ぶ or pのとなりにいることが必要であるが、要はqの数が奇数であった場合のみ、pが1個必要になる。よって、r + q % 2 <= p であればYESである。ただし、qが存在しない時はrprprprみたいに並べることが可能なので、r + 1 <= p であればYES。