ARC080 - C: 4-adjacent

問題

正の整数列が与えられる。数列を並び替えて隣り合う値を全て4の倍数にすることは出来るか


解答

数列の値について、興味あるのは2の因数の数のみである。 また、2の因数が2つ以上ある場合は、両隣の値に対して2の因数が2つの場合と同等なので、 値の状態は2の因数が0, 1, 2個の3つのうち何れかとなる。順に、(0)(1)(2)の値と表現する。

(0)の値は、隣接する値が(2)であるような制約の厳しい値であるので、(0)の扱いから考える。 はじめに(0)を置いた時、次に(2)を置くしかない。(0)をできるだけ消費してしまいたいので、これを繰り返すと以下のようなケースが考えられる。

  1. (0)(2)(0)(2)…(0)
  2. (0)(2)(0)(2)…(2)

1のケースは、(0)(2)を繰り返した結果末尾が(0)で終わるものである。このとき(1)は0個である必要がある。 2のケースは、(0)より(2)の数のほうが多かった場合である。この場合末尾の(2)の後に、任意回数(1)または(2)を置いて良い。(1)は(1)または(2)を両隣に置くことが出来るからである。

よって、以下の3パターンが答えとなる。

  1. (0)(2)(0)(2)…(0) -> Yes
  2. (0)(2)(0)(2)…(2) + 末尾に(1)または(2)が並ぶ -> Yes
  3. それ以外 -> No