ARC080 C : 4-adjacent(400)
作成日：2017.08.07
最終更新日：2017.08.07
問題概要
長さ$N$の数列$\{a_i\}$を並び替えることで、任意の隣り合う2つの要素の積を$4$の倍数にすることができるか判定せよ。
制約
$2 \leq N \leq 10^5$
$1 \leq a_i \leq 10^9$
$a_i$は整数
考え方
2つの要素の積が$4$の倍数であるかを判定するには、各要素が$2$で割り切れる回数が0回,1回,2回以上であるかが分かれば良い。
$2$で割り切れない要素は、両隣の要素が$4$の倍数でなければならない。
$2$の倍数だが$4$の倍数でない要素は、両隣の要素は$2$の倍数でなければならない。
特に、$2$の倍数だが$4$の倍数でない要素が連続している箇所の両端の要素は$4$の倍数でなければならない。
$4$の倍数である要素は、両隣の要素に関する制約はない。
以上より$2$で割り切れない要素は、$4$の倍数である要素と交互に並べなければならない。
また、$2$の倍数だが$4$の倍数でない要素がある場合は、$2$で割り切れない要素がさらに1つあるとみなせる。
両端の要素の隣は1つしかないので、$4$の倍数である要素は$2$で割り切れない要素(そのようにみなしたものを含む)$-1$以上であれば良い。
ソースコード
マクロ等はこちら
int N;
int x,y,z;
int main(){
scanf("%d" , &N);
repp(i,0,N){
int a;
scanf("%d" , &a);
if(a % 4 == 0) ++x;
else if(a % 2 == 0) ++y;
else ++z;
}
if(y>0) ++z;
printf("%s\n" , x >= z-1 ? "Yes" : "No");
return 0;
}解法まとめ
$4$の倍数である要素、$2$の倍数であるが$4$の倍数でない要素、$2$の倍数でない要素の数$x,y,z$をそれぞれ数える。(6-12行)
$2$の倍数であるが$4$の倍数でない要素があれば、それを$2$の倍数でない要素1つとみなす。(13行)
$x \geq z-1$なら可能である。(14行)