No.069 C

$a_i$ を以下のようにグループ分けする.

• 奇数
• 2の倍数かつ4の倍数でない (以下2の倍数と表す)
• 4の倍数

こうすると, 条件を満たすためには次の並べ方をするのが最適である.

• 2の倍数を先頭から並べる.
• その後, 4の倍数, 奇数, 4の倍数, 奇数の順に並べる. ただし, 2の倍数がない場合は, 奇数, 4の倍数, 奇数, 4の倍数の順に並べるのも可.

よって, 目標を達成できる条件は, 各グループの個数を $C_{odd}, C_{mul2}, C_{mul4}$ とすると,

• $C_{mul2} \gt 0$ ならば, $C_{odd} \leq C_{mul4}$
• $C_{mul2} = 0$ ならば, $C_{odd} \leq C_{mul4}+1$

となる.