ARC Wrecker 2 を複素数を用いて数学的に一般化する

　[C - ARC Wrecker 2](https://atcoder.jp/contests/arc119/tasks/arc119_c)

　このような問題があります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/28972d7f-b411-72fb-5135-2100cd475fea.png)

　ある連続した棒グラフが与えられた時に、隣り合った 2 つの区間を隆起・沈降させることによってすべての高さを 0 にできる区間はいくらあるかという問題です。$[3,3]$ は自明に可能ですし、上記の例の通り $[11,3,3,13,2]$ も可能です。

# 愚直解

　例えば、区間の長さが 2 だった場合、いくつなら可能でしょうか。高さが A,B として、これは当然 $A=B$ の時です。

　長さが 3 ならどうでしょうか。高さが A,B,C として、以下のような変遷をたどります。

1. $A,B,C$
1. $0,B-A,C$
1. $0,0,C-(B-A) = C - B + A$

　すべてを 0 にできる時、最後の「皺寄せ」が 0 である必要があるので、条件は $B=A+C$ となります。

　この考えを延長すると、**隣り合う高さをジグザグに足したり引いたりしてその合計が 0 になる区間は可能**ということになります。これをすべての区間に対して計測すれば答えは出ますが、すべての区間を列挙するのに二重ループ、更にシミュレーションに一重ループが必要なので、$O(N^3)$ の計算量が必要になり、余裕で時間オーバーします。高速化が必要です。

# 高速化

　ここで活躍するのが**累積和**です。予め左から各要素の累積和を求めておけば、それを足し引きすることによりすべての区間和を高速で計算することができます。上記の例だと累積和は以下のようになります。

- $[12,8,11,3,3,13,2]$（元の配列）
- $[0,12,4,15,12,15,2,4]$（左からのジグザグ累積和）

　これを見ると、累積和が「15のペア」「4のペア」が条件を満たすことがわかります。それぞれ元の配列の区間で言うと $[3,3]$、$[11,3,3,13,2]$ にあたります。

　実は問題的には現時点でも $O(N^2)$ で時間オーバーしてしまい、更なる高速化が必要です。要は、同じ数が出てくればそれらの間でペアを組めるのですから、ある数が出てくる頻度だけを数えればよいです。連想配列でカウントした後に $_nC _2$ を計算したり、連想配列や fenwick tree で要素をカウントしながら足していったりすることによって、より高速に求めることができます（$O(N\log{N})$）。

# 本質

　解説にはエレガントな †本質† が載っていまして、

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/240e591f-84c9-7358-e07f-f6705eba56ec.png)

　操作によって、**奇数番目の和と偶数番目の和の差が変わらない** ことがわかります。最初の考察で述べた「ジグザグの累積和」はこのような性質から導かれることがわかります。

# 操作区間が 3 だったら？

　ここで、次のような疑問が湧きます。

「操作区間が 3 だったら？」

　上記の本質を考えると、すぐに「操作によって $0 \bmod 3,1 \bmod 3,2 \bmod 3$ の高さの合計の差は変わらない」ことが考察できます。例えば $[1,3,3,2] = [1,1,1,0] + [0,2,2,2]$ は条件を満たしており、これは $1+2=3=3$ により判別できます。

　しかし、これを累積和で高速化することはできるでしょうか？

　そもそも操作区間が 2 の時に累積和で高速に求められたのは、

「2 種類の数値が同じである $\Leftrightarrow$ 差（引き算）が0になる」

　という推論が成り立ったからです。3 種類以上になると、これは成り立ちません。次善策として、実数同士の演算からベクトル同士の演算に拡張して、

「3 種類の数値が同じである $\Leftrightarrow$ 3 次元空間上でのベクトルが $t\cdot(1,1,1)$ で表現できる」

　という条件にすれば同様の判別はできますが、これだと区間長に応じてどんどん次元を拡張していく必要があります。なんかスマートではありませんし、区間長に応じた計算量の増大を招きます。

　操作区間長 2 の時はうまくジグザグに処理できたのですから、もっと何かこう、上手い方法がありそうです。

　2 の時はうまくジグザグにできる......この状況には何か見覚えがある......

　そう、**複素数** ですね。

# 複素数への拡張

　ここで、操作区間長p に対する mod を複素数平面上に対する角度 360°を分割したものと考えます。$p=2$ の時は 0°、180°、360°、540°... と繰り返すので、実数軸上のプラス、マイナス、プラス、マイナス... となります。

　$p=3$ だとどうでしょうか。[1,3,3,2] で考えてみます。

-$[(1.00,0.00),(-1.50,2.60),(-1.50,-2.60),(2.00,-0.00)]$（元の配列）
-$[(0.00,0.00),(1.00,0.00),(-0.50,2.60),(-2.00,0.00),(-0.00,0.00)]$（左からの累積和）

　これだけだとわかりづらいと思うので、累積和の推移を複素数平面上で図示します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/2ee38ad9-f8d8-02c8-6367-d8a5d795e639.png)

　もう少し複雑な例として、$[2,2,1,3,4,3,1,2,4,2]$ という例を考えてみます。（条件を満たす区間は$[2,2,1,3,4,3,1,2,4,3]$ と $[1,3,4,3,1]$ です）

　複素数平面を図示すると以下のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/bdbfea8e-4c1f-58e1-9a79-4f4fa62eb46a.png)

　黄→オレンジ→赤のループ、または、オレンジのループが条件を満たします。このように、問題の条件は**複素数平面上で累積和がループする点の組み合わせ**と言い換えることもできます。$p=2$ の時はそれがたまたま実数軸の数直線だっただけで、実は複素数平面に一般化できたのです。

# 難点

　実はこのような使い方ができる p は限られています。具体的に言うと p が素数の時に限ります。例えば $p=6$ で $[1,0,1,0,1,0]$ の時は、本来ならばできないはずですが、この判定だと OK ということになってしまいます。

　各角度の単位ベクトルを基底 $\boldsymbol{e}$ のように考えた時、p が合成数だと「すべてのベクトル係数が和が等しい時のみ、累積和が 0 になる」という前提が崩れてしまいます。（例えば $p=6$ だと、 $e_0 + e_2 - 2e_4 = 0, e_0 + e_3 = 0$ といった関係が成り立ち、一部のベクトル同士で独立したループが築けてしまう）

　また、実際にこれで判定をしようとする場合、**小数点誤差**を考えないといけません。恐らく、倍精度小数点の精度で $p = 10^9+7, |a_i| < 10^9 
 $ といったオーダーで正確な計算を行うことは困難でしょう。

# まとめ

　隣り合った区間を操作することの判別問題を、複素数を考えることによって一般化することができました。実際の競プロや実務に役立つことはないでしょうが、こういった考察も面白いのではないでしょうか。