ARC080 - C: 4-adjacent

問題

C: 4-adjacent - AtCoder Regular Contest 080 | AtCoder

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

• 
• 

解説

2で割り切れない数の影響を低くしたいので、これらを数列の両サイドから置いていく。 すると、2で割り切れない数の隣に、4で割り切れる数を隣においていく形になる。 の偶奇で、数列の中心の条件が判定が異なる。2で割り切れる数は無害。

int main() {
  int N; cin >> N;
  int F = 0, K = 0;
  rep(i, N) {
    int a; cin >> a;
    if (a % 4 == 0) F++;
    if (a % 2 == 1) K++;
  }

  if (N % 2) {
    cout << (K - 1 <= F ? "Yes" : "No") << "\n";
  } else {
    cout << (K <= F ? "Yes" : "No") << "\n";
  }
}

以前書いた解説

数列の値について、興味あるのは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