Div. 2 の E まで。
A
の値が小さい順に
を
に足す。
B
にするとする。
は素数だけ考えれば良い。
の倍数は連続する区間においては
個おきに出てくるので、最も頻繁に出てくる 2 の倍数にできれば良い。
1 回の操作で奇数は 1 つ減らせるので、数列に含まれる奇数の個数を求める。
要素数が 1 のときはコーナーケースなので注意する。
C
mex は要素数が増えても小さくならないので、数列全体の mex を計算し、その mex を達成できる のうち最小のものを選ぶことを繰り返せば良い。
mex を計算するために個数配列と fenwick tree と二分探索を使ったが、今回の問題では mex は広義単調減少なので、なくても良いはず。
D
まず単体で回文があればその時点で YES を出力。そうでないとき、各要素は長さが 2 または 3 である。
ある部分列が回文になっているとする。
先頭要素と末尾要素に注目する。2 つの要素の長さが同じなら先頭要素と末尾要素で回文を作れる。異なるときには 2+3 か 3+2 になるが、これらも回文にできる。
結局要素を 2 つ選んで回文を作れるかだけ考えれば良く、文字の種類数が少ないことを活かして高速に判定する。（長さ の配列を用意するなど）
E
いくつかのマスを選択し、選択された各マスについて、隣接するマスを多重集合 に追加するとする。全てのマスが
に奇数回含まれるようなマスの選び方を 1 つ求め、選ばれたマス
に対する
の総 XOR を求めれば良い。
なので実は の値はあまり重要ではない。
行目から
行目まで順に、「
が偶数回
に追加されていたなら、マス
を選択する」という操作を行うと、
行目もうまくいく。
証明はできていないが、 について、どの場合も
行目まで上手くいっているかを手元実行で判定しても 1 分くらいでできる。
証明？
公式 Editorial のコメント欄 に証明っぽいものがあった。
公式の解法 2 によって解の存在が保証されており、1 行目のマスの 1 つを選択しなかったことにしても辻褄を合わせていくことができるので、これを繰り返し行うことで 1 行目のマスを一切選択していない解が構築できる。1 行目を全く選択しなかった場合はどのマスを選ぶかは決定的になるので、上記の操作でも良い。
辻褄の合わせ方については、1 行目のマスの 1 つを選択しないことにすると、そのマスを 1 つの角とする 45° の長方形の全てのマスについて、選択するかしないかを反転させることで辻褄を合わせられる。なぜかというと、その長方形上のマスをすべて選択しても、どのマスも集合に追加された回数が変化しないから。（この説明もなぜ回数が変化しないのかという点で不十分な気がしており、微妙。）
例
8 × 8 のグリッドについて、ある解が存在したと仮定し、現在 (1, 3) が選択されているがこれを選択しなかったことにして辻褄を合わせたい場合、以下の X のマスについて、選択するかしないかを反転させれば良い。
· · X · · · · ·
· X · X · · · ·
X · X · X · · ·
· X · X · X · ·
· · X · X · X ·
· · · X · X · X
· · · · X · X ·
· · · · · X · ·
