ARC #080 C
\(\{ a_i \}\) を次の3つのグループに分ける.
- (1) 4 で割り切れる
- (2) 2 で割り切れるが4では割り切れない
- (3) 2 で割り切れない
(3) の隣は (1) でなければならない. また, (2) の隣は (1) か (2) でなければならない.
それぞれのグループの要素数を \(N_1, N_2, N_3\) とすると, 条件が成り立つように並べるためには以下のいずれかでなければならない.
- (2) が存在しないときは, (3)(1)(3)(1)… とならべていい. すなわち, \(N_2 = 0 \land N_3 \leq N_1+1\)
- (2) が存在するときは, (2)(2)…(2)(1)(3)… と並べられる. すなわち, \(N_2 \gt 0 \land N_3 \leq N_1\)