Radio Interference

解説

$A$ の順序は答えに影響しないので、 $A$ は昇順ソートされているとして考える。

$A$ において隣接するラジオ局の周波数の差が偶数であるとき、その平均は正整数であり、混線が発生する。

したがって、混線が発生しないための必要十分条件は、すべての隣接する周波数の差が奇数であることである。

$A$ の要素を $1$ つ変更して混線が発生しないようにできる条件を考える。

$A$ の要素を $1$ つ変更することは、$1$ 要素の削除と $1$ 要素の挿入に分けて考えられる。

$c$：$A_{i+1}-A_i$ が偶数である $i$ の個数

$d$：$A_{i+1}=A_i$ である $i$ の個数

と定義する。混線が発生しないことと $c=d=0$ であることは同値である。

$A$ の要素を $1$ つ削除すること、および $1$ つ挿入することは、それぞれ $c$ の値を高々 $1$ しか減らせない。よって、$c\le 2$ が必要である。

また、$d \ge 2$ なら、$1$ 要素を削除しても $A_i = A_j$ $(i \neq j)$ となる $i, j$ が残るため、$d\le 1$ も必要である。

逆に、$c=0$ なら変更する必要はない。$1\le c\le 2$ かつ $d\le 1$ なら、次のように変更できる。

• $d=1$ なら、重複する要素の一方を削除する。

• $d=0$ かつ $c\ge 1$ なら、差が偶数である隣接する $2$ 要素の一方を削除する。

削除した場合、残った要素はすべて相異なり、$c$ はちょうど $1$ 減るため、$c\le 1$ かつ $d=0$ となる。 $c=1$ なら、差が偶数である隣接する $2$ 要素の間に、左側の要素 $+1$ を挿入すればよい。$c=0$ なら、最大値 $+1$ を挿入すればよい。 いずれの場合も混線が発生しないので、十分性が示された。

すなわちこの条件を満たすか判定することで、 $O(N\log{N})$ でこの問題を解くことができる。