Palindromic Game

解説

$A$ の中央でないある要素を削除できるならば、それと対称な位置にある要素も削除できる。この $2$ つを削除すると、再び回文になる。

$N$ が偶数のとき、 Bob は Alice の削除した要素と対称な位置にある要素を削除し続けることができるので、 Bob の勝ちである。

$N$ が奇数のとき、 Alice が最初に $A_{\frac{N+1}{2}}$ を削除することができれば、 $N$ が偶数のときと同様にすることで Alice の勝ちである。そうでなければ Bob の勝ちである。

Alice が最初に $A_{\frac{N+1}{2}}$ を削除することができるということは、

$$x, y \in \{A_1, A_2, \dots, A_{\frac{N-1}{2}}\}, ~ x + y = 2 A_{\frac{N+1}{2}}$$

を満たす $x, y$ が存在することと同値である。

すなわち、各 $x$ について条件を満たす $y$ が存在するかどうかをset などを用いて判定することで、全体で $O(N \log{N})$ でこの問題を解くことができる。